QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#450936 | #6349. Is This FFT? | Harry27182 | WA | 0ms | 40496kb | C++14 | 3.5kb | 2024-06-22 19:41:31 | 2024-06-22 19:41:31 |
Judging History
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'