QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197814 | #6349. Is This FFT? | zhouhuanyi | ML | 0ms | 28484kb | C++23 | 4.7kb | 2023-10-02 20:15:31 | 2023-10-02 20:15:31 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 250
#define M 62500
#define K 32768
#define W 6935
#define Q 16
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using namespace std;
struct Barrett {u64 b, m;Barrett() : b(), m() {}Barrett(u64 _b) : b(_b), m(-1ULL / _b) {}u32 reduce(u64 x) {u64 q = (u64)((u128(m) * x) >> 64), r = x - q * b;return r - b * (r >= b);}} BA;
u32 mult(u32 x, u32 y) {return BA.reduce((u64)x * y);}
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,g,len,length,ans,st[N+1],leng,rev[K+1],S[N+1],F[W+1][K+1],fac[M+1],invfac[M+1],inv[M+1],A[K+1],B[K+1],dp[N+1][M+1],DP[N+1][K+1],wn[Q+1][K+1],wn2[Q+1][K+1],snum[M+1],pw[N+1][M+1],pw2[N+1][M+1],num[K+1],mod;
bool used[M+1];
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
void Adder2(int &x,int d)
{
x+=d;
if (x<0) x+=mod;
return;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
int fast_pow(int a,int b)
{
int res=1,mul=a;
while (b)
{
if (b&1) res=mult(res,mul);
mul=mult(mul,mul),b>>=1;
}
return res;
}
int C(int x,int y)
{
if (x<y) return 0;
return mult(mult(fac[x],invfac[y]),invfac[x-y]);
}
void NTT(int limit,int *s,int type)
{
int s1,s2;
for (int i=0;i<limit;++i)
if (rev[i]>i)
swap(s[i],s[rev[i]]);
if (type==1)
{
for (int i=2;i<=limit;i<<=1)
for (int j=0;j+i-1<limit;j+=i)
for (int k=j;k<j+(i>>1);++k)
s1=s[k],s2=mult(s[k+(i>>1)],wn[num[i]][k-j]),s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
}
else
{
for (int i=2;i<=limit;i<<=1)
for (int j=0;j+i-1<limit;j+=i)
for (int k=j;k<j+(i>>1);++k)
s1=s[k],s2=mult(s[k+(i>>1)],wn2[num[i]][k-j]),s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
s1=fast_pow(limit,mod-2);
for (int i=0;i<=limit;++i) s[i]=mult(s[i],s1);
}
return;
}
int main()
{
int x,w,limit=1;
bool op;
n=read(),mod=read(),x=mod-1,fac[0]=1,BA=Barrett(mod);
for (int i=1;i<=M;++i) fac[i]=mult(fac[i-1],i);
invfac[M]=fast_pow(fac[M],mod-2);
for (int i=M-1;i>=0;--i) invfac[i]=mult(invfac[i+1],i+1);
for (int i=1;i<=M;++i) inv[i]=mult(fac[i-1],invfac[i]);
for (int i=2;i*i<=(mod-1);++i)
if (x%i==0)
{
while (x%i==0) x/=i;
st[++leng]=i;
}
if (x!=1) st[++leng]=x;
while (1)
{
g++,op=1;
for (int i=1;i<=leng;++i)
if (fast_pow(g,(mod-1)/st[i])==1)
op=0;
if (op) break;
}
for (int i=2;i<=K;i<<=1)
{
num[i]=++length,w=fast_pow(g,(mod-1)/i);
for (int j=0,res=1;j<(i>>1);++j,res=mult(res,w)) wn[num[i]][j]=res;
w=fast_pow(g,(mod-1)/i*(i-1));
for (int j=0,res=1;j<(i>>1);++j,res=mult(res,w)) wn2[num[i]][j]=res;
}
for (int i=1;i<=n;++i) S[i]=S[i-1]+i-1;
while (limit<=S[n]) limit<<=1;
for (int i=1;i<limit;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?limit>>1:0);
dp[1][0]=DP[1][0]=1,NTT(limit,DP[1],1);
A[0]=1,A[1]=MD2(-1),NTT(limit,A,1);
B[1]=1,NTT(limit,B,1);
for (int i=2;i<=n;++i)
for (int j=0;j<=limit;++j)
DP[i][j]=DP[1][j];
for (int i=1;i<=n;++i)
for (int j=1;i+j<=n;++j)
used[i*j]=1;
for (int i=0;i<=limit;++i)
{
pw[0][i]=pw2[0][i]=1;
for (int j=1;j<=n;++j) pw[j][i]=1ll*pw[j-1][i]*A[i]%mod;
for (int j=1;j<=n;++j) pw2[j][i]=1ll*pw2[j-1][i]*pw[n][i]%mod;
}
for (int i=1;i<=n*n;++i)
if (used[i])
{
snum[i]=++len;
for (int j=0;j<=limit;++j) F[snum[i]][j]=mult(B[j],mult(pw[(i-1)%n][j],pw2[(i-1)/n][j]));
}
for (int i=2;i<=n;++i)
{
for (int j=1;j<=i-1;++j)
{
for (int k=0;k+7<=limit;k+=8)
{
Adder(DP[i][k],mult(mult(DP[j][k],DP[i-j][k]),F[snum[j*(i-j)]][k]));
Adder(DP[i][k+1],mult(mult(DP[j][k+1],DP[i-j][k+1]),F[snum[j*(i-j)]][k+1]));
Adder(DP[i][k+2],mult(mult(DP[j][k+2],DP[i-j][k+2]),F[snum[j*(i-j)]][k+2]));
Adder(DP[i][k+3],mult(mult(DP[j][k+3],DP[i-j][k+3]),F[snum[j*(i-j)]][k+3]));
Adder(DP[i][k+4],mult(mult(DP[j][k+4],DP[i-j][k+4]),F[snum[j*(i-j)]][k+4]));
Adder(DP[i][k+5],mult(mult(DP[j][k+5],DP[i-j][k+5]),F[snum[j*(i-j)]][k+5]));
Adder(DP[i][k+6],mult(mult(DP[j][k+6],DP[i-j][k+6]),F[snum[j*(i-j)]][k+6]));
Adder(DP[i][k+7],mult(mult(DP[j][k+7],DP[i-j][k+7]),F[snum[j*(i-j)]][k+7]));
}
Adder(DP[i][limit],mult(mult(DP[j][limit],DP[i-j][limit]),F[snum[j*(i-j)]][limit]));
}
NTT(limit,DP[i],-1);
for (int j=1;j<=S[i];++j) dp[i][j]=mult(DP[i][j],inv[j]);
for (int j=0;j<=limit;++j) DP[i][j]=0;
for (int j=1;j<=S[i];++j) DP[i][j]=dp[i][j];
NTT(limit,DP[i],1);
}
for (int i=2;i<=n;++i)
{
ans=0;
for (int j=1;j<=S[i];++j) Adder(ans,dp[i][j]);
printf("%lld\n",1ll*ans*fac[i]%mod*inv[2]%mod);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 28484kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Memory Limit Exceeded
input:
250 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062 289137877 768923227 177538883 440227465 101981224 874960215 35275208 664066979 334444870 46651494 799130693 122319095 913072242 44703442 965640306 52873544 461938281 263838691 777326453 356621754 560569747 812581766 46147702 12...