CUBE-198: Number Theory

#include <bits/stdc++.h>

using namespace std;

using lli = long long;
const lli PB = 98765431;
int A[200010], B[200010];

int main(){

    int n, m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d", &A[i]);
    for(int i=1;i<=m;i++) scanf("%d", &B[i]);

    vector <lli> R;
    vector <int> pst;

    lli rem = 1, hsh = 0, cmp = 0;
    for(int i = 1; i <= m; i ++){
        if(i != 1) rem = rem * PB;
        hsh = hsh * PB + A[i];
        cmp = cmp * PB + B[i];
        for(int j = 0; j < pst.size(); j ++) R[j] = R[j] * PB;
        if(B[i] == 1){
            pst.push_back(i);
            R.push_back(1);
        }
    }

    int cnt = 0;
    for(int i = m; i <= n; i ++){
        if(i != m) hsh = hsh * PB + A[i];
        lli h = hsh;
        for(int j = 0; j < pst.size(); j ++){
            h = h + (1 - A[i-m+pst[j]])*R[j];
        }
        if(h == cmp) cnt ++;
        hsh = hsh - A[i-m+1] * rem;
    }

    printf("%d", cnt);

    return 0;
}