-
Notifications
You must be signed in to change notification settings - Fork 22
/
fft_test_ntt.cpp
130 lines (124 loc) · 3.22 KB
/
fft_test_ntt.cpp
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
// MAXN must be power of 2 !!
// MOD-1 needs to be a multiple of MAXN !!
// big mod and primitive root for NTT:
const int MOD=998244353,RT=3,MAXN=1<<18;
typedef vector<ll> poly;
// FFT
/*
struct CD {
double r,i;
CD(double r=0, double i=0):r(r),i(i){}
double real()const{return r;}
void operator/=(const int c){r/=c, i/=c;}
};
CD operator*(const CD& a, const CD& b){
return CD(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}
CD operator+(const CD& a, const CD& b){return CD(a.r+b.r,a.i+b.i);}
CD operator-(const CD& a, const CD& b){return CD(a.r-b.r,a.i-b.i);}
const double pi=acos(-1.0);
*/
int mulmod(ll a, ll b){return a*b%MOD;}
int addmod(int a, int b){int r=a+b;if(r>=MOD)r-=MOD;return r;}
int submod(int a, int b){int r=a-b;if(r<0)r+=MOD;return r;}
int pm(ll a, ll e){
int r=1;
while(e){
if(e&1)r=mulmod(r,a);
e>>=1;a=mulmod(a,a);
}
return r;
}
int inv(int a){return pm(a,MOD-2);}
// NTT
struct CD {
int x;
CD(int x):x(x){}
CD(){}
int get()const{return x;}
};
CD operator*(const CD& a, const CD& b){return CD(mulmod(a.x,b.x));}
CD operator+(const CD& a, const CD& b){return CD(addmod(a.x,b.x));}
CD operator-(const CD& a, const CD& b){return CD(submod(a.x,b.x));}
vector<int> rts(MAXN+9,-1);
CD root(int n, bool inv){
int r=rts[n]<0?rts[n]=pm(RT,(MOD-1)/n):rts[n];
return CD(inv?pm(r,MOD-2):r);
}
CD cp1[MAXN+9],cp2[MAXN+9];
int R[MAXN+9];
void dft(CD* a, int n, bool inv){
fore(i,0,n)if(R[i]<i)swap(a[R[i]],a[i]);
for(int m=2;m<=n;m*=2){
//double z=2*pi/m*(inv?-1:1); // FFT
//CD wi=CD(cos(z),sin(z)); // FFT
CD wi=root(m,inv); // NTT
for(int j=0;j<n;j+=m){
CD w(1);
for(int k=j,k2=j+m/2;k2<j+m;k++,k2++){
CD u=a[k];CD v=a[k2]*w;a[k]=u+v;a[k2]=u-v;w=w*wi;
}
}
}
//if(inv)fore(i,0,n)a[i]/=n; // FFT
if(inv){ // NTT
CD z(pm(n,MOD-2)); // pm: modular exponentiation
fore(i,0,n)a[i]=a[i]*z;
}
}
poly multiply(poly& p1, poly& p2){
int n=p1.size()+p2.size()+1;
int m=1,cnt=0;
while(m<=n)m+=m,cnt++;
fore(i,0,m){R[i]=0;fore(j,0,cnt)R[i]=(R[i]<<1)|((i>>j)&1);}
fore(i,0,m)cp1[i]=0,cp2[i]=0;
fore(i,0,p1.size())cp1[i]=p1[i];
fore(i,0,p2.size())cp2[i]=p2[i];
dft(cp1,m,false);dft(cp2,m,false);
fore(i,0,m)cp1[i]=cp1[i]*cp2[i];
dft(cp1,m,true);
poly res;
n-=2;
//fore(i,0,n)res.pb((ll)floor(cp1[i].real()+0.5)); // FFT
fore(i,0,n)res.pb(cp1[i].x); // NTT
return res;
}
vector<ll> p;
ll f[100005],fi[100005];
int n;ll m;
void doit(vector<ll>& p, bool asd){
fore(i,0,n)p[i]=mulmod(p[i],f[i]);
vector<ll> q;
fore(i,0,n)q.pb(fi[n-1-i]);
if(asd)for(int i=n-2;i>=0;i-=2)q[i]=MOD-q[i];
vector<ll> v=multiply(p,q);
p.clear();
fore(i,0,n)p.pb(v[i+n-1]);
fore(i,0,n)p[i]=mulmod(p[i],fi[i]);
}
int main(){
f[0]=1;
fore(i,1,100005)f[i]=mulmod(f[i-1],i);
fore(i,0,100005)fi[i]=inv(f[i]);
scanf("%d%lld",&n,&m);n++;
fore(i,0,n){
int x;
scanf("%d",&x);
p.pb(x);
}
doit(p,false);
fore(i,0,n)p[i]=mulmod(p[i],pm(inv(i+1),m));
doit(p,true);
fore(i,0,n)printf("%lld%c",p[i]," \n"[i==n-1]);
return 0;
}