题目
有一排 (n) 个球，定义一个组可以只包含一个球或者包含两个相邻的球。
现在一个球只能分到一个组中，求从这些球中取出 (k) 组的方案数。
(nleq 10^9 ,k<2^{15})。
分析
设(f[n][k])表示方案数，则
[f[n][k]=f[n-1][k]+f[n-1][k-1]+f[n-2][k-1]
]
考虑另一种转移方式就是
[f[n+m][k]=sum_{i=0}^kf[n][i]f[m][k-i]+sum_{i=0}^{k-1}f[n-1][i]f[m-1][k-i-1]
]
如果这些用生成函数(f_n(x))表示的话就是
[f_n(x)=f_{n-1}(x)+f_{n-1}(x-1)+f_{n-2}(x-1)
]
[f_{n+m}(x)=f_{n}(x)f_{m}(x)+xf_{n-1}(x)f_{m-1}(x)
]
其实直接用下面这一条二进制拼凑结果即可，需要维护(f_{n}(x),f_{n-1}(x),f_{n-2}(x))
代码
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
#define rr register
#define mem(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int mod=998244353,inv3=332748118,N=70011;
typedef long long lll; typedef unsigned long long ull;
int n,m,Gmi[31],Imi[31],len,ff[3][N],ans[2][N],gg[3][N];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed ksm(int x,int y){
rr int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
namespace Theoretic{
int rev[N],LAST; ull Wt[N],F[N];
inline void Pro(int n){
if (LAST==n) return; LAST=n,Wt[0]=1;
for (rr int i=0;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
}
inline void NTT(int *f,int n,int op){
Pro(n);
for (rr int i=0;i<n;++i) F[i]=f[rev[i]];
for (rr int o=1,len=1;len<n;++o,len<<=1){
rr int W=(op==1)?Gmi[o]:Imi[o];
for (rr int j=1;j<len;++j) Wt[j]=Wt[j-1]*W%mod;
for (rr int i=0;i<n;i+=len+len)
for (rr int j=0;j<len;++j){
rr int t=Wt[j]*F[i|j|len]%mod;
F[i|j|len]=F[i|j]+mod-t,F[i|j]+=t;
}
if (o==10) for (rr int j=0;j<n;++j) F[j]%=mod;
}
if (op==-1){
rr int invn=ksm(n,mod-2);
for (rr int i=0;i<n;++i) F[i]=F[i]%mod*invn%mod;
}else for (rr int i=0;i<n;++i) F[i]%=mod;
for (rr int i=0;i<n;++i) f[i]=F[i];
}
inline void trans_ans(){
for (rr int j=0;j<3;++j) cpy(gg[j],ff[j],len);
for (rr int j=0;j<3;++j) mem(gg[j]+n,len-n);
for (rr int j=0;j<3;++j) NTT(gg[j],len,1);
NTT(ans[0],len,1),NTT(ans[1],len,1);
for (rr int i=0;i<len;++i){
rr lll now0=ans[0][i],now1=ans[1][i];
ans[0][i]=now0*gg[0][i]%mod,gg[0][i]=now1*gg[1][i]%mod;
ans[1][i]=now0*gg[1][i]%mod,gg[1][i]=now1*gg[2][i]%mod;
}
NTT(ans[0],len,-1),NTT(ans[1],len,-1);
NTT(gg[0],len,-1),NTT(gg[1],len,-1);
for (rr int j=0;j<2;++j)
for (rr int i=1;i<len;++i)
ans[j][i]=(ans[j][i]+gg[j][i-1])%mod;
for (rr int j=0;j<2;++j) mem(ans[j]+n,len-n);
}
inline void trans(){
for (rr int j=0;j<3;++j) NTT(ff[j],len,1);
for (rr int i=0;i<len;++i){
rr lll now0=ff[0][i],now1=ff[1][i],now2=ff[2][i];
ff[0][i]=now0*now0%mod,gg[0][i]=now1*now1%mod;
ff[1][i]=now0*now1%mod,gg[1][i]=now1*now2%mod;
ff[2][i]=now1*now1%mod,gg[2][i]=now2*now2%mod;
}
for (rr int j=0;j<3;++j)
NTT(ff[j],len,-1),NTT(gg[j],len,-1);
for (rr int j=0;j<3;++j)
for (rr int i=1;i<len;++i)
ff[j][i]=(ff[j][i]+gg[j][i-1])%mod;
for (rr int j=0;j<3;++j) mem(ff[j]+n,len-n);
}
}
inline void GmiImi(){
for (rr int i=0;i<31;++i) Gmi[i]=ksm(3,(mod-1)/(1<<i));
for (rr int i=0;i<31;++i) Imi[i]=ksm(inv3,(mod-1)/(1<<i));
}
signed main(){
m=iut(),n=iut()+1,GmiImi();
for (len=1;len<n*2;len<<=1);
ff[0][0]=ff[1][0]=ff[0][1]=ans[0][0]=1;
for (rr int t=1;t<=m;t<<=1){
if (m&t) Theoretic::trans_ans();
Theoretic::trans();
}
for (rr int i=1;i<n;++i)
print(ans[0][i]),putchar(32);
return 0;
}