QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#292248#7647. 树哈希CharlieVinnie0 0ms0kbC++173.4kb2023-12-27 22:02:572023-12-27 22:02:57

Judging History

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

  • [2023-12-27 22:02:57]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-12-27 22:02:57]
  • 提交

answer

// #define _GLIBCXX_DEBUG
#include "bits/stdc++.h"
#undef DEBUG
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
constexpr int N=105;
int mod;
inline int qpow(int x,int y){int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
inline int ID(int x) { return x&1?mod-1:1; }
class Poly : public vector<int>{
public:
    using vector<int>::vector;
    friend Poly& operator+= (Poly& A,const Poly& B){
        if(A.size()<B.size()) A.resize(B.size());
        for(auto i=0u;i<B.size();i++) A[i]=(A[i]+B[i])%mod;
        return A;
    }
    friend Poly& operator-= (Poly& A,const Poly& B){
        if(A.size()<B.size()) A.resize(B.size());
        for(auto i=0u;i<B.size();i++) A[i]=(A[i]-B[i]+mod)%mod;
        return A;
    }
    friend Poly& operator*= (Poly& A,const Poly& B){
        Poly C(A.size()+B.size()-1);
        for(auto i=0u;i<A.size();i++) for(auto j=0u;j<B.size();j++) C[i+j]=(C[i+j]+1ll*A[i]*B[j])%mod;
        return A=C;
    }
    friend Poly operator+ (Poly A,const Poly& B) { return A+=B; }
    friend Poly operator- (Poly A,const Poly& B) { return A-=B; }
    friend Poly operator* (Poly A,const Poly& B) { return A*=B; }
};
Poly pow(Poly A,int k){
    Poly res{1}; while(k) { if(k&1) res*=A;; A*=A; k>>=1; }; return res;
}
int n,q,f[N],cp[N],ci[N],inv[N];
int solve(int D){
    debuga(f,1,D);
    int ans=1ll*qpow(q,f[1])*qpow(f[1],f[1]-1)%mod*cp[n]%mod;
    For(i,2,D) if(f[i]) {
        Poly A{1};
        For(p,1,i-1){
            Poly tmp(i+1); For(j,0,i/p) tmp[j*p]=qpow(ci[j],p);
            A*=pow(tmp,f[p]); //A.resize(i+1);
        }
        Poly B=(A-Poly{1})*Poly{q};
        Poly G,tmp{1}; For(j,1,i){
            tmp*=B;
            G+=tmp*Poly{int(1ll*ID(j-1)*inv[j]%mod)};
        }
        debug(G,1ll*G[i]*cp[n]%mod);
        int res=0;
        For(k,1,f[i]){
            res=(res+1ll*qpow(G[i],k)*(k==f[i]?1:1ll*k*qpow(f[i],f[i]-k-1)%mod)%mod*cp[f[i]]%mod*ci[k]%mod*ci[f[i]-k]%mod*qpow(q,f[i]-k)%mod)%mod;
        }
        ans=1ll*ans*res%mod;
        debug(res,i,ans);
    }
    debug(ans);
    For(i,1,D) ans=1ll*ans*ci[f[i]]%mod;
    debug(ans);
    return ans;
}
int dfs(int dep,int rest){
    if(rest==0) return solve(dep-1);
    if(rest<dep) return 0;
    int res=0; For(i,(dep==1),rest/dep) f[dep]=i,res=(res+dfs(dep+1,rest-i*dep))%mod;
    return res;
}
void Init(){
    cp[0]=1; For(i,1,n) cp[i]=1ll*cp[i-1]*i%mod;
    ci[n]=qpow(cp[n],mod-2); Rev(i,n-1,0) ci[i]=1ll*ci[i+1]*(i+1)%mod;
    For(i,1,n) inv[i]=1ll*ci[i]*cp[i-1]%mod;
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    // cin>>n>>q>>mod;
    // n=30; q=2; mod=998244353;
    // Init(); cout<<1ll*dfs(1,n)*inv[n]%mod<<'\n'; //For(i,1,n) cout<<dfs(1,i)<<'\n';
    cin>>n>>q>>mod; Init();
    int B=27;
    For(i,1,B) cout<<dfs(1,i)<<'\n';
    For(i,B+1,100) cout<<0<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: December 27 Wed, 16 : 40 : 53

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

100 910342260 935929297

output:


result: