P5270 无论怎样神树大人都会删库跑路。

好复杂啊(代码太乱了),差点搞我几个小时,还好讨论区有警示后人:不能直接用 109+710^9+7(会有精度误差)。

首先问题转化,对于每一个询问要求的位置,判断当前位置的和 TT 长度相同的后缀每一个出现过的数出现次数相同。

大体思路就是设计一个哈希,需要只判断数字出现个数相同,但是不需要对应位置相同。

然后一个比较好的就是:

∑(109+7)ai\sum (10^9+7)^{a_i}

这种大的数字一般用 unsigned long long 自然溢出。

这道题中 QQ 很大,怎么办?我们发现会重复这 mm 个操作,所以可以计算循环节。

然后代码的思路是先从 11 计算,然后我们可以先找到 szsz 大于 TT 的第一个点,然后从这个点开始进行 mm 次操作,然后记录每一次操作的答案为循环节。

最后统计答案需要去除 sz<Tsz<T 的部分,还要加上最后不在一整个循环节内的部分。

还要提醒,注意细节,我写代码 2020 分钟,调了至少 4040 分钟,写的输出调试差不多 2020 行。

代码

C++
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,T,q,m;
int want=0;
int a[100010];
int len[100010],h[100010];
int l[100010],vis[100010];
vector<int>x[100010];
int r[100010],qq[100010];
int num=0,ans=0;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>T>>q;
	h[0]=1;
	for(int i=1;i<=100000;i++)h[i]=(h[i-1]*(100000007));
	for(int i=1;i<=T;i++){
		cin>>a[i];
		want+=h[a[i]];
	}
	for(int i=1;i<=n;i++){
		cin>>len[i];
		for(int j=1;j<=len[i];j++){
			int c;
			cin>>c;
			x[i].push_back(c);
		}
	}
	int sz=0,p=1;
	int res=0;
	int tot=0;
	int t=0;
	
	cin>>m;
	for(int i=1;i<=m;i++)cin>>qq[i];
	for(int i=1,j=1;i<=q;i++){
		int now=qq[j];
		sz+=len[now];
		int cnt=0;
		while(cnt<len[now]){
			if(vis[p])res-=h[l[p]];
			vis[p]=1;
			l[p]=x[now][cnt];
			res+=h[l[p]];
			if(p==T)p=1;
			else p++;
			cnt++;
			if(cnt>=len[now])break;
		}
		if(sz>=T){
			r[(j-1)%(m)+1]=(res==want);
			num+=(res==want);
			tot++;
			if(tot==m)break;
		}else{
			t++;
		}
		if(j==m)j=1;
		else j++;
	}
	
	if(q==t)cout<<0<<endl;
	else{
		q-=t;
		ans=((int)q/m)*num;
		q=q-(int)(q/m)*m;
		for(int i=1,j=(t)%m+1;i<=q;i++){
			ans+=r[j];
			if(j==m)j=1;
			else j++;
		}
		cout<<ans<<endl;
	}
	
	return 0;
}