题解
liaojiqing2012
·
·
题解
对于 q 比较小的情况
想一想，如果只有 0,1 的情况，是不是只要判断后缀长度 t 的字符串中有多少个 1 就可以了。
如果数可以是 0,1 以外的数呢，是不是就行不通了，没关系，我们仍然可以讨论他们的总和。但是我们得稍微变一下，不能直接加起来。
利用 hash 的思想，我们把一个数化成六个参数，分别是
-
x
-
x\times 23
-
x^3
-
f(x)
-
x^2
-
\sqrt{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
*/
```