QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153699 | #6349. Is This FFT? | PhantomThreshold# | TL | 3ms | 12864kb | C++20 | 5.4kb | 2023-08-30 19:12:31 | 2023-08-30 19:12:31 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
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);
}
const int maxn = 255;
const int maxm = (1<<16)+5;
int P;
inline void add(int &a,const int &b){ a+=b; if(a>=P) a-=P; }
int pw(int x,int k)
{
int re=1;
for(;k;k>>=1,x=mult(x,x)) if(k&1)
re=mult(re,x);
return re;
}
int invi(int x){ return pw(x,P-2); }
int fac[maxm],ifac[maxm];
int C(int i,int j)
{
if(i<0||j<0||i<j) return 0;
return mult(fac[i],mult(ifac[j],ifac[i-j]));
}
int findg()
{
vector<int>pi;
int tmpP = P-1;
for(int i=2;i*i<=tmpP;i++) if(tmpP%i==0)
{
pi.push_back(i);
while(tmpP%i==0) tmpP/=i;
}
if(tmpP>1) pi.push_back(tmpP);
for(int i=2;;i++)
{
int ok=1;
for(auto k:pi) if( pw(i,(P-1)/k)==1 )
{
ok=0;
break;
}
if(ok) return i;
}
}
int g,gi[maxm];
void pre()
{
fac[0]=1; for(int i=1;i<maxm;i++) fac[i]=mult(fac[i-1],i);
ifac[maxm-1]=invi(fac[maxm-1]);
for(int i=maxm-2;i>=0;i--) ifac[i]=mult(ifac[i+1],i+1);
gi[0]=1; gi[1]=pw(g,(P-1)/(1<<16));
for(int i=2;i<=(1<<16);i++) gi[i]=mult(gi[i-1],gi[1]);
}
int id[maxm],N,ln;
void DFT(int f[],const int sig)
{
for(int i=1;i<N;i++) if(i<id[i]) swap(f[i],f[id[i]]);
for(int m=2;m<=N;m<<=1)
{
int t=m>>1,tt=(1<<16)/m;
int wn= gi[ sig==1?tt:(1<<16)-tt ];
for(int j=0;j<N;j+=m)
{
int ww=1;
for(int i=0;i<t;i++)
{
int tx=f[j+i], ty=mult(f[j+i+t],ww);
f[j+i]= (tx+ty);
if(f[j+i]>=P) f[j+i]-=P;
f[j+i+t]= (tx-ty);
if(f[j+i+t]<0) f[j+i+t]+=P;
ww= mult(ww,wn);
}
}
}
if(sig==-1)
{
int iN= mult( ifac[N],fac[N-1] );
for(int i=0;i<N;i++) f[i]=mult(f[i],iN);
}
}
int n;
int e[maxn];
int f[maxn][maxm];
int a[maxn][maxm],b[maxn][maxm],c[maxm],ret[maxm];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> P;
BA = Barrett(P);
g = findg();
pre();
for(int i=1;i<=n;i++) e[i]=i*(i-1)/2;
N=1,ln=0;
f[0][0]=1;
f[1][0]=1;
f[2][1]=1;
for(int i=3;i<=n;i++)
{
int flag=0;
if(N<=e[i])
{
flag=1;
while(N<=e[i]) N<<=1,ln++;
}
if(flag)
{
for(int s=1;s<N;s++) id[s]=id[s>>1]>>1|(s&1)<<(ln-1);
for(int j=1;j<i;j++)
{
int sum=0;
for(int x=0;x<=e[j];x++)
{
add(sum,f[j][x]);
a[j][x]= mult( mult( mult( mult( sum, ifac[j] ), ifac[x] ), ifac[e[j]-x] ), 1+(j!=1) );
if(x>0) b[j][x]= mult( mult( mult( mult( f[j][x], ifac[j] ), ifac[x-1] ), ifac[e[j]-x] ), 1+(j!=1) );
else b[j][x]= 0;
}
for(int x=e[j]+1;x<N;x++) a[j][x]=b[j][x]=0;
// for(int x=0;x<2;x++) a[j][x]=1;
// for(int x=0;x<2;x++) b[j][x]=2;
DFT(a[j],1);
DFT(b[j],1);
// for(int x=0;x<N;x++) c[x]=mult(a[j][x],b[j][x]);
// DFT(c,-1);
}
}
else
{
for(int j=i-1;j<i;j++)
{
int sum=0;
for(int x=0;x<=e[j];x++)
{
add(sum,f[j][x]);
a[j][x]= mult( mult( mult( mult( sum, ifac[j] ), ifac[x] ), ifac[e[j]-x] ), 1+(j!=1) );
if(x>0) b[j][x]= mult( mult( mult( mult( f[j][x], ifac[j] ), ifac[x-1] ), ifac[e[j]-x] ), 1+(j!=1) );
else b[j][x]= 0;
}
for(int x=e[j]+1;x<N;x++) a[j][x]=b[j][x]=0;
// for(int x=0;x<2;x++) a[j][x]=1;
// for(int x=0;x<2;x++) b[j][x]=2;
DFT(a[j],1);
DFT(b[j],1);
// for(int x=0;x<N;x++) c[x]=mult(a[j][x],b[j][x]);
// DFT(c,-1);
}
}
for(int u=1;u<i;u++)
{
int v=i-u;
for(int x=0;x<N;x++) ret[x]= mult( a[u][x], b[v][x] );
DFT(ret, -1);
ret[0]=0;
for(int x=1;x<=e[u]+e[v];x++)
{
ret[x]= mult( mult( mult(ret[x],fac[u+v]), fac[x-1]), fac[e[u]+e[v]-x] );
}
int sum=0;
for(int x=0;x+u*v-1<=e[i];x++)
{
add(f[i][x], mult( mult(sum,fac[e[i]-x]), ifac[e[i]-x-u*v+1]) );
add(sum,ret[x]);
}
}
// cerr<<i<<" : "<<clock()<<endl;
}
/*
1,0 + 2,1
1*1 *6
for(int i=3;i<=n;i++)
{
for(int j=1;j<i;j++)
{
// f j,x (+k) * f i-j,y
for(int x=j-1;x<=e[j];x++)
{
for(int y=max(1,i-j-1);y<=e[i-j];y++)
{
for(int k=0;x+k<=e[j];k++)
{
u32 cc=
mult( mult( mult( f[j][x],f[i-j][y] ), C(i,j) ) , mult( C(x+k+y-1,y-1) ,C(e[j]-x-k+e[i-j]-y,e[i-j]-y) ) );
if(j!=1) cc=mult(cc,2);
if(i-j!=1) cc=mult(cc,2);
//x+k+y
for(int x2=x+y+k+1;x2<=e[i];x2++)
{
add(f[i][x2], mult( mult(cc,C(e[i]-x2,j*(i-j)-1)),fac[j*(i-j)-1] ));
}
}
}
}
}
}
*/
/*
f[i][x] (+k)
f[j][y]
f[i][x]/i!/(x+k)!/(e[i]-x-k)!*(1+[i!=1]) *f[j][y]/j!/(y-1)!/(e[j]-y)!*(1+(j!=1))
(i+j)! (x+k+y-1)! (e[i]+e[j]-x-y-k)!
g[i+j][x+k+y]
g[x]->g[y]
x(+c)=y
g[x]*C(E-y,e-1)*(e-1)!
= g[x] * (E-y)! / (E-y-e+1)!
*C(e[i+j]-x-y-k-c,i*j-1) *(i*j-1)!
*/
for(int i=2;i<=n;i++)
{
int ans=0;
for(int j=i-1;j<=e[i];j++) add(ans,f[i][j]);
//cout<<ans<<' ';
cout<<mult( ans , ifac[e[i]] )<<endl;
}
return 0;
}
/*
10 998244353
1 1
6 1
528 532396989
1627200 328786831
165386946 443364983
584100363 567813846
223285012 34567523
931131059 466373946
157453919 474334062
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 12864kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
250 998244353