写哈希时哈希值开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];
}