QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#292248 | #7647. 树哈希 | CharlieVinnie | 0 | 0ms | 0kb | C++17 | 3.4kb | 2023-12-27 22:02:57 | 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