QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#450532 | #6349. Is This FFT? | fireince | WA | 7736ms | 551608kb | C++14 | 4.4kb | 2024-06-22 15:13:25 | 2024-06-22 15:13:25 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<array>
#define endl '\n'
using namespace std;
using ll = long long;
using pi2 = array<int,2>;
using pi3 = array<int,3>;
const int N=250,M=1<<17,FN=M;
struct FastMod{
using ull=unsigned long long;
using L=__int128;
ull b,m;
void set(ull b){
this->b=b,this->m=ull((L(1)<<64)/b);
}
ull reduce(ull a) const{
ull q=(ull)((L(m)*a)>>64),r=a-q*b;
return r>=b?r-b:r;
}
};
template<typename T>
T operator%(T x,const FastMod& Mod){
return Mod.reduce(x);
}
template<typename T>
T& operator%=(T& x,const FastMod& Mod){
return x=Mod.reduce(x);
}
FastMod P;
int P_;
int n;
ll fpow(ll a,ll b){
return b==0?1:(b&1?a*fpow(a*a%P,b/2)%P:fpow(a*a%P,b/2));
}
ll fact[FN],inv_fact[FN];
void init_fact(int n){
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= n; i++)
fact[i] = 1ll*fact[i - 1] * i % P;
inv_fact[n] = fpow(fact[n], P_ - 2);
for (int i = n - 1; i >= 1; i--)
inv_fact[i] = 1ll*inv_fact[i + 1] * (i + 1) % P;
}
ll binom(ll n,ll k){
if(n<k)return 0;
return 1ll*fact[n]*inv_fact[k]%P*inv_fact[n-k]%P;
}
void mod(ll& x){
if(x>=P_)x-=P_;
}
void mod(int& x){
if(x>=P_)x-=P_;
}
int m;
ll res[N];
int root;
namespace NTT{
void mod(int& x){
if(x>=P_)x-=P_;
}
int W[M],IW[M];
int G,IG;
void init(int n){
for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
for(int i=0,wn=fpow(G,(P_-1)/l),iwn=fpow(IG,(P_-1)/l),w=1,iw=1;i<mid;i++)
W[mid+i]=w,IW[mid+i]=iw,w=((ll)w*wn)%P,iw=((ll)iw*iwn)%P;
}
void dft(int* f,int n){
for(int l=n,mid=l>>1;l>=2;l>>=1,mid>>=1)
for(int p=0;p<n;p+=l)
for(int i=0,x,y;i<mid;i++)
x=f[p+i],y=f[p+mid+i],mod(f[p+i]+=y),f[p+mid+i]=(ll)W[mid+i]*(P_+x-y)%P;
}
void idft(int* f,int n){
for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
for(int p=0;p<n;p+=l)
for(int i=0,x,y;i<mid;i++)
x=f[p+i],y=(ll)f[p+mid+i]*IW[mid+i]%P,mod(f[p+i]+=y),mod(f[p+i+mid]=P_+x-y);
for(int i=0,invn=fpow(n,P_-2);i<n;i++)f[i]=(ll)f[i]*invn%P;
}
int gt(int l){
int n=1;
while(n<l)n<<=1;
return n;
}
};
ll f[N][M],g[N][M];
int tmp[M],tmp2[M];
int gp[N][M];
ll WP[M];
int tr[M];
void init_butterfly(int n){
int w=__lg(n);
for(int i=0;i<n;i++)tr[i]=tr[i>>1]>>1|((i&1)<<w-1);
ll wn=fpow(root,(P_-1)/n);
WP[0]=1;
for(int i=1;i<n;i++)WP[i]=WP[i-1]*wn%P;
}
void dp(){
f[1][0]=g[1][0]=res[1]=1;
int ml=NTT::gt(m);
init_butterfly(ml);
for(int j=0;j<=0;j++)gp[1][j]=g[1][j]*inv_fact[1*(1-1)/2-j]%P*inv_fact[j]%P;
NTT::dft(gp[1],ml);
for(int i=2;i<=n;i++){
int im=i*(i-1)/2-(i-1);
fill(tmp2,tmp2+ml,0);
for(int k=1;k<i;k++){
int x=k*(k-1)/2,y=(i-k)*(i-k-1)/2,z=k*(i-k)-1;
ll bk=binom(i,k);
for(int j=0;j<ml;j++)tmp[j]=(ll)gp[k][j]%P*gp[i-k][j]%P*bk%P;
for(int j=0;j<ml;j++)tmp[j]=tmp[j]*WP[tr[j]*z%ml]%P;
for(int j=0;j<ml;j++)
mod(tmp2[j]+=tmp[j]);
}
NTT::idft(tmp2,ml);
for(int j=0;j<=im;j++)
f[i][j]=(ll)tmp2[j]*fact[i*(i-1)/2-1-j]%P*fact[j]%P;
g[i][im]=f[i][im];
for(int j=im-1;j>=0;j--)mod(g[i][j]=g[i][j+1]+f[i][j]);
for(int j=0;j<=im;j++)gp[i][j]=g[i][j]*inv_fact[i*(i-1)/2-j]%P*inv_fact[j]%P;
NTT::dft(gp[i],ml);
for(int j=0;j<=im;j++)mod(res[i]+=f[i][j]);
res[i]=res[i]*fpow(2,P_-2)%P;
}
}
void findrt(){
int t=P_-1;
vector<int> vs;
for(int i=2;i<=t&&i*i<=P_;i++){
if(t%i==0){
vs.push_back(i);
while(t%i==0)t/=i;
}
}
if(t!=1)vs.push_back(t);
for(int i=2;i<=P_;i++){
bool flag=true;
for(int j:vs){
if(fpow(i,(P_-1)/j)==1){
flag=false;
break;
}
}
if(flag)return root=i,void();
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>P_;
P.set(P_);
findrt();
NTT::G=root,NTT::IG=fpow(root,P_-2);
m=n*(n-1)/2;
init_fact(m);
NTT::init(NTT::gt(m));
dp();
for(int i=2;i<=n;i++)cout<<res[i]*inv_fact[i*(i-1)/2]%P<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38612kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Wrong Answer
time: 7736ms
memory: 551608kb
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: '299444202'