QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#450530#6349. Is This FFT?fireinceWA 0ms36336kbC++144.4kb2024-06-22 15:12:372024-06-22 15:12:37

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 15:12:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:36336kb
  • [2024-06-22 15:12:37]
  • 提交

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=1;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: 0
Wrong Answer
time: 0ms
memory: 36336kb

input:

10 998244353

output:

1
1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

wrong answer 3rd numbers differ - expected: '532396989', found: '1'