(模板)NTT

2019-04-13 15:39发布

站内文章 / 模拟电子
12009 0 1012
//const LL P = 50000000001507329LL; //190734863287 * 2 ^ 18 + 1 常数巨大 //const int P = 1004535809LL; //479 * 2 ^ 21 + 1 const int P = 1004535809; // 119 * 2 ^ 23 + 1 const int G = 3; int a[N], b[N]; int wn[25]; int n; LL mul(LL x, LL y) { return (x * y - (LL)(x / (long double)P * y + 1e-3) * P + P) % P; } int qpow(int x, int k, int p) { int ret = 1; while(k) { if(k & 1) ret = 1LL * ret * x % p; k >>= 1; x = 1LL * x * x % p; } return ret; } void getwn() { for(int i = 1; i <= 21; ++i) { int t = 1 << i; wn[i] = qpow(G, (P - 1) / t, P); } } void change(int *y, int len) { for(int i = 1, j = len / 2; i < len - 1; ++i) { if(i < j) swap(y[i], y[j]); int k = len / 2; while(j >= k) { j -= k; k /= 2; } j += k; } } void NTT(int *y, int len, int on) { change(y, len); int id = 0; for(int h = 2; h <= len; h <<= 1) { ++id; for(int j = 0; j < len; j += h) { int w = 1; for(int k = j; k < j + h / 2; ++k) { int u = y[k]; int t = 1LL * y[k+h/2] * w % P; y[k] = u + t; if(y[k] >= P) y[k] -= P; y[k+h/2] = u - t + P; if(y[k+h/2] >= P) y[k+h/2] -= P; w = 1LL * w * wn[id] % P; } } } if(on == -1) { for(int i = 1; i < len / 2; ++i) swap(y[i], y[len-i]); int inv = qpow(len, P - 2, P); for(int i = 0; i < len; ++i) y[i] = 1LL * y[i] * inv % P; } }