自动搬运

查看原文

来自洛谷，原作者为

	liaojiqing2012 **

搬运于2025-08-24 22:08:55，当前版本为作者最后更新于2021-11-12 15:46:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于 $q$ 比较小的情况

想一想，如果只有 $0,1$ 的情况，是不是只要判断后缀长度 $t$ 的字符串中有多少个 $1$ 就可以了。 如果数可以是 $0,1$ 以外的数呢，是不是就行不通了，没关系，我们仍然可以讨论他们的总和。但是我们得稍微变一下，不能直接加起来。 利用 hash 的思想，我们把一个数化成六个参数，分别是

• $x$
• $x\times 23$
• $x^3$
• $f(x)$
• $x^2$
• $\sqrt{x}$

$f(x)$ 是一个随机生成的映射函数。

然后也和 $0,1$ 的情况一样判断。把所有参数加起来就可以。

对于 $q$ 比较大的情况

考虑到 $q$ 比较大时候，是一个循环队列。所以答案可以看成：

起始部分的答案加上重复部分的答案乘以重复次数再加上结束部分的答案。

所以，选一个大概合理的重复部分，就可以计算了。

顺带一提，其他题解的标程全是错的。

hack 数据：

9 50 20
1 2 1 2 1 2 1 1 2 2 1 1 2 1 2 1 1 2 1 1 2 2 1 2 2 1 2 2 2 1 2 1 1 1 1 2 1 2 2 1 1 2 2 1 2 2 2 1 2 1  
2 1 2 
1 2 
5 2 1 1 1 1 
3 1 1 2 
3 1 2 2 
4 1 2 2 2 
3 1 1 1 
4 2 2 1 1 
3 2 2 2 
9
7 5 3 1 8 2 6 4 9

正确答案输出 $2$，他们输出 $1$。

1 3 10
1 1 1
1 1
1
1

正确答案输出 $8$，他们输出 $0$。

标程

#include<bits/stdc++.h>
#define random(l,r) ((rand()*32768+rand())%(r-l+1)+l) 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int inf=0x7fffffff;
const int maxn=210000;
int fval[maxn];
struct ss{
	unsigned  a,b,c,d,e,f;
	ss(){a=b=c=d=e=f=0;}
	ss(int a,int b,int c,int d,int e,int f):a(a),b(b),c(c),d(d),e(e),f(f){}
	ss(int x){
		a=x;
		b=x*23;
		c=x*x*x;
		d=fval[x];
		e=x*x;
		f=sqrt(x);
	}
	ss operator -=(ss t1){
		a-=t1.a;
		b-=t1.b;
		c-=t1.c;
		d-=t1.d;
		e-=t1.e;
		f-=t1.f;
		return *this;
	} 
	ss operator +=(ss t1){
		a+=t1.a;
		b+=t1.b;
		c+=t1.c;
		d+=t1.d;
		e+=t1.e;
		f+=t1.f;
		return *this;
	} 
	bool operator ==(ss t1){
		return a==t1.a&&b==t1.b&&c==t1.c&&d==t1.d&&e==t1.e&&f==t1.f;
	} 
};
ss operator + (ss t1,ss t2){
	return  ss(t1.a+t2.a,t1.b+t2.b,t1.c+t2.c,t1.d+t2.d,t1.e+t2.e,t1.f+t2.f);
}
int gcd(int a,int b){
	return !b?a:gcd(b,a%b);
}
vector<int>aa[maxn];
vector<ss>tot[maxn];
int n,t,q,m,r[maxn];
void solve() {
	srand(time(0));
	for(int i=0;i<=1e5;i++)
		fval[i]=random(1,(int)1e9);
	cin>>n>>t>>q;
	ss key;
	for(int a,i=1;i<=t;i++){
		cin>>a;
		key+=ss(a);
	}
	for(int z,i=1;i<=n;i++){
	//	cout<<" input "<<i<<endl;
		cin>>z;
		aa[i].push_back(z);
		for(int kk,j=z;j>=1;j--){
			cin>>kk;
			aa[i].push_back(kk);
		}
		ss key;
		tot[i].push_back(key);
		for(int j=z;j>=1;j--){
			tot[i].push_back(key+=ss(aa[i][j]));
		}
	}
	//cout<<"check123"<<endl;
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>r[i];
	}
	ss tt;
	int be=0,len=0,len0=0,ans=0;
	tot[0].push_back(tt);
	aa[0].push_back(0);
//	cout<<"qwe"<<endl;
	if(q<=maxn*8){
		for(int i=1;i<=q;i++){
			int x=r[(i-1)%m+1]; 
	//		cout<<"x = "<<x<<endl;
			len+=aa[x][0];
		//	cout<<"len = "<<len<<endl;
			tt+=tot[x][aa[x][0]];
		//	cout<<"check 0"<<endl;
			while(be<i&&len-len0>=t){
			//	cout<<be<<endl;
				len-=len0;
				tt-=tot[r[(be-1)%m+1]][len0];
				be++;
				len0=aa[r[(be-1)%m+1]][0];
			//	cout<<len0<<" "<<len<<endl;
			}
			//cout<<"check 1"<<endl; 
			if(len>t){
				tt-=tot[r[(be-1)%m+1]][len0];
				len0=len0-(len-t);
				tt+=tot[r[(be-1)%m+1]][len0];
				len=t;
			}
			if(len==t){
				if(tt==key)ans++;
			}
		//	cout<<i<<" "<<ans<<" "<<be<<" "<<len<<" "<<len0<<endl;
		} 
		cout<<ans<<endl;
	}else{
		int mm=m;
		while(mm*2<=maxn*2)mm*=2;
		int bb=(q-mm)%mm,kk=(q-mm)/mm;
	//	cout<<kk<<" "<<bb<<" "<<mm<<endl;
	//	cout<<mm<<endl;
		for(int i=1;i<=mm;i++){
			int x=r[(i-1)%m+1]; 
	//		cout<<"x = "<<x<<endl;
			len+=aa[x][0];
		//	cout<<"len = "<<len<<endl;
			tt+=tot[x][aa[x][0]];
		//	cout<<"check 0"<<endl;
			while(be<i&&len-len0>=t){
			//	cout<<be<<endl;
				len-=len0;
				tt-=tot[r[(be-1)%m+1]][len0];
				be++;
				len0=aa[r[(be-1)%m+1]][0];
			//	cout<<len0<<" "<<len<<endl;
			}
			//cout<<"check 1"<<endl; 
			if(len>t){
				tt-=tot[r[(be-1)%m+1]][len0];
				len0=len0-(len-t);
				tt+=tot[r[(be-1)%m+1]][len0];
				len=t;
			}
			if(len==t){
				if(tt==key)ans++;
			}
		//	cout<<i<<" "<<ans<<" "<<be<<" "<<len<<" "<<len0<<endl;
		} 
		int ans2=0;
		for(int i=mm+1;i<=mm+mm;i++){
			int x=r[(i-1)%m+1]; 
	//		cout<<"x = "<<x<<endl;
			len+=aa[x][0];
		//	cout<<"len = "<<len<<endl;
			tt+=tot[x][aa[x][0]];
		//	cout<<"check 0"<<endl;
			while(be<i&&len-len0>=t){
			//	cout<<be<<endl;
				len-=len0;
				tt-=tot[r[(be-1)%m+1]][len0];
				be++;
				len0=aa[r[(be-1)%m+1]][0];
			//	cout<<len0<<" "<<len<<endl;
			}
			//cout<<"check 1"<<endl; 
			if(len>t){
				tt-=tot[r[(be-1)%m+1]][len0];
				len0=len0-(len-t);
				tt+=tot[r[(be-1)%m+1]][len0];
				len=t;
			}
			if(len==t){
				if(tt==key)ans2++;
			}
		//	cout<<i<<" "<<ans<<" "<<be<<" "<<len<<" "<<len0<<endl;
		} 
		ans2*=kk;
		ans+=ans2;
	//	cout<<ans<<endl;
//		cout<<bb<<" "<<be<<" "<<len<<" "<<len0<<" "<<kk<<endl;
		for(int i=mm*2+1;i<=mm*2+bb;i++){
			int x=r[(i-1)%m+1]; 
	//		cout<<"x = "<<x<<endl;
			len+=aa[x][0];
		//	cout<<"len = "<<len<<endl;
			tt+=tot[x][aa[x][0]];
		//	cout<<"check 0"<<endl;
			while(be<i&&len-len0>=t){
			//	cout<<be<<endl;
				len-=len0;
				tt-=tot[r[(be-1)%m+1]][len0];
				be++;
				len0=aa[r[(be-1)%m+1]][0];
			//	cout<<len0<<" "<<len<<endl;
			}
			//cout<<"check 1"<<endl; 
			if(len>t){
				tt-=tot[r[(be-1)%m+1]][len0];
				len0=len0-(len-t);
				tt+=tot[r[(be-1)%m+1]][len0];
				len=t;
			}
			if(len==t){
				if(tt==key)ans++;
			}
		//	cout<<i<<" "<<ans<<" "<<be<<" "<<len<<" "<<len0<<endl;
		} 
		cout<<ans<<endl;
	}
}
int main() {
	int t=1;
	//cin>>t;
	while(t--) solve();
}

/*
10 10 9600
0 1 1 1 0 1 1 0 0 0 
6 0 0 1 1 1 0 
6 0 0 0 0 0 0 
5 0 0 0 0 0 
4 1 0 0 0 
5 1 1 1 0 1 
2 1 1 
6 0 0 0 0 0 1 
1 0 
4 0 0 1 1 
1 1 
30
10 4 3 9 10 9 4 8 5 10 9 8 6 10 10 4 9 2 2 9 6 4 1 10 10 1 9 10 3 5 
*/