| 15 | Num pow(int p) const { return mod_pow<ll>((ll)x, p, mod); } |
| 16 | } T1[MAXN], T2[MAXN]; |
| 17 | void ntt(Num x[], int n, bool inv = false) { |
| 18 | Num z = inv ? ginv : g; |
| 19 | z = z.pow((mod - 1) / n); |
| 20 | for (ll i = 0, j = 0; i < n; i++) { |
| 21 | if (i < j) swap(x[i], x[j]); |
| 22 | ll k = n>>1; |
| 23 | while (1 <= k && k <= j) j -= k, k >>= 1; |
| 24 | j += k; } |
| 25 | for (int mx = 1, p = n/2; mx < n; mx <<= 1, p >>= 1) { |
| 26 | Num wp = z.pow(p), w = 1; |
| 27 | for (int k = 0; k < mx; k++, w = w*wp) { |
| 28 | for (int i = k; i < n; i += mx << 1) { |
| 29 | Num t = x[i + mx] * w; |
| 30 | x[i + mx] = x[i] - t; |
| 31 | x[i] = x[i] + t; } } } |
| 32 | if (inv) { |
| 33 | Num ni = Num(n).inv(); |
| 34 | rep(i,0,n) { x[i] = x[i] * ni; } } } |
| 35 | void inv(Num x[], Num y[], int l) { |
| 36 | if (l == 1) { y[0] = x[0].inv(); return; } |
| 37 | inv(x, y, l>>1); |