粘板子:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int N = 100050;
const int M = N*3;
template<typename T>
inline void read(T&x)
{
T f = 1,c = 0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
x = f*c;
}
template<typename T>inline void Mod(T&x){if(x>=MOD)x-=MOD;}
int fastpow(int x,int y)
{
int ret = 1;
while(y)
{
if(y&1)ret=1ll*ret*x%MOD;
x=1ll*x*x%MOD;y>>=1;
}
return ret;
}
int inv(int x){return fastpow(x,MOD-2);}
int to[M],lim,L,LL[M];
void init(int len)
{
lim=LL[2]=1;
while(lim<len)lim<<=1,LL[lim<<1]=LL[lim]+1;
}
void get_lim(int len)
{
lim = len,L = LL[len];
for(int i=1;i<=lim;i++)to[i]=((to[i>>1]>>1)|((i&1)<<(L-1)));
}
void ntt(int*a,int len,int k)
{
for(int i=0;i<len;i++)
if(i<to[i])swap(a[i],a[to[i]]);
for(int i=1;i<len;i<<=1)
{
int w0 = fastpow(3,(MOD-1)/(i<<1));
for(int j=0;j<len;j+=(i<<1))
{
int w = 1;
for(int o=0;o<i;o++,w=1ll*w*w0%MOD)
{
int w1 = a[j+o],w2 = 1ll*a[j+o+i]*w%MOD;
Mod(a[j+o] = w1+w2);
Mod(a[j+o+i] = w1+MOD-w2);
}
}
}
if(k==-1)
{
for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]);
int Inv = inv(len);
for(int i=0;i<len;i++)a[i]=1ll*a[i]*Inv%MOD;
}
}
int a[M],b[M],c[M];
int f[M],g[M],n;
void cdq(int l,int r)
{
if(l==r)return ;
int mid = (l+r)>>1;
cdq(l,mid);
get_lim(2*(r-l+1));
for(int i=0;i<lim;i++)a[i]=b[i]=0;
for(int i=0;i<=mid-l;i++)a[i]=f[l+i];
for(int i=1;i<=r-l+1;i++)b[i]=g[i];
ntt(a,lim,1),ntt(b,lim,1);
for(int i=0;i<=lim;i++)c[i]=1ll*a[i]*b[i]%MOD;
ntt(c,lim,-1);
for(int i=mid+1-l;i<=r-l;i++)Mod(f[i+l]+=c[i]);
cdq(mid+1,r);
}
int main()
{
// freopen("tt.in","r",stdin);
read(n);init(n<<1);f[0]=1;
for(int i=1;i<n;i++)read(g[i]);
cdq(0,lim-1);
for(int i=0;i<n;i++)printf("%d ",f[i]);
puts("");
return 0;
}

最新文章

  1. AC日记——字符串判等 openjudge 1.7 17
  2. C++模板编程里的主版本模板类、全特化、偏特化(C++ Type Traits)
  3. 计时函数 clock() in c and c++
  4. nginx看端口使用情况
  5. C和C++混合编译
  6. 问题:-[UIViewController _loadViewFromNibNamed:bundle:] loaded the &quot;BlueView&quot; nib but the view outlet was not set.
  7. css3_note
  8. python列表元组
  9. IBATIS动态SQL
  10. .NET读写Excel工具Spire.Xls使用(1)入门介绍
  11. hdu_5925_Coconuts(离散化+dfs)
  12. sql server 数据库导出表里所有数据成insert 语句
  13. Charles使用(二)
  14. hosts管理工具1.0发布了。。。。
  15. 了解Vue.js
  16. Python requests 多线程抓取 出现HTTPConnectionPool Max retires exceeded异常
  17. oracle中REGEXP_SUBSTR方法的使用
  18. 指定分隔符连接数组元素join()
  19. Java NIO.2 —— 文件或目录移动操作
  20. WPF根据ScrollViewer的滚动条出现与否来设置触发器Trigger

热门文章

  1. 基于XC7Z100+AD9361的双收双发无线电射频板卡
  2. 树莓派GPIO开发(三):蜂鸣器-PWM调节
  3. Spring MVC 是什么? 核心总结
  4. Spring Boot 自定义配置文件异常&quot;expected single matching bean but found 2&quot;
  5. [LeetCode]1470. 重新排列数组
  6. Hbuilderx换行问题(属性合并一行展示)
  7. C# 提取Word中插入的多媒体文件(视频、音频)
  8. CobaltStrike逆向学习系列(13):RDI 任务执行流程分析
  9. linux下使用fcrackzip来暴力破解zip压缩包
  10. 从数据源支持、支持方式等角度深入了解Smartbi与Tableau