P5270 无论怎样神树大人都会删库跑路
syk666
·
·
题解
对于字符集较小的情况，考虑对于每一个出现过的字符开桶，最后将出现过的次数当成一个字符串。
然后我们如何判断能否拼出来，即两个字符串完全相同。
那么检索过程我们尽量做到更快，则可以使用到字符串哈希。
接着分为两个步骤：
一.第一轮匹配完 m 次操作。
二.除了 1 以外的所有操作。
为什么要分两步呢？
因为第一步做完后我们会剩余一些数影响到后面操作，而接下来的操作前面所多的数是相同的，因此可以搞在一起做。
接着稍微描述下匹配时的细节：
因为 S 串的长度为 m ，那么我们只需要记录恰好 m 位即可。
插入很好做，主要需要排除开头对答案的影响。
定义 nxt 为第一个字符串是什么，nxtpos 当前取到 nxt 这个字符串的第几位。
```cpp
for(int i=1;i<=m&&i<=Q;i++){
now+=a[r[i]].h;
Len+=a[r[i]].len;
while(Len>T&&nxt<=i){
if(nxtpos!=1||Len-a[r[nxt]].len<T){
//当前不是一整个字符串或者长度不足以到达一整个
int delta=min(Len-T,a[r[nxt]].len-nxtpos+1);
now-=calc(r[nxt],nxtpos,nxtpos+delta-1);
Len-=delta;
nxtpos+=delta;
}else if(Len-a[r[nxt]].len>=T){
//跳一整个
Len-=a[r[nxt]].len;
now-=a[r[nxt]].h;
nxt++;
nxtpos=1;
}
while(nxtpos>a[r[nxt]].len&&nxt<=i){
//调整nxt，nxtpos
nxtpos-=a[r[nxt]].len;
nxt++;
}
}
if(now==hash1) res++;
}
```
对于第二步，与第一步大同小异，唯一需要记录当前步的前缀答案和（为了方便统计后面的答案）。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=6e6+5000;
int n,T,Q;
int s[N];
const unsigned long long base=19260817;
unsigned long long hash1=0;
int len;
vector<int> v[N];
int maxx;
int m,r[N];
map<int,int> tong;
unsigned long long p[N];
long long p2[N];//
vector<unsigned long long> h[N];
vector<long long > H[N];//
const int mod=1e9+9;//
const int base2=233;//
struct node{
int len;
unsigned long long h;
}a[N];
unsigned long long now=0;
int Len=0;
int res=0;
unsigned long long calc(int id,int L,int R){
unsigned long long ans=h[id][R]-h[id][L-1];
return ans;
}
int SUM=0;
int Pre[N];
int main(){
scanf("%d%d%d",&n,&T,&Q);
p[0]=1;
for(int i=1;i<=2000000;i++)
p[i]=p[i-1]*base;
for(int i=1;i<=T;i++){
scanf("%d",&s[i]);
tong[s[i]]++;
maxx=max(maxx,s[i]);
hash1+=p[s[i]];
}
tong.clear();
for(int i=1;i<=n;i++){
int len;
scanf("%d",&len);
h[i].push_back(0);
for(int j=1;j<=len;j++){
int x;
scanf("%d",&x);
v[i].push_back(x);
unsigned long long tmp=h[i][j-1];
tmp=tmp+p[x];
h[i].push_back(tmp);
}
a[i].len=len;
a[i].h=h[i][len];
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&r[i]);
if(m<T){
for(int i=1;i<=m;i++)
for(int j=1;j<=10;j++)
r[i+j*m]=r[i];
m*=10;
}
for(int i=1;i<=m;i++)
r[i+m]=r[i];
int nxt=1,nxtpos=1;
for(int i=1;i<=m&&i<=Q;i++){
now+=a[r[i]].h;
Len+=a[r[i]].len;
while(Len>T&&nxt<=i){
if(nxtpos!=1||Len-a[r[nxt]].len<T){
int delta=min(Len-T,a[r[nxt]].len-nxtpos+1);
now-=calc(r[nxt],nxtpos,nxtpos+delta-1);
Len-=delta;
nxtpos+=delta;
}else if(Len-a[r[nxt]].len>=T){
Len-=a[r[nxt]].len;
now-=a[r[nxt]].h;
nxt++;
nxtpos=1;
}
while(nxtpos>a[r[nxt]].len&&nxt<=i){
nxtpos-=a[r[nxt]].len;
nxt++;
}
}
if(now==hash1) res++;
}
for(int i=1;i<=m&&i+m<=Q;i++){
now+=a[r[i]].h;
Len+=a[r[i]].len;
while(Len>T&&nxt<=i+m){
if(nxtpos!=1||Len-a[r[nxt]].len<T){
int delta=min(Len-T,a[r[nxt]].len-nxtpos+1);
now-=calc(r[nxt],nxtpos,nxtpos+delta-1);
Len-=delta;
nxtpos+=delta;
}else if(Len-a[r[nxt]].len>=T){
Len-=a[r[nxt]].len;
now-=a[r[nxt]].h;
nxt++;
nxtpos=1;
}
while(nxtpos>a[r[nxt]].len&&nxt<=i+m){
nxtpos-=a[r[nxt]].len;
nxt++;
}
}
Pre[i]=Pre[i-1];
if(now==hash1) res++,SUM++,Pre[i]++;
}
Q-=2*m;
if(Q>=0){
res+=(Q/m)*SUM+(Pre[Q%m]);
}
cout<<res<<endl;
return 0;
}
```