# 萌新初学OI,求助

@Sai_0511 2019-04-19 22:43 回复

#include <bits/stdc++.h>
#define il inline
const int maxn = 4e5 + 10;
const int mod = 998244353;
using namespace std;
int f[maxn],g[maxn];
int n,m,i,j,k;
il void _swap(int& x,int& y) {
int t = x;  x = y;  y = t;
return;
}
il int mul(int a,int b) {
return 1ll * a * b % mod;
}
il int ins(int a,int b) {
a += b;  if(a > mod) a -= mod;  return a;
}
il int sub(int a,int b) {
a -= b;  if(a < 0) a += b;  return a;
}
il int qpow(int a,int b,int p = mod) {
int res = 1;
while(b) {
if(b & 1) res = mul(res,a);
a = mul(a,a);  b >>= 1;
}
return res;
}
namespace Poly_Space {
int rev[maxn],A[maxn],B[maxn],tmp[maxn],C[maxn],D[maxn];
il void ntt(int* p,int lim,int type) {
int li = 1, tot = 0;
while(li < lim) li <<= 1, tot++;
for(int i = 0;i < li;i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (tot - 1));
for(int i = 0;i < li;i++) if(i < rev[i]) _swap(p[i],p[rev[i]]);
for(int i = 1;i < li;i <<= 1) {
int wn = qpow(3,(mod - 1) / (i << 1));  tmp[0] = 1;
for(int j = 1;j < i;j++) tmp[j] = mul(tmp[j - 1],wn);
for(int j = 0;j < li;j += i << 1) {
for(int k = 0;k < i;k++) {
int x = p[j + k], y = mul(tmp[k],p[j + k + i]);
p[j + k] = ins(x,y);  p[j + k + i] = sub(x,y);
}
}
}
if(!~type) {
reverse(p + 1,p + li);  int inv = qpow(lim,mod - 2);
for(int i = 0;i < li;i++) p[i] = mul(p[i],inv);
}
return;
}
void Poly_Inv(int* a,int* b,int deg) {
if(deg == 1) return void(b[0] = qpow(a[0],mod - 2));
Poly_Inv(a,b,deg >> 1);
for(int i = 0;i < deg;i++) A[i] = a[i], B[i] = b[i];
ntt(A,deg << 1,1);  ntt(B,deg << 1,1);
for(int i = 0;i < deg << 1;i++) A[i] = mul(mul(A[i],B[i]),B[i]);
ntt(A,deg << 1,-1);
for(int i = 0;i < deg;i++) b[i] = sub(1ll * (b[i] << 1) % mod,A[i]);
return;
}
il void direv(int* a,int* b,int li) {
for(int i = 1;i < li;i++) b[i - 1] = mul(a[i],i);  b[li - 1] = 0;
}
il void integ(int* a,int* b,int li) {
for(int i = 1;i < li;i++) b[i] = mul(a[i - 1],qpow(i,mod - 2));  b[0] = 0;
}
il void Poly_Ln(int* a,int* b,int li) {
direv(a,C,li);  Poly_Inv(a,D,li);
ntt(C,li << 1,1);  ntt(D,li << 1,1);
for(int i = 0;i < li << 1;i++) C[i] = mul(C[i],D[i]);
ntt(C,li << 1,-1);  integ(C,b,li);
}
}
using namespace Poly_Space;
int main() {
scanf("%d",&n);
for(int i = 0;i < n;i++) scanf("%d",&f[i]);
int li = 1;  while(li < n) li <<= 1;
Poly_Ln(f,g,li);
for(int i = 0;i < n;i++) printf("%d ",g[i]);
return 0;
}
@Irressey 2019-04-19 22:51 回复 举报