比赛 |
noi2017模板练习+ |
评测结果 |
AAAAAAAAAA |
题目名称 |
帕秋莉的超级多项式 |
最终得分 |
100 |
用户昵称 |
FoolMike |
运行时间 |
14.647 s |
代码语言 |
C++ |
内存使用 |
12.88 MiB |
提交时间 |
2017-07-18 19:02:26 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=3e5+10,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
int ans=1;
for (;y;y>>=1,x=mul(x,x))
if (y&1) ans=mul(ans,x);
return ans;
}
int inverse[N];
void init_inv(){
inverse[1]=1;
for (int i=2;i<N;i++) inverse[i]=mul(p-p/i,inverse[p%i]);
}
int w[N],iw[N];
void init(int n){
w[0]=1;w[1]=power(3,(p-1)/n);
for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
for (int i=0;i<=n;i++) iw[i]=w[n-i];
}
void fft(int n,int *a,int *w){
for (int i=0,j=0;i<n;i++){
if (i<j) swap(a[i],a[j]);
for (int k=n>>1;(j^=k)<k;k>>=1);
}
for (int i=2;i<=n;i<<=1){
int m=i>>1,step=n/i;
for (int j=0;j<n;j+=i)
for (int k=0,pos=0;k<m;k++,pos+=step){
int t=mul(a[j+k+m],w[pos]);
a[j+k+m]=dec(a[j+k],t);
a[j+k]=inc(a[j+k],t);
}
}
if (w==iw)
for (int i=0;i<n;i++) a[i]=mul(a[i],inverse[n]);
}
void getinv(int n,int *a,int *b){
if (n==1) return void(b[0]=power(a[0],p-2));
getinv((n+1)>>1,a,b);
int size=1;
while (size<n+n) size<<=1;
init(size);
static int tmp[N];
for (int i=0;i<n;i++) tmp[i]=a[i];
for (int i=n;i<size;i++) tmp[i]=0;
fft(size,tmp,w);fft(size,b,w);
for (int i=0;i<size;i++) b[i]=mul(b[i],dec(2,mul(b[i],tmp[i])));
fft(size,b,iw);
for (int i=n;i<size;i++) b[i]=0;
}
void getln(int n,int *a,int *b){
static int tmp[N],inv[N];
int size=1;
while (size<n+n) size<<=1;
for (int i=0;i<size;i++) tmp[i]=inv[i]=0;
getinv(n,a,inv);
for (int i=0;i<n;i++) tmp[i]=mul(a[i+1],i+1);
init(size);
fft(size,tmp,w);fft(size,inv,w);
for (int i=0;i<size;i++) tmp[i]=mul(tmp[i],inv[i]);
fft(size,tmp,iw);
for (int i=1;i<n;i++) b[i]=mul(tmp[i-1],inverse[i]);
}
void getexp(int n,int *a,int *b){
if (n==1) return void(b[0]=1);
getexp((n+1)>>1,a,b);
int size=1;
while (size<n+n) size<<=1;
static int ln[N];
for (int i=0;i<size;i++) ln[i]=0;
getln(n,b,ln);
for (int i=0;i<n;i++) ln[i]=dec(a[i],ln[i]);
ln[0]=inc(ln[0],1);
init(size);
fft(size,b,w);fft(size,ln,w);
for (int i=0;i<size;i++) b[i]=mul(b[i],ln[i]);
fft(size,b,iw);
for (int i=n;i<size;i++) b[i]=0;
}
void getroot(int n,int *a,int *b){
if (n==1) return void(b[0]=sqrt(a[0]));
getroot((n+1)>>1,a,b);
int size=1;
while (size<n+n) size<<=1;
static int tmp[N],inv[N];
for (int i=0;i<size;i++) tmp[i]=inv[i]=0;
getinv(n,b,inv);
for (int i=0;i<n;i++) tmp[i]=a[i];
for (int i=n;i<size;i++) tmp[i]=0;
fft(size,tmp,w);fft(size,inv,w);fft(size,b,w);
for (int i=0;i<size;i++)
b[i]=mul(mul(inv[i],inverse[2]),inc(mul(b[i],b[i]),tmp[i]));
fft(size,b,iw);
for (int i=n;i<size;i++) b[i]=0;
}
int n,k,f[N],g[N];
int main()
{
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout);
scanf("%d%d",&n,&k);
for (int i=0;i<n;i++) scanf("%d",&f[i]);
init_inv();
getroot(n,f,g);
for (int i=0;i<n;i++) f[i]=0;
getinv(n,g,f);
g[0]=0;
for (int i=1;i<n;i++) g[i]=mul(f[i-1],inverse[i]);
for (int i=0;i<n;i++) f[i]=0;
getexp(n,g,f);
for (int i=0;i<n;i++) g[i]=0;
getinv(n,f,g);
g[0]=inc(g[0],1);
for (int i=0;i<n;i++) f[i]=0;
getln(n,g,f);
f[0]=inc(f[0],1);
for (int i=0;i<n;i++) g[i]=0;
getln(n,f,g);
for (int i=0;i<n;i++) g[i]=mul(g[i],k);
for (int i=0;i<n;i++) f[i]=0;
getexp(n,g,f);
for (int i=0;i<n;i++) g[i]=mul(f[i+1],i+1);
for (int i=0;i<n;i++) f[i]=0;
for (int i=0;i<n;i++) printf("%d ",g[i]);
puts("");
return 0;
}