CF755G PolandBall and Many Other Balls

题面传送门
首先我们设\(f_{i,j}\)表示到了第\(i\)个球，选了\(j\)个框的方案数，那么我们有\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-2,j-1}\)
然后我们又发现对于一个\(f_{i,j}\)，我们可以拆成两个\(f_{\frac{i}{2},j}\)与两个\(f_{\frac{i}{2}-1,j-1}\)的卷积，所以我们可以倍增NTT
具体的，我们对于当前的\(n\)，我们维护\(n,n-1,n-2\)的值，这样就可以推到\(2\times n,2\times n-1,2\times n-2\)了。
然后这样总共就是\(8\)次倍增NTT就可以求得答案了。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N (1<<16)
#define M 1000000
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-4)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
using namespace std;
int n,m,k,Ts,tr[N+5];
I ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}const ll G=3,InvG=mpow(G);
I void NTT(ll *F,int n,int Fl){
	RI i,j,h;ll key,pus,now;for(i=0;i>=1;return cnt;}
int main(){
	freopen("1.in","r",stdin);
	RI i,j;scanf("%d%d",&n,&k);for(m=1;m<=(k<<1);m<<=1);for(i=0;i>1]>>1)|((i&1)?m/2:0);
	S.F[0][0]=1;S.F[1][0]=S.F[1][1]=1;S.F[2][0]=1;S.F[2][1]=3;S.F[2][2]=1;
	if(n==1){for(i=1;i<=k;i++) printf("%lld ",S.F[1][i]);return 0;}
	if(n>2){Ts=Cnt(n)-1;if((n>>Ts-1)&1) S.Ins();for(i=Ts-2;~i;i--) S.Jump(),n>>i&1&&(S.Ins(),0);}
	for(i=1;i<=k;i++) printf("%lld ",S.F[2][i]%mod);
}