QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463396 | #6349. Is This FFT? | atgc | WA | 3001ms | 68672kb | C++14 | 1.8kb | 2024-07-04 19:50:45 | 2024-07-04 19:50:46 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define d(i) ((i)*(i-1) >> 1)
using namespace std;
const int N = 250;
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: 7684kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Wrong Answer
time: 3001ms
memory: 68672kb
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...
result:
wrong answer 249th numbers differ - expected: '107476421', found: '572574591'