Advertisement
YEZAELP

CUBE-198: Number Theory

Oct 12th, 2020
115
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. const lli PB = 98765431;
  7. int A[200010], B[200010];
  8.  
  9. int main(){
  10.  
  11.     int n, m;
  12.     scanf("%d%d",&n,&m);
  13.  
  14.     for(int i=1;i<=n;i++) scanf("%d", &A[i]);
  15.     for(int i=1;i<=m;i++) scanf("%d", &B[i]);
  16.  
  17.     vector <lli> R;
  18.     vector <int> pst;
  19.  
  20.     lli rem = 1, hsh = 0, cmp = 0;
  21.     for(int i = 1; i <= m; i ++){
  22.         if(i != 1) rem = rem * PB;
  23.         hsh = hsh * PB + A[i];
  24.         cmp = cmp * PB + B[i];
  25.         for(int j = 0; j < pst.size(); j ++) R[j] = R[j] * PB;
  26.         if(B[i] == 1){
  27.             pst.push_back(i);
  28.             R.push_back(1);
  29.         }
  30.     }
  31.  
  32.     int cnt = 0;
  33.     for(int i = m; i <= n; i ++){
  34.         if(i != m) hsh = hsh * PB + A[i];
  35.         lli h = hsh;
  36.         for(int j = 0; j < pst.size(); j ++){
  37.             h = h + (1 - A[i-m+pst[j]])*R[j];
  38.         }
  39.         if(h == cmp) cnt ++;
  40.         hsh = hsh - A[i-m+1] * rem;
  41.     }
  42.  
  43.     printf("%d", cnt);
  44.  
  45.     return 0;
  46. }
  47.  
Advertisement
RAW Paste Data Copied
Advertisement