QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#451096 | #6349. Is This FFT? | EXODUS | WA | 15ms | 11108kb | C++17 | 4.4kb | 2024-06-22 21:01:27 | 2024-06-22 21:01:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define Debug(...) fprintf(stderr,__VA_ARGS__)
#define Exit(p) fprintf(stderr,"[exit]: at breakpoint %d\n",p),exit(0);
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)
template<typename T>void read(T &x){x=0;T flg=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x*=flg;}
template<typename T,typename... Args>void read(T &x,Args &...args){read(x),read(args...);}
template<typename T>void cmax(T& x,T y){x=max(x,y);}
template<typename T,typename... Args>void cmax(T& x,T y,Args ...args){cmax(x,y);cmax(x,args...);}
template<typename T>void cmin(T& x,T y){x=min(x,y);}
template<typename T,typename... Args>void cmin(T& x,T y,Args ...args){cmin(x,y);cmin(x,args...);}
template<typename T,typename U>ostream &operator<<(ostream &os,const pair<T,U>&x){return os<<"("<<x.first<<","<<x.second<< ")"; };
template<typename T>ostream &operator<<(ostream &os,const vector<T> &as){const int sz=as.size();os<<"[";for(int i=0;i<sz;++i){if(i>=256){os<<",...";break;}if(i>0){os<<",";}os<<as[i];}return os<<"]";}
bool membg=0;
constexpr int N=257;
int n,groot,mod,fac[N*N],ifac[N*N],rev[N*N];
int f[N][N*N],h[N][N*N];
int g[N*N];
struct Barret{
ull p,m;
Barret(ull _p=2):p(_p),m(((i128)1<<64)/_p){}
ull mod(ull x){
ull q=((i128)x*m)>>64;
x-=q*p;
return x>=p?x-p:x;
}
}M;
bool memed=0;
int qpow(int x,int y){
int res=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1)res=(ll)res*x%mod;
return res;
}
typedef unsigned long long ull;
void ntt_transfer(std::vector<int>& f, int len, const int g, int tp) {
f.resize(len);
for(int i = 0;i < (int)f.size();i++)
if(i<rev[i])
swap(f[i],f[rev[i]]);
std::vector<ull> temp(f.size());
for (int i = 0; i < (int)f.size(); i++)
temp[i] = f[i];
for (int mid = 1; mid < (int)f.size(); mid <<= 1) {
int len = (mid << 1);
int cur = qpow(tp ? g : qpow(g, mod - 2), (mod - 1) / len);
for (int l = 0; l < (int)f.size(); l += len) {
ull buf = 1;
for (int k = l; k < l + mid; k++) {
ull w1 = temp[k], w2 = temp[k + mid] * buf % mod;
temp[k] = w1 + w2; temp[k + mid] = w1 + mod - w2;
buf = buf * cur % mod;
}
}
}
for (int i = 0; i < (int)f.size(); i++)
f[i] = temp[i] % mod;
if (!tp) {
auto inv = qpow(f.size(), mod - 2);
for (int i = 0; i < (int)f.size(); i++)
f[i] = (ll) f[i] * inv % mod;
}
}
int check(int w){
int t=mod-1;
for(int i=2;i*i<=t;i++){
if(t%i==0){
while(t%i==0)t/=i;
if(qpow(w,(mod-1)/i)==1)
return 0;
}
}
if(t>1)
if(qpow(w,(mod-1)/t)==1)
return 0;
return 1;
}
void getgen(){
for(int i=2;;i++){
if(check(i)){
groot=i;
return;
}
}
}
int binom(int n,int m){
return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void solve(){
read(n,mod);
M=Barret(mod);
int inv2=(mod+1)>>1;
getgen();
int len=1;
while(len<=n*(n-1)/2)len<<=1;
int cnt=0;
while(len!=(1<<cnt))cnt++;
for(int i=1;i<len;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));
for(int i=fac[0]=ifac[0]=1;i<N*N;i++)
fac[i]=(ll)fac[i-1]*i%mod,ifac[i]=qpow(fac[i],mod-2);
f[1][0]=1;
vector<int>G(len),H(len);
int tot=0;
for(int i=1;i<=n;i++){
memset(g,0,sizeof(g));
for(int k=1;k<i;k++)
for(int j=0;j<len;j++)
g[j]=M.mod(g[j]+M.mod((ull)h[k][j]*h[i-k][j])*binom(i,k));
G.assign(g,g+len);
// cout<<G<<'\n';
int tbg=clock();
ntt_transfer(G,len,groot,0);
tot+=clock()-tbg;
for(int j=1;j<=i*(i-1)/2;j++)
f[i][j]=M.mod(M.mod((ll)G[j-1]*fac[j-1])*inv2);
for(int j=1;j<=i*(i-1)/2;j++)
f[i][j]=M.mod(f[i][j]+(ll)f[i][j-1]*(i*(i-1)/2-j+1));
for(int j=0;j<=i*(i-1)/2;j++)
h[i][j]=M.mod((ll)(1+(i!=1))*f[i][j]*ifac[j]);
H.assign(h[i],h[i]+len);
tbg=clock();
ntt_transfer(H,len,groot,1);
tot+=tbg-clock();
// cout<<H<<'\n';
for(int j=0;j<len;j++)
h[i][j]=H[j];
}
for(int i=1;i<=n;i++)
printf("%lld\n",(ll)f[i][i*(i-1)/2]*ifac[i*(i-1)/2]%mod);
return;
}
int main(){
Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
int timbg=clock();
int T=1;
while(T--)solve();
int timed=clock();
Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
fflush(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 11108kb
input:
10 998244353
output:
1 1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
wrong answer 3rd numbers differ - expected: '532396989', found: '1'