不开int见祖宗?!
查看原帖
不开int见祖宗?!
362627
frank15楼主2021/4/3 12:55

写哈希时哈希值开int就能过,ll就会wa掉,求助大佬讲解

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define ll long long
#define P pair<ll,ll>
using namespace std;
const ll base=233,mod=212370440130137957ll,maxn=1e5+5;
ll n,t,Q,m;
ll now,k,lenx,ANS;
ll pow[maxn],ans[maxn];
ll s[maxn],a[maxn],r[maxn],len[maxn];
deque<P> q;
struct node{
	ll hash1,hash2;
}hashx,hashs;
vector<node> v[maxn];
void init(){
	pow[0]=1;
	for(int i=1;i<=100000;i++)
		pow[i]=(pow[i-1]*base)%mod;
}
int main(){
	init();
	scanf("%lld%lld%lld",&n,&t,&Q);
	for(int i=1;i<=t;i++){
		scanf("%lld",&s[i]);
		hashs.hash1=(hashs.hash1+pow[s[i]])%mod;
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&len[i]);
		for(int j=1;j<=len[i];j++)
			scanf("%lld",&a[j]);
		v[i].resize(len[i]+1);
		v[i][len[i]].hash1=pow[a[len[i]]];
		for(int j=len[i]-1;j>=1;j--){
			v[i][j].hash1=(v[i][j+1].hash1+pow[a[j]])%mod;
		}
	}
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
		scanf("%lld",&r[i]);
	for(int i=1;i<=m&&i<=Q;i++){
		now=r[i];
		lenx+=len[now];
		hashx.hash1=(hashx.hash1+v[now][1].hash1)%mod;
		q.push_back(P{now,1});
		while(lenx>t){
			P top=q.front();
			q.pop_front();
			lenx-=len[top.first]-top.second+1;
			hashx.hash1-=v[top.first][top.second].hash1;
			if(lenx<t){
				k=len[top.first]-(t-lenx)+1;
				lenx=t;
				hashx.hash1+=v[top.first][k].hash1;
				hashx.hash1%=mod;
				q.push_front(P(top.first,k));
			}
		}
		if(hashx.hash1==hashs.hash1)
			ANS++;
		}
	if(Q<=m){
		printf("%lld",ANS);
		return 0;
	}
	Q-=m;
	for(int i=1;i<=m&&i<=Q;i++){
		now=r[i];
		lenx+=len[now];
		hashx.hash1=(hashx.hash1+v[now][1].hash1)%mod;
		q.push_back(P{now,1});
		while(lenx>t){
			P top=q.front();
			q.pop_front();
			lenx-=len[top.first]-top.second+1;
			hashx.hash1-=v[top.first][top.second].hash1;
			if(lenx<t){
				k=len[top.first]-(t-lenx)+1;
				lenx=t;
				hashx.hash1+=v[top.first][k].hash1;
				hashx.hash1%=mod;
				q.push_front(P(top.first,k));
			}
		}
		ans[i]=ans[i-1]+(hashx.hash1==hashs.hash1);
		}
	cout<<ANS+ans[m]*(Q/m)+ans[Q%m];
}
2021/4/3 12:55
加载中...