P3560 [POI2013] LAN-Colorful Chain

我们需要先求出目标串的 hash 值。

先求出每个数的 hash 值，再将目标串的每个数的 hash 值乘上各自出现次数，加和即可得到。

同理求出原串每个长度为目标串长度的串的 hash 值，随便比较一下，并记录答案即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7 , base = 13331;
int n , m , hsh[1000010] , sum[1000010] , l[1000010] , c[1000010] , a[1000010] , len , ans , res;
signed main()
{
    scanf("%lld%lld" , &n , &m);
    hsh[0] = 1;
    for(int i = 1 ; i <= n ; i ++) hsh[i] = hsh[i - 1] * base % mod;
    for(int i = 1 ; i <= m ; i ++) scanf("%lld" , &l[i]) , len += l[i];
    for(int i = 1 , x ; i <= m ; i ++) scanf("%lld" , &x) , res += hsh[x] * l[i] % mod , res %= mod;
    for(int i = 1 , x ; i <= n ; i ++) scanf("%lld" , &x) , sum[i] = (sum[i - 1] + hsh[x]) % mod;
    for(int i = 1 ; i + len - 1 <= n ; i ++) ans += ((sum[i + len - 1] - sum[i - 1] + mod) % mod == res);
    printf("%lld" , ans);
    return 0;
}