QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#362590#7647. 树哈希-Ofast#0 0ms0kbC++142.3kb2024-03-23 16:16:022024-07-04 03:30:36

Judging History

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

  • [2024-07-04 03:30:36]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-03-23 16:16:02]
  • 提交

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;
}



详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

100 910342260 935929297

output:


result: