QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362602#7647. 树哈希-Ofast#36 1774ms259884kbC++142.3kb2024-03-23 16:18:112024-07-04 03:30:42

Judging History

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

  • [2024-07-04 03:30:42]
  • 评测
  • 测评结果:36
  • 用时:1774ms
  • 内存:259884kb
  • [2024-03-23 16:18:11]
  • 提交

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: 1774ms
memory: 259856kb

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: 1748ms
memory: 259816kb

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: 1737ms
memory: 259816kb

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: 1744ms
memory: 259884kb

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: 1747ms
memory: 259760kb

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!