好复杂啊(代码太乱了),差点搞我几个小时,还好讨论区有警示后人:不能直接用 (会有精度误差)。
首先问题转化,对于每一个询问要求的位置,判断当前位置的和 长度相同的后缀每一个出现过的数出现次数相同。
大体思路就是设计一个哈希,需要只判断数字出现个数相同,但是不需要对应位置相同。
然后一个比较好的就是:
这种大的数字一般用 unsigned long long 自然溢出。
这道题中 很大,怎么办?我们发现会重复这 个操作,所以可以计算循环节。
然后代码的思路是先从 计算,然后我们可以先找到 大于 的第一个点,然后从这个点开始进行 次操作,然后记录每一次操作的答案为循环节。
最后统计答案需要去除 的部分,还要加上最后不在一整个循环节内的部分。
还要提醒,注意细节,我写代码 分钟,调了至少 分钟,写的输出调试差不多 行。
代码
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;
}