Advertisement
Guest User

Untitled

a guest
Apr 26th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. const int MAXN = (int)1e2 + 7;
  2. const int INF = (int)2e9 + 7;
  3. const ll LINF = (ll)7e18 + 7;
  4. const ll MOD = (ll)1e9 + 7;
  5. const ll P = 59;
  6. const ll Q = 61;
  7. const ll HMOD = (ll)2e9 + 33;
  8.  
  9. int n, m;
  10. int p[MAXN], q[MAXN];
  11. int h[MAXN][MAXN], rh[MAXN][MAXN];
  12. char a[MAXN][MAXN];
  13.  
  14. int mul(int a, int b)
  15. {
  16.     return ((ll)a * (ll)b) % HMOD;
  17. }
  18.  
  19. int gethash(int x1, int y1, int x2, int y2)
  20. {
  21.     int mns = 0;
  22.     if (x1)
  23.     {
  24.         mns = ((ll)mns + mul(h[x1 - 1][y2], p[x2 - x1 + 1])) % HMOD;
  25.     }
  26.     if (y1)
  27.     {
  28.         mns = ((ll)mns + mul(h[x2][y1 - 1], q[y2 - y1 + 1])) % HMOD;
  29.     }
  30.     int pl = h[x2][y2];
  31.     if (x1 && y1)
  32.     {
  33.         pl = ((ll)pl + mul(mul(h[x1 - 1][y1 - 1], p[x2 - x1 + 1]), q[y2 - y1 + 1])) % HMOD;
  34.     }
  35.     int ans = (pl - mns) % HMOD;
  36.     if (ans < 0)
  37.         return ans + HMOD;
  38.     return ans;
  39. }
  40.  
  41. int getrhash(int x1, int y1, int x2, int y2)
  42. {
  43.     int mns = 0;
  44.     if (x1)
  45.     {
  46.         mns = ((ll)mns + mul(rh[x1 - 1][y2], p[x2 - x1 + 1])) % HMOD;
  47.     }
  48.     if (y1)
  49.     {
  50.         mns = ((ll)mns + mul(rh[x2][y1 - 1], q[y2 - y1 + 1])) % HMOD;
  51.     }
  52.     int pl = rh[x2][y2];
  53.     if (x1 && y1)
  54.     {
  55.         pl = ((ll)pl + mul(mul(rh[x1 - 1][y1 - 1], p[x2 - x1 + 1]), q[y2 - y1 + 1])) % HMOD;
  56.     }
  57.     int ans = (pl - mns) % HMOD;
  58.     if (ans < 0)
  59.         return ans + HMOD;
  60.     return ans;
  61. }
  62.  
  63. int solve()
  64. {
  65.     q[0] = 1;
  66.     p[0] = 1;
  67.     for (int i = 1; i < MAXN; ++i)
  68.     {
  69.         p[i] = ((ll)p[i - 1] * P) % HMOD;
  70.         q[i] = ((ll)q[i - 1] * Q) % HMOD;
  71.     }
  72.     scanf("%d %d", &n, &m);
  73.     for (int i = 0; i < n; ++i)
  74.     {
  75.         for (int j = 0; j < m; ++j)
  76.         {
  77.             scanf(" %c", &a[i][j]);
  78.             h[i][j] = a[i][j] - 'a' + 1;
  79.             if (i)
  80.                 h[i][j] = ((ll)h[i][j] + mul(h[i - 1][j], P)) % HMOD;
  81.             if (j)
  82.                 h[i][j] = ((ll)h[i][j] + mul(h[i][j - 1], Q)) % HMOD;
  83.             if (i && j)
  84.             {
  85.                 h[i][j] = ((ll)h[i][j] - mul(mul(h[i - 1][j - 1], P), Q)) % HMOD;
  86.                 if (h[i][j] < 0)
  87.                     h[i][j] += HMOD;
  88.             }
  89.         }
  90.     }
  91.     for (int i1 = n - 1, i = 0; i1 >= 0; --i1, ++i)
  92.     {
  93.         for (int j1 = m - 1, j = 0; j1 >= 0; --j1, ++j)
  94.         {
  95.             rh[i][j] = a[i1][j1] - 'a' + 1;
  96.             if (i)
  97.                 rh[i][j] = ((ll)rh[i][j] + mul(rh[i - 1][j], P)) % HMOD;
  98.             int rs = mul(rh[i][j - 1], Q);
  99.             if (j)
  100.                 rh[i][j] = ((ll)rh[i][j] + mul(rh[i][j - 1], Q)) % HMOD;
  101.             if (i && j)
  102.             {
  103.                 rh[i][j] = ((ll)rh[i][j] - mul(mul(rh[i - 1][j - 1], P), Q)) % HMOD;
  104.                 if (rh[i][j] < 0)
  105.                     rh[i][j] += HMOD;
  106.             }
  107.         }
  108.     }
  109.     int ans = 0;
  110.     for (int x1 = 0; x1 < n; ++x1)
  111.     {
  112.         for (int y1 = 0; y1 < m; ++y1)
  113.         {
  114.             for (int x2 = x1; x2 < n; ++x2)
  115.             {
  116.                 for (int y2 = y1; y2 < m; ++y2)
  117.                 {
  118.                     ans += gethash(x1, y1, x2, y2) == getrhash(n - 1 - x2, m - 1 - y2, n - 1 - x1, m - 1 - y1);
  119.                 }
  120.             }
  121.         }
  122.     }
  123.     printf("%d\n", ans);
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement