洛谷P4238【模板】多项式求逆

 1 #prag 2 ma GCC optimize(2)
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<vector>
 7 #include<cmath>
 8 using namespace std;
 9 #define fi first
10 #define se second
11 #define mp make_pair
12 #define pb push_back
13 typedef long long ll;
14 typedef unsigned long long ull;
15 const ll md=998244353;
16 const int N=262145;
17 int rev[N];
18 void init(int len)
19 {
20     int bit=0,i;
21     while((1<<(bit+1))<=len)    ++bit;
22     for(i=0;i<len;++i)
23         rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
24 }
25 ll poww(ll a,ll b)
26 {
27     ll base=a,ans=1;
28     for(;b;b>>=1,base=base*base%md)
29         if(b&1)
30             ans=ans*base%md;
31     return ans;
32 }
33 void dft(ll *a,int len,int idx)//要求len为2的幂
34 {
35     int i,j,k;ll t1,t2,wn,wnk;
36     for(i=0;i<len;++i)
37         if(i<rev[i])
38             swap(a[i],a[rev[i]]);
39     for(i=1;i<len;i<<=1)
40     {
41         wn=poww(idx==1?3:332748118,(md-1)/(i<<1));
42         for(j=0;j<len;j+=(i<<1))
43         {
44             wnk=1;
45             for(k=j;k<j+i;++k,wnk=wnk*wn%md)
46             {
47                 t1=a[k];t2=a[k+i]*wnk%md;
48                 a[k]+=t2;
49                 (a[k]>=md) && (a[k]-=md);
50                 a[k+i]=t1-t2;
51                 (a[k+i]<0) && (a[k+i]+=md);
52             }
53         }
54     }
55     if(idx==-1)
56     {
57         ll ilen=poww(len,md-2);
58         for(i=0;i<len;++i)    (a[i]*=ilen)%=md;
59     }
60 }
61 ll f[N],g[N],t1[N];
62 int n,n1;
63 void p_inv(ll *f,ll *g,int len)//g=f^(-1);f,g长度不小于2^(ceil(log2(len))+1) 
64 {
65     g[0]=poww(f[0],md-2);
66     for(int i=2,j;i<(len<<1);i<<=1)
67     {
68         init(i<<1);
69         memcpy(t1,f,sizeof(ll)*i);
70         memset(t1+i,0,sizeof(ll)*i);
71         memset(g+(i>>1),0,sizeof(ll)*(i+(i>>1)));
72         dft(t1,i<<1,1);dft(g,i<<1,1);
73         for(j=0;j<(i<<1);++j)
74             g[j]=g[j]*(2+(md-g[j])*t1[j]%md)%md;
75         dft(g,i<<1,-1);
76     }
77 }
78 int main()
79 {
80     int i,t;
81     scanf("%d",&n);n1=n;
82     for(i=0;i<n;++i)
83         scanf("%lld",g+i);
84     for(t=1;t<n;t<<=1);
85     n=t;
86     p_inv(g,f,n);
87     for(i=0;i<n1;++i)
88         printf("%lld ",f[i]);
89     return 0;
90 }