————————————————————————–
LuoguP4238【模板】多项式求逆（<==链接请点这儿）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define mo 998244353 #define G 3 using namespace std; const int N=300010; int n,m,L,H,a[N],b[N],w[N],A[N],B[N],c[N],P[N]; ll INV; ll mi(ll x,int y) { ll ans=1; while (y) { if (y&1) ans=ans*x%mo; x=x*x%mo; y>>=1; } return ans; } void NTT(int *a,int f) { for (int i=0,j=0;i<L;i++) { if (i>j) swap(a[i],a[j]); for (int k=L>>1;(j^=k)<k;k>>=1); } for (int len=2;len<=L;len<<=1) { int l=len>>1; ll W=mi(G,(mo-1)/len); for (int i=1;i<l;i++) w[i]=W*w[i-1]%mo; for (int i=0;i<L;i+=len) for (int j=0;j<l;j++) { int x=a[i+j],y=(ll)w[j]*a[i+j+l]%mo; a[i+j]=(x+y>=mo)?x+y-mo:x+y;a[i+j+l]=(x-y<0)?x-y+mo:x-y; } } if (f==-1) { for (int i=1;i<L/2;i++) swap(a[i],a[L-i]); for (int i=0;i<L;i++) a[i]=(ll)a[i]*INV%mo; } } void pre(int l) { w[0]=1; L=1;H=0; while (L<l) L<<=1,H++; INV=mi(L,mo-2); for (int i=0;i<L;i++) A[i]=B[i]=0; } void mul(int *a,int *b,int *c,int n) { pre(n); for (int i=0;i<(n>>1);i++) A[i]=b[i],B[i]=c[i]; NTT(A,1);NTT(B,1); for (int i=0;i<L;i++) A[i]=(ll)A[i]*B[i]%mo; NTT(A,-1); for (int i=0;i<n;i++) a[i]=A[i]; } void Get_INV(int *a,int n) { if (n==1) { b[0]=mi(a[0],mo-2); return; } Get_INV(a,n>>1); mul(P,b,b,n); mul(P,P,a,n<<1); for (int i=0;i<n;i++) b[i]=((b[i]+b[i])%mo-P[i]+mo)%mo; } int main() { scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&a[i]); int X=1; for (;X<n;X<<=1); Get_INV(a,X); for (int i=0;i<n;i++) printf("%d%c",b[i]," \n"[i==n-1]); return 0; } |
