QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362590 | #7647. 树哈希 | -Ofast# | 0 | 0ms | 0kb | C++14 | 2.3kb | 2024-03-23 16:16:02 | 2024-07-04 03:30:36 |
answer
#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define mt make_tuple
#define int long long
#define fin(File) freopen(File".in","r",stdin)
#define fout(File) freopen(File".out","w",stdout)
using namespace std;
int n,q,pw[105],mod;
int qpow(int a,int b){
a%=mod;int res=1;
while(b){
if(b&1)res=(res*a)%mod;
a=(a*a)%mod;b>>=1;
}return res;
}
int cnt=1;
struct tree{
signed son[22],sz,big;
}T[10000005];
int l[105],r[105],fac[105],C[105][105],ifac[105];
int dfs(int u){
//cout<<u<<" ";
int ans=T[u].big,b=T[u].big-1,tot=0;
//cout<<"node: "<<u<<" "<<ans<<"\n";
for(int i=1;i<=T[u].sz;i++){
tot++;
int v=T[u].son[i];
//cout<<"son: "<<u<<" "<<v<<" "<<C[b][T[v].big]<<"\n";
ans*=dfs(v);ans%=mod;
ans*=C[b][T[v].big];ans%=mod;b-=T[v].big;
if(v!=T[u].son[i+1]){
//cout<<"tot: "<<tot<<" "<<ifac[tot]<<"\n";
ans*=ifac[tot];ans%=mod;
tot=0;
}
}
//cout<<"ret: "<<u<<" "<<ans<<"\n";
return ans;
}
void cont(int u,set <int> &S){
if(S.count(u))return;
S.insert(u);
for(int i=1;i<=T[u].sz;i++){
cont(T[u].son[i],S);
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>q>>mod;
l[1]=1;r[1]=1;pw[1]=q;fac[1]=1;ifac[1]=1;T[1].big=1;
cout<<q<<"\n";
for(int i=0;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=2;i<=n;i++){
l[i]=r[i-1]+1;
for(int j=1;j<i;j++){
for(int k=1;j+k<=i;k++){
for(int tot=1;j+k*tot<=i;tot++){
if(j+k*tot!=i)continue;
for(int pid=l[j];pid<=r[j];pid++){
for(int tid=l[k];tid<=r[k];tid++){
if(T[pid].son[T[pid].sz]<=tid&&T[pid].sz>0)continue;
++cnt;T[cnt].sz=T[pid].sz+tot;
memcpy(T[cnt].son,T[pid].son,sizeof(T[cnt].son));
for(int pos=T[pid].sz+1;pos<=T[cnt].sz;pos++)
T[cnt].son[pos]=tid;
}
}
}
}
}
pw[i]=pw[i-1]*q%mod;
fac[i]=fac[i-1]*i%mod;
ifac[i]=qpow(fac[i],mod-2);
r[i]=cnt;
int ans=0;
int inv=qpow(i,mod-2);
set <int> S;
for(int j=l[i];j<=r[i];j++){
S.clear();
T[j].big=i;cont(j,S);int t=dfs(j);
//cout<<"tree: "<<(t=dfs(j));cout<<"\n";
//cout<<"count: "<<S.size()<<"\n\n";
ans+=(t*inv)%mod*pw[S.size()];ans%=mod;
}
cout<<ans<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
100 910342260 935929297