Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int MAXN = (int)1e2 + 7;
- const int INF = (int)2e9 + 7;
- const ll LINF = (ll)7e18 + 7;
- const ll MOD = (ll)1e9 + 7;
- const ll P = 59;
- const ll Q = 61;
- const ll HMOD = (ll)2e9 + 33;
- int n, m;
- int p[MAXN], q[MAXN];
- int h[MAXN][MAXN], rh[MAXN][MAXN];
- char a[MAXN][MAXN];
- int mul(int a, int b)
- {
- return ((ll)a * (ll)b) % HMOD;
- }
- int gethash(int x1, int y1, int x2, int y2)
- {
- int mns = 0;
- if (x1)
- {
- mns = ((ll)mns + mul(h[x1 - 1][y2], p[x2 - x1 + 1])) % HMOD;
- }
- if (y1)
- {
- mns = ((ll)mns + mul(h[x2][y1 - 1], q[y2 - y1 + 1])) % HMOD;
- }
- int pl = h[x2][y2];
- if (x1 && y1)
- {
- pl = ((ll)pl + mul(mul(h[x1 - 1][y1 - 1], p[x2 - x1 + 1]), q[y2 - y1 + 1])) % HMOD;
- }
- int ans = (pl - mns) % HMOD;
- if (ans < 0)
- return ans + HMOD;
- return ans;
- }
- int getrhash(int x1, int y1, int x2, int y2)
- {
- int mns = 0;
- if (x1)
- {
- mns = ((ll)mns + mul(rh[x1 - 1][y2], p[x2 - x1 + 1])) % HMOD;
- }
- if (y1)
- {
- mns = ((ll)mns + mul(rh[x2][y1 - 1], q[y2 - y1 + 1])) % HMOD;
- }
- int pl = rh[x2][y2];
- if (x1 && y1)
- {
- pl = ((ll)pl + mul(mul(rh[x1 - 1][y1 - 1], p[x2 - x1 + 1]), q[y2 - y1 + 1])) % HMOD;
- }
- int ans = (pl - mns) % HMOD;
- if (ans < 0)
- return ans + HMOD;
- return ans;
- }
- int solve()
- {
- q[0] = 1;
- p[0] = 1;
- for (int i = 1; i < MAXN; ++i)
- {
- p[i] = ((ll)p[i - 1] * P) % HMOD;
- q[i] = ((ll)q[i - 1] * Q) % HMOD;
- }
- scanf("%d %d", &n, &m);
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- scanf(" %c", &a[i][j]);
- h[i][j] = a[i][j] - 'a' + 1;
- if (i)
- h[i][j] = ((ll)h[i][j] + mul(h[i - 1][j], P)) % HMOD;
- if (j)
- h[i][j] = ((ll)h[i][j] + mul(h[i][j - 1], Q)) % HMOD;
- if (i && j)
- {
- h[i][j] = ((ll)h[i][j] - mul(mul(h[i - 1][j - 1], P), Q)) % HMOD;
- if (h[i][j] < 0)
- h[i][j] += HMOD;
- }
- }
- }
- for (int i1 = n - 1, i = 0; i1 >= 0; --i1, ++i)
- {
- for (int j1 = m - 1, j = 0; j1 >= 0; --j1, ++j)
- {
- rh[i][j] = a[i1][j1] - 'a' + 1;
- if (i)
- rh[i][j] = ((ll)rh[i][j] + mul(rh[i - 1][j], P)) % HMOD;
- int rs = mul(rh[i][j - 1], Q);
- if (j)
- rh[i][j] = ((ll)rh[i][j] + mul(rh[i][j - 1], Q)) % HMOD;
- if (i && j)
- {
- rh[i][j] = ((ll)rh[i][j] - mul(mul(rh[i - 1][j - 1], P), Q)) % HMOD;
- if (rh[i][j] < 0)
- rh[i][j] += HMOD;
- }
- }
- }
- int ans = 0;
- for (int x1 = 0; x1 < n; ++x1)
- {
- for (int y1 = 0; y1 < m; ++y1)
- {
- for (int x2 = x1; x2 < n; ++x2)
- {
- for (int y2 = y1; y2 < m; ++y2)
- {
- ans += gethash(x1, y1, x2, y2) == getrhash(n - 1 - x2, m - 1 - y2, n - 1 - x1, m - 1 - y1);
- }
- }
- }
- }
- printf("%d\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement