POJ.3690 Constellations

1.Problem
http://poj.org/problem?id=3690

2.Idea
Rolling Hash D2

3.Source Code

 typedef unsigned long long ull;  
 int N, M, T, P, Q;  
 char field[1100][1100];  
 char patterns[110][1100][1100];  
 ull Hash[1100][1100], tmp[1100][1100];  
 void compute_hash(char a[1100][1100], int n, int m)  
 {  
      const ull B1 = 9973;  
      const ull B2 = 1000000007;  
      ull t1 = 1;  
      for (int j = 0; j < Q; j++) t1 *= B1;  
      for (int i = 0; i < n; i++) {  
           ull e = 0;  
           for (int j = 0; j < Q; j++) {  
                e = e * B1 + a[i][j];  
           }  
           for (int j = 0; j + Q <= m; j++) {  
                tmp[i][j] = e;  
                if (j + Q < m) e = e * B1 - t1 * a[i][j] + a[i][j + Q];  
           }  
      }  
      ull t2 = 1;  
      for (int i = 0; i < P; i++) t2 *= B2;  
      for (int j = 0; j + Q <= m; j++) {  
           ull e = 0;  
           for (int i = 0; i < P; i++) {  
                e = e * B2 + tmp[i][j];  
           }  
           for (int i = 0; i + P <= n; i++) {  
                Hash[i][j] = e;  
                if (i + P < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];  
           }  
      }  
 }  
 void solve()  
 {  
      int cnt = 0;  
      while (true) {  
           scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);  
           if (N + M + T + P + Q == 0) break;  
           cnt++;  
           for (int i = 0; i < N; ++i) {  
                scanf("%s", field[i]);  
           }  
           for (int t = 0; t < T; ++t) {  
                for (int i = 0; i < P; ++i) {  
                     scanf("%s", patterns[t][i]);  
                }  
           }  
           multiset<ull> unseen;  
           for (int k = 0; k < T; k++) {  
                compute_hash(patterns[k], P, Q);  
                unseen.insert(Hash[0][0]);  
           }  
           compute_hash(field, N, M);  
           for (int i = 0; i + P <= N; i++) {  
                for (int j = 0; j + Q <= M; j++) {  
                     unseen.erase(Hash[i][j]);  
                }  
           }  
           printf("Case %d: %d\n", cnt, T - unseen.size());  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

CodeForces. 1333C Eugene and an array

1.Problem
https://codeforces.com/problemset/problem/1333/C

2.Idea
Keep tracking right most sum zero segment. 

3.Source

 int n;  
 map<ll, int> mp;  
 ll ans, sum;  
 int x, q;  
 int main()  
 {  
      cin >> n;  
      q = -1;  
      mp[0] = 0;  
      for (int i = 1; i <= n; i++)  
      {  
           cin >> x;  
           sum += x;  
           if (mp.count(sum)) {  
                q = max(q, mp[sum]);  
           }  
           ans += (i - q - 1);  
           mp[sum] = i;  
      }  
      cout << ans << endl;  
      return 0;  
 }