关于NTT分治乘
  • 板块P4705 玩游戏
  • 楼主Prean
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/8/24 20:40
  • 上次更新2023/11/4 09:09:24
查看原帖
关于NTT分治乘
160839
Prean楼主2021/8/24 20:40

RT,因为懒得算分治乘的长度就写了个类似堆式建树的东西。。。

两个样例都AC,后面的WA+RE,有dalao能帮忙看看吗/kel

不知道是不是炸边界了/kk

请不要出现无意义回复。

#include<cstring>
#include<cstdio>
#define clr(f,len) memset(f,0,(len)<<2)
#define cpy(f,g,len) memcpy(f,g,(len)<<2)
typedef unsigned uint;
const uint M=1e5+5,mod=998244353,G=3,invG=332748118;
uint n,m,k,inv[M<<2],t[M<<2],A[M<<2],B[M<<2];
uint CDQ_f[M<<2];
inline void swap(uint&a,uint&b){
	uint c=a;a=b;b=c;
}
inline uint Add(const uint&a,const uint&b){
    return a+b>=mod?a+b-mod:a+b;
}
inline uint Del(const uint&a,const uint&b){
    return b>a?a-b+mod:a-b;
}
inline void px(uint*f,uint*g,const uint&len){
    for(register uint i=0;i<len;++i)f[i]=1ull*f[i]*g[i]%mod;
}
inline void Der(uint*f,const uint&len){
    for(register uint i=1;i<len;++i)f[i-1]=1ull*f[i]*i%mod;
    f[len-1]=0;
}
inline void Int(uint*f,const uint&len){
	for(register uint i=len;i>=1;--i)f[i]=1ull*f[i-1]*inv[i]%mod;
	f[0]=0;
}
inline uint pow(uint a,uint b=mod-2){
    uint ans=1;
    for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;
    return ans;
}
inline void NTT(uint*f,const uint&n,bool flag){
    register uint i,k,w,w1,len,tmp;
    for(i=0;i<n;++i)if(i<t[i])swap(f[i],f[t[i]]);
    for(len=1;len<n;len<<=1){
	    w1=pow(flag?G:invG,(mod-1>>1)/len);
	    for(k=0;k<n;k+=len<<1){
		    w=1;
		    for(i=0;i<len;++i){
			    tmp=1ll*f[i|k|len]*w%mod;
			    if((f[i|k|len]=f[i|k]-tmp)>=mod)f[i|k|len]+=mod;
			    if((f[i|k]=f[i|k]+tmp)>=mod)f[i|k]-=mod;
			    w=1ll*w*w1%mod;
			}
		}
	}
    if(flag)return;k=pow(n);
    for(i=0;i<n;++i)f[i]=1ll*f[i]*k%mod;
}
inline void invp(uint*f,const uint&m){
    static uint b1[M],b2[M],b3[M];
    register uint i,n=1,len;
    while(n<m)n<<=1;b1[0]=pow(f[0]);
    for(len=2;len<=n;len<<=1){
	    for(i=0;i<(len>>1);++i)b3[i]=Add(b1[i],b1[i]);
	    for(i=0;i<(len<<1);++i)t[i]=t[i>>1]>>1|(i&1?len:0);
	    cpy(b2,f,len);
	    NTT(b1,len<<1,1);px(b1,b1,len<<1);
	    NTT(b2,len<<1,1);px(b1,b2,len<<1);
	    NTT(b1,len<<1,0);clr(b1+len,len);
	    for(i=0;i<len;++i)b1[i]=Del(b3[i],b1[i]);
	}
    cpy(f,b1,m);clr(b1,n+n);clr(b2,n+n);clr(b3,n+n);
}
inline void CDQtimes(uint*f,uint*g,const uint&len){
    static uint sav[M<<1];
    register uint i;
    for(i=0;i<(len>>1);++i)sav[i]=g[i],g[i]=0;
    for(i=0;i<len;++i)t[i]=t[i>>1]>>1|(i&1?len>>1:0);
    NTT(f,len,1);NTT(sav,len,1);
    for(i=0;i<len;++i)f[i]=1ll*f[i]*sav[i]%mod,sav[i]=0;
    NTT(f,len,0);
}
void CDQ(uint*f,uint*ed,const uint&len){
    if(len==2)return;
    CDQ(f,ed,len>>1);
    if(f+(len>>1)<=ed)CDQ(f+(len>>1),ed,len>>1);
    CDQtimes(f,f+(len>>1),len);
}
inline void Solve(uint*f,const uint&n){
    register uint i,a,len=1;
    for(i=0;i<n;++i){
	    scanf("%u",&a);
	    CDQ_f[i<<1]=1;CDQ_f[i<<1|1]=mod-a;
	}
    while(len<n+n)len<<=1;
    CDQ(CDQ_f,CDQ_f+n+n,len);
    for(i=0;i<=n;++i)f[i]=CDQ_f[i],CDQ_f[i]=0;
}
inline void lnp(uint*f,const uint&m){
	static uint g[M];uint n=1;
	while(n<m)n<<=1;cpy(g,f,m);
	invp(g,m);Der(f,m);
	for(register uint i=0;i<(n<<1);++i)t[i]=t[i>>1]>>1|(i&1?n:0);
	NTT(f,n<<1,1);NTT(g,n<<1,1);
	px(f,g,n<<1);NTT(f,n<<1,0);
	clr(g,n<<1);
}
signed main(){
    register int i,tk,tmp=1,len=1;
    scanf("%d%d",&n,&m);inv[0]=inv[1]=1;
    Solve(A,n);Solve(B,m);
    scanf("%d",&k);tk=k;
    if(tk<n)tk=n;if(tk<m)tk=m;
    lnp(A,tk+1);lnp(B,tk+1);
    for(i=k;i>=1;--i){
    	A[i]=mod-A[i-1];
    	B[i]=mod-B[i-1];
	}
	A[0]=n;B[0]=m;
    for(i=2;A[i]||B[i];++i){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	    tmp=1ll*tmp*inv[i]%mod;
	    A[i]=1ll*A[i]*tmp%mod;
	    B[i]=1ll*B[i]*tmp%mod;
	}
    while(len<=tk+tk)len<<=1;
    for(i=0;i<len;++i)t[i]=t[i>>1]>>1|(i&1?len>>1:0);
    NTT(A,len,1);NTT(B,len,1);
    px(A,B,len);NTT(A,len,0);
    tmp=pow(1ll*n*m%mod);
    for(i=1;i<=k;++i){
	    tmp=1ll*tmp*i%mod;
	    printf("%d\n",1ll*A[i]*tmp%mod);
	}
}
2021/8/24 20:40
加载中...