Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using poly = vector<int>;
- void bit_reverse_swap(poly &a) {
- int n = SZ(a);
- for (int i = 1, j = n >> 1, k; i < n - 1; i++) {
- if (i < j) swap(a[i], a[j]);
- //tricky
- for (k = n >> 1; j >= k; j -= k, k >>= 1); //inspect the highest "1"
- j += k;
- }
- }
- const int g = 3; // mod 998244353 下的最小原根
- void FFT(poly &a, int type) {
- bit_reverse_swap(a);
- int n = SZ(a);
- for (int i = 2; i <= n; i *= 2) {
- const auto wi = fp(g, type * (mod - 1) / i); // fp(g, (mod - 1) / i) 是 i 次单位根
- for (int j = 0; j < n; j += i) {
- auto w(1);
- for (int k = j, h = i / 2; k < j + h; k++) {
- auto t = Mul(w, a[k + h]), u = a[k];
- a[k] = Add(u, t);
- a[k + h] = Sub(u, t);
- mul(w, wi);
- }
- }
- }
- const int inv = fp(n, -1);
- if (type == -1) for (auto &x : a) mul(x, inv);
- }
- void mul(poly &a, const poly &b) {
- int n = pow2(SZ(a) + SZ(b) - 1);
- auto _b = b;
- a.resize(n), _b.resize(n);
- FFT(a, 1), FFT(_b, 1);
- rng (i, 0, n) mul(a[i], _b[i]);
- FFT(a, -1);
- }
- void fp(poly &a, const int n) {
- a.resize((ul)pow2((SZ(a)-1) * n + 1));
- FFT(a, 1);
- for(auto &x: a) x = fp(x, n);
- FFT(a, -1);
- }
Add Comment
Please, Sign In to add comment