QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#450936#6349. Is This FFT?Harry27182WA 0ms40496kbC++143.5kb2024-06-22 19:41:312024-06-22 19:41:31

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 19:41:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:40496kb
  • [2024-06-22 19:41:31]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[205][1<<16],n,mod,fac[1<<16],inv[1<<16],f[205][1<<16],val[1<<16],tmp[1<<16];
int cur[20][1<<16][2],d[1<<16],p[1<<16],a[1<<16],g,val1[205][1<<16],val2[205][1<<16];
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int qpow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;y/=2;
	}
	return res;
}
struct FastMod
{
    using ull=unsigned long long;
    using L=__int128;
    ull b,m;
    void init(ull x){b=x;m=ull((L(1)<<64)/b);}
    ull reduce(ull a)
    {
        ull q=(ull)((L(m)*a)>>64),r=a-q*b;
        return r>=b?r-b:r;
    }
}F;
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int binom(int x,int y){return (x<y?0:F.reduce(F.reduce(fac[x]*inv[y])*inv[x-y]));}
void ntt(int *a,int n,int x)
{
	for(int i=0;i<n;i++)if(i<p[i])swap(a[i],a[p[i]]);
	for(int i=1,p=0;i<n;i<<=1,p++)
	{
		for(int j=0;j<n;j+=i<<1)
		{
			for(int k=0;k<i;k++)
			{
				int w=(x==1?cur[p][k][0]:cur[p][k][1]);
				int x=a[j+k],y=F.reduce(w*a[i+j+k]);
				a[j+k]=x;Add(a[j+k],y);
				a[i+j+k]=x;Add(a[i+j+k],mod-y);
			}
		}
	}
	if(x==-1)
	{
		int inv=qpow(n,mod-2);
		for(int i=0;i<n;i++)a[i]=F.reduce(a[i]*inv);
	}
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>mod;F.init(mod);
	int phi=mod-1,x=mod-1,tot=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)d[++tot]=i;
		while(x%i==0)x/=i;
	}
	if(x>1)d[++tot]=x;
	for(int i=1;i<=mod;i++)
	{
		int flag=1;
		if(qpow(i,phi)!=1)continue;
		for(int j=1;j<=tot;j++)
		{
			if(qpow(i,phi/d[j])==1){flag=0;break;}
		}
		if(flag==1){g=i;break;}
	}
	int lim=1,Log=0;
	while(lim<=n*(n-1)/2)lim<<=1,Log++;
	for(int i=0;i<lim;i++)p[i]=(p[i>>1]>>1)|((i&1)<<(Log-1));
	for(int i=1,p=0;i<lim;i<<=1,p++)
	{
		int wn=qpow(g,(mod-1)/(i<<1));
		for(int j=0;j<lim;j+=i<<1)
		{
			for(int k=0,w=1;k<i;k++,w=F.reduce(w*wn))cur[p][k][0]=w,cur[p][k][1]=qpow(w,mod-2);
		}
	}
	fac[0]=inv[0]=1;dp[1][0]=1;
	for(int i=1;i<=n*(n-1)/2;i++)fac[i]=F.reduce(fac[i-1]*i);
	inv[n*(n-1)/2]=qpow(fac[n*(n-1)/2],mod-2);
	for(int i=n*(n-1)/2-1;i>=1;i--)inv[i]=F.reduce(inv[i+1]*(i+1));
	for(int i=0;i<lim;i++)a[i]=1ll*dp[1][i]*inv[i]%mod;
	ntt(a,lim,1);
	for(int i=0;i<lim;i++)f[1][i]=a[i];
	a[0]=a[1]=1;
	for(int i=2;i<lim;i++)a[i]=0;
	ntt(a,lim,1);
	for(int i=0;i<lim;i++)val1[0][i]=val2[0][i]=1,val1[1][i]=a[i];
	for(int i=2;i<n;i++)
	{
		for(int j=0;j<lim;j++)val1[i][j]=F.reduce(val1[i-1][j]*a[j]);
	}
	for(int i=0;i<lim;i++)val2[1][i]=F.reduce(val1[n-1][i]*a[i]);
	for(int i=2;i<n;i++)
	{
		for(int j=0;j<lim;j++)val2[i][j]=F.reduce(val2[i-1][j]*val2[1][j]);
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<lim;j++)val[j]=0;
		for(int j=1;j<i;j++)
		{
			int k=i-j;
			for(int p=0;p<lim;p++)tmp[p]=F.reduce(f[j][p]*f[k][p]);
			int x=(j*k-1)%n,y=(j*k-1)/n;
			for(int p=0;p<lim;p++)tmp[p]=F.reduce(F.reduce(tmp[p]*val1[x][p])*val2[y][p]);
			for(int p=0;p<lim;p++)Add(val[p],tmp[p]);
		}
		ntt(val,lim,-1);
		for(int j=1;j<lim;j++)dp[i][j]=F.reduce(val[j-1]*fac[j-1]);
		for(int j=0;j<lim;j++)a[j]=F.reduce(dp[i][j]*inv[j]);
		ntt(a,lim,1);
		for(int j=0;j<lim;j++)f[i][j]=a[j];
	}
	for(int k=1;k<=n;k++)
	{
		int ans=0;
		for(int i=k-1;i<=k*(k-1)/2;i++)
		{
			int x=k*(k-1)/2-i,p=i-(k-1);
			if(p&1)Add(ans,mod-F.reduce(F.reduce(dp[k][i]*fac[x])*binom(k*(k-1)/2,x)));
			else Add(ans,F.reduce(F.reduce(dp[k][i]*fac[x])*binom(k*(k-1)/2,x)));
		}
		if(k>=2)ans=F.reduce(F.reduce(ans*fac[k])*((mod+1)>>1));
		ans=F.reduce(ans*inv[k*(k-1)/2]);
		cout<<ans<<'\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 40496kb

input:

10 998244353

output:

1
1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

wrong answer 3rd numbers differ - expected: '532396989', found: '1'