QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362598 | #7647. 树哈希 | -Ofast# | 36 | 1733ms | 261936kb | C++14 | 2.3kb | 2024-03-23 16:17:16 | 2024-07-04 03:30:37 |
Judging History
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<=18;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";
}
for(int i=19;i<=100;i++)cout<<0<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 36
Acceptable Answer
Test #1:
score: 36
Acceptable Answer
time: 1713ms
memory: 260884kb
input:
100 910342260 935929297
output:
910342260 816177711 569226551 514707635 267406725 391906453 250727611 208481307 81485772 23235693 216730633 285646992 175230876 274553119 174038157 203318484 775234565 322891510 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.360 You got 36 pts!
Test #2:
score: 36
Acceptable Answer
time: 1703ms
memory: 261564kb
input:
100 222959056 947643239
output:
222959056 358599927 365062242 287299555 872152310 785181552 689517811 751458049 373969559 887125628 238000283 265869067 862846962 717459206 118380127 903859172 38731072 220551290 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
points 0.360 You got 36 pts!
Test #3:
score: 36
Acceptable Answer
time: 1702ms
memory: 261936kb
input:
100 135352674 235854343
output:
135352674 116843515 129198122 128256418 202034449 101078108 134511179 26177395 38146936 177689345 171471260 220203615 2725266 54489245 202150371 51581049 9159057 174134120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.360 You got 36 pts!
Test #4:
score: 36
Acceptable Answer
time: 1727ms
memory: 261204kb
input:
100 538608644 566215339
output:
538608644 365236991 134179965 39370099 416828003 17910602 226317362 529379896 407121368 81806097 249408176 336758120 296361261 35236747 429449088 328368699 409154256 418665686 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.360 You got 36 pts!
Test #5:
score: 36
Acceptable Answer
time: 1733ms
memory: 261576kb
input:
100 56831820 281897771
output:
56831820 213573518 5338712 114481529 104176011 222091299 258318286 168492731 248042852 279768543 163273831 250332871 125456436 55441194 94771937 85241933 265069860 227132810 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.360 You got 36 pts!