多项式求逆入门 板题(Luogu P4238)

2019-04-14 16:17发布

站内文章 / 模拟电子
10290 0 1314
class="markdown_views prism-atom-one-light">
模板Code
#include #include #include using namespace std; const int mod = 998244353, g = 3, MAXN = 1<<18; typedef long long LL; inline void change(int arr[], const int &len) { register int i, j, k; for(i = 1, j = len/2; i < len-1; ++i) { if(i < j) swap(arr[i], arr[j]); k = len/2; while(j >= k) j -= k, k >>= 1; j += k; } } inline int qmul(int a, int b, const int &c) { register int ret = 1; while(b) { if(b&1) ret = (LL)ret * a % c; a = (LL)a * a % c; b >>= 1; } return ret; } inline void NTT(int arr[], const int &len, const int &flg) { change(arr, len); register int wn, w, A0, wA1, i, j, k; for(i = 2; i <= len; i <<= 1) { if(~flg) wn = qmul(g, (mod-1)/i, mod); else wn = qmul(g, (mod-1) - (mod-1)/i, mod); for(j = 0; j < len; j += i) { w = 1; for(k = j; k < j + i/2; ++k) { A0 = arr[k], wA1 = (LL)w * arr[k + i/2]% mod; arr[k] = (A0 + wA1) % mod; arr[k + i/2] = ((A0 - wA1) % mod + mod) % mod; w = (LL)w * wn % mod; } } } if(flg == -1) { register int rev = qmul(len, mod-2, mod); for(i = 0; i < len; ++i) arr[i] = (LL)arr[i] * rev % mod; } } int a[MAXN], b[MAXN], c[MAXN]; void work(const int &deg, int a[], int b[]) { if(deg == 1) { b[0] = qmul(a[0], mod-2, mod); return; } work(deg+1>>1, a, b); register int len = 1; while(len < deg<<1) len <<= 1; for(int i = 0; i < deg; ++i) c[i] = a[i]; for(int i = deg; i < len; ++i) c[i] = 0; NTT(c, len, 1); NTT(b, len, 1); for(int i = 0; i < len; ++i) b[i] = (2 - (LL)b[i]*c[i]%mod + mod) % mod * b[i] % mod; NTT(b, len, -1); for(int i = deg; i < len; ++i) b[i] = 0; } int n; void init() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d", &a[i]); } void solve() { work(n, a, b); for(int i = 0; i < n; ++i) printf("%d%c", b[i], i == n-1 ? ' ' : ' '); } int main () { init(); solve(); }

热门文章