QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463395 | #6349. Is This FFT? | atgc | RE | 61ms | 7456kb | C++14 | 1.8kb | 2024-07-04 19:50:19 | 2024-07-04 19:50:19 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define d(i) ((i)*(i-1) >> 1)
using namespace std;
const int N = 201;
const int maxn = N*(N-1)>>1;
int n,mod,G;
int qpow(int a,int n){int ans=1;while(n){if(n&1)(ans*=a)%=mod;(a*=a)%=mod,n>>=1;}return ans;}
int inv[maxn],fac[maxn],ifac[maxn];
void init(){
fac[0]=ifac[0]=inv[1]=fac[1]=ifac[1]=1;
for(int i=2;i<maxn;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod,fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i-1]*inv[i]%mod;
}
int calG() {
vector<int>ps;
int x=mod-1;//assert(__builtin_ctz(x) >= 17);
ps.push_back(2);x>>=__builtin_ctz(x);
for(int i=3;i*i<=x;++i)if(x%i==0){ps.push_back(i);while(x%i==0)x/=i;}
if(x!=1)ps.push_back(x);
for(int G=2;;++G){
for(int p:ps)
if(qpow(G, (mod-1)/p) == 1) goto nxt;
return G;nxt:;
}
}
//cnt P that len=[j], pts = [i].
int rv[1<<15];
int f[1<<15], g[N][1<<15];
void NTT(int*a,int n){
for(int i=1;i<n;++i)if(i<(rv[i]=(rv[i>>1]|(i&1)*n)>>1))swap(a[i],a[rv[i]]);
for(int L=1;L<n;L<<=1)for(int i=0,wn=qpow(G,(mod-1)/L>>1);i<n;i+=L<<1)
for(int j=0,w=1,u,v;j<L;++j,(w*=wn)%=mod)
u=a[i|j],v=a[i|L|j],a[i|j]=(u+w*v)%mod,a[i|L|j]=(u-w*v)%mod;
}
void INTT(int*a,int n){NTT(a,n);reverse(a+1,a+n);for(int i=0,iv=qpow(n,mod-2);i<n;++i)(a[i]*=iv)%=mod;}
signed main() {
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>mod;init();G=calG();int N=1<<15;
inv[0]=1;g[1][0]=1;NTT(g[1],N);
for(int i=2;i<=n;++i) {
memset(f,0,sizeof f);
for(int li=1;li<=i-li;++li)
for(int j=0;j<N;++j)
(f[j] += g[li][j]*g[i-li][j] << ((li<<1)!=i) ) %= mod;
INTT(f,N);
memmove(f+1,f,d(i) * sizeof f[0]);
f[i-2]=0;
for(int j=i-1;j<=d(i);++j) {
(f[j] += f[j-1]*(d(i)-j+1)%mod*inv[j-1]) %= mod,
g[i][j] = f[j]*inv[j]%mod;
}
NTT(g[i],N);
cout<<(f[d(i)]*inv[d(i)]%mod*fac[i]%mod*inv[2]%mod+mod)%mod<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 61ms
memory: 7456kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Runtime Error
input:
250 998244353