Beautiful Matrix

前往 算竞题解 分类 || 前往 算竞模板 分类

原题链接

G-Beautiful Matrix 2023牛客暑期多校训练营3

简明题意

  • 给一个二维矩阵，求其中有多少个中心对称正方形子矩阵。
  • 数据范围：矩阵小于 2000x2000，没有多组，时间限制 5s 。

注：这道题非常的丑，一点不 Beautiful ！

解题思路（一）

  • 可以考虑使用二维字符串哈希。对矩阵求二维哈希，然后逆序求一遍哈希，通过比较哈希值可以 O(1)O(1) 判定一个矩阵是否为中心对称矩阵。

  • 预处理二维哈希值是 O(n2)O(n^2) 的，但是如果我们考虑枚举所有正方形子矩阵，发现时间复杂度是 O(n3)O(n^3) 的，这是一个不可接受的时间。然后我们可以考虑枚举矩阵的中心，然后通过二分判断以该点为中心的最大中心对称正方形子矩阵，因为对于中心对称正方形满足相同中心的更小正方形同样满足中心对称。时间复杂度为 O(n2logn)O(n^2logn) ，这里需要注意偶矩阵与奇矩阵需要分类讨论，或者直接添加空字符将矩阵拓展为两倍。

  • 这个解法，非常的卡常。题解说这个思路有点卡常。 O(n2logn)O(n^2logn) 大概是 4×1074 \times {10}^7 ，考虑常数：进行一次逆序哈希 ×2\times 2 ；哈希过程大量的取模操作 ×4\times 4 ；考虑使用双哈否则精度不够 ×2\times 2 ；然后你需要讨论奇偶矩阵，如果你使用分类讨论 ×2\times 2 ，如果使用拓展矩阵 ×4\times 4 。我的这个解法折算评测机时间大概需要 9s 。你可以尝试使用自然溢出哈希，可以节约大概 ×8\times 8 的常数，但是最后一组数据把自然溢出卡的 SS 的。

  • 我赛事看到这道题第一想法就是 HashHash ！但是一直想不明白二维哈希如何编码。二维哈希使用下图方式编码。

    hash[x][y]=hash[x−1][y]×basex+ hash[x][y−1]×basey− hash[x−1][y−1]×basex×basey\begin{array}{rl} hash[x][y] & = hash[x-1][y] \times base_x \\ & +~hash[x][y-1] \times base_y \\ & -~hash[x-1][y-1] \times base_x \times base_y \\ \end{array}

    hash[x1..x2][y1..y2]=hash[x2][y2]− hash[x1−1][y2]×basexx2−x1+1− hash[x2][y1−1]×baseyy2−y1+1+ hash[x1−1][x2−1]×basexx2−x1+1×baseyy2−y1+1\begin{array}{rl} hash[x_1..x_2][y_1..y_2] & = hash[x_2][y_2] \\ & -~hash[x_1 - 1][y_2] \times base_x^{x_2 - x_1 + 1} \\ & -~hash[x_2][y_1 - 1] \times base_y^{y_2 - y_1 + 1} \\ & +~hash[x_1 - 1][x_2 - 1] \times base_x^{x_2 - x_1 + 1} \times base_y^{y_2 - y_1 + 1} \\ \end{array}

代码（一）

  • 这份代码可以当作板子存起来，提供了三个编译开关：双哈，自然溢出，逆序哈希。三个开关可以任意排列组合，各有利弊。
  • 这份代码考虑时间和数据，带模数的单哈，这种哈希的精度是不够的，在不断尝试下才过的题。跑了 4.7s 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
// Beautiful Matrix
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1  // Test Switch
#else
// #define TEST 1
#define LOCAL 1  // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
// #pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 2005;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

// #define HASH_DOUBLE   // 双哈开关         // 关闭，不然会 TLE
// #define HASH_NETURAL  // 自然溢出哈希开关  // 关闭，不然会被最后一组数据卡掉
#define HASH_REV      // 逆序开关

#ifdef HASH_NETURAL
#define HASH_CODE uint64_t
#else
#define HASH_CODE int64_t
#endif

const int HX1 = 157, HY1 = 13331, HM1 = 1000000009;
#ifdef HASH_DOUBLE
const int HX2 = 131, HY2 = 10037, HM2 = 999999937;
#endif

HASH_CODE px1[MAX];
HASH_CODE py1[MAX];
HASH_CODE h1[MAX][MAX];
#ifdef HASH_DOUBLE
HASH_CODE px2[MAX];
HASH_CODE py2[MAX];
HASH_CODE h2[MAX][MAX];
#endif
#ifdef HASH_REV
HASH_CODE g1[MAX][MAX];
#ifdef HASH_DOUBLE
HASH_CODE g2[MAX][MAX];
#endif
#endif

#ifdef HASH_NETURAL
#define mm0(x, m) (x)
#define mm1(x, m) (x)
#define mm2(x, m) (x)
#else
#define mm0(x, m) (((x) % (m) + (m)) % (m))  // use for the uncertained x
#define mm1(x, m) (((x) + (m)) % (m))        // use while x must in [-m, inf)
#define mm2(x, m) ((x) % (m))                // use while x must in [0, inf)
#endif


void hash_init(int n) {
    px1[0] = 1, py1[0] = 1;
#ifdef HASH_DOUBLE
    px2[0] = 1, py2[0] = 1;
#endif
    for (int i = 0; i < n; i++) {
        px1[i + 1] = mm2(px1[i] * HX1, HM1);
        py1[i + 1] = mm2(py1[i] * HY1, HM1);
#ifdef HASH_DOUBLE
        px2[i + 1] = mm2(px2[i] * HX2, HM2);
        py2[i + 1] = mm2(py2[i] * HY2, HM2);
#endif
    }
}

void hash_it(const char s[MAX][MAX], int n, int m) {
    for (int i = 0; i <= n; i++) {
        h1[i][0] = 0;
#ifdef HASH_DOUBLE
        h2[i][0] = 0;
#endif
    }
    for (int j = 0; j <= m; j++) {
        h1[0][j] = 0;
#ifdef HASH_DOUBLE
        h2[0][j] = 0;
#endif
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            h1[i + 1][j + 1] = mm0((h1[i][j + 1] * HX1 + h1[i + 1][j] * HY1 + s[i][j] - mm2(h1[i][j] * HX1, HM1) * HY1), HM1);
#ifdef HASH_DOUBLE
            h2[i + 1][j + 1] = mm0((h2[i][j + 1] * HX2 + h2[i + 1][j] * HY2 + s[i][j] - mm2(h2[i][j] * HX2, HM2) * HY2), HM2);
#endif
        }
    }

#ifdef HASH_REV
    for (int i = n + 1; i >= 1; i--) {
        g1[i][m + 1] = 0;
#ifdef HASH_DOUBLE
        g2[i][m + 1] = 0;
#endif
    }
    for (int j = m + 1; j >= 1; j--) {
        g1[n + 1][j] = 0;
#ifdef HASH_DOUBLE
        g2[n + 1][j] = 0;
#endif
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            g1[i + 1][j + 1] = mm0((g1[i + 2][j + 1] * HX1 + g1[i + 1][j + 2] * HY1 + s[i][j] - mm2(g1[i + 2][j + 2] * HX1, HM1) * HY1), HM1);
#ifdef HASH_DOUBLE
            g2[i + 1][j + 1] = mm0((g2[i + 2][j + 1] * HX2 + g2[i + 1][j + 2] * HY2 + s[i][j] - mm2(g2[i + 2][j + 2] * HX2, HM2) * HY2), HM2);
#endif
        }
    }
#endif
}

// 截取子矩阵哈希. 0-index, 左闭右闭
inline int hash_sub(int x, int y, int xx, int yy, bool reverse = false) {
    if (x > xx) swap(x, xx);
    if (y > yy) swap(y, yy);
#ifdef HASH_REV
    if (reverse) {
        x++, y++, xx += 2, yy += 2;
        int s1 = mm0((g1[x][y] - g1[xx][y] * px1[xx - x] - g1[x][yy] * py1[yy - y] + mm2(g1[xx][yy] * px1[xx - x], HM1) * py1[yy - y]), HM1);
#ifdef HASH_DOUBLE
        int s2 = mm0((g2[x][y] - g2[xx][y] * px2[xx - x] - g2[x][yy] * py2[yy - y] + mm2(g2[xx][yy] * px2[xx - x], HM2) * py2[yy - y]), HM2);
        return s1 * HM2 + s2;
#else
        return s1;
#endif
    }
#endif
    xx++, yy++;
    int s1 = mm0((h1[xx][yy] - h1[x][yy] * px1[xx - x] - h1[xx][y] * py1[yy - y] + mm2(h1[x][y] * px1[xx - x], HM1) * py1[yy - y]), HM1);
#ifdef HASH_DOUBLE
    int s2 = mm0((h2[xx][yy] - h2[x][yy] * px2[xx - x] - h2[xx][y] * py2[yy - y] + mm2(h2[x][y] * px2[xx - x], HM2) * py2[yy - y]), HM2);
    return s1 * HM2 + s2;
#else
    return s1;
#endif
}

// 判断是否为回文串. 0-index, 左闭右闭
#ifdef HASH_REV
inline bool is_central_symmetry(int x, int y, int xx, int yy) {
    return hash_sub(x, y, xx, yy) == hash_sub(x, y, xx, yy, true);
}
#endif

// 获取以 (x, y) 为中心的最大中心对称正方形. 0-index, odd: 为奇中心对称矩阵, 否则 (x, y) 表示偶回文子串的左上偏中心
#ifdef HASH_REV
inline int largest_central_symmetry_square(int x, int y, int n, int m, bool odd = true) {
    int l = 0, r = min({x, y, n - 1 - x - (int)(not odd), m - 1 - y - (int)(not odd)});
    while (l <= r) {
        int m = l + r >> 1;
        if (is_central_symmetry(x - m, y - m, x + m + (int)(not odd), y + m + (int)(not odd))) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return r + 1;
}
#endif

char a[MAX][MAX];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < m; j++) {
            char &x = a[i][j];
            // 因为数据可以把我的单哈卡掉，所以使用了一些打乱，简单说哈希要过就要乱搞
            if (x == 'k') x = 'b';
            else if (x == 'b') x = 'k';
            if (x == 'l') x = 'y';
            else if (x == 'y') x = 'l';
        }
    }
    hash_it(a, n, m);
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            res += largest_central_symmetry_square(i, j, n, m);
            res += largest_central_symmetry_square(i, j, n, m, false);
        }
    }
    cout << res << endl;
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);

    hash_init(MAX - 1);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif
    return 0;
}

解题思路（二）

  • 考虑使用二维 Manacher，这是一个 O(n2)O(n^2) 的解法。实际上二维 Manacher 依然需要用到二维哈希，所以请先阅读第一篇题解。
  • 首先枚举每行，对每行单独跑一次 Manacher ，需要注意的是只需把 Manacher 中的比较环节改为中心对称矩阵的判定即可。原版 Manacher 的判定环节提供了中心 i 和半径 r，并且保证了中心 i 和半径 r-1 的串为回文串，而且这一性质是由上一次该判定环节提供的，因此我们每次只需要判定 s[i−l]=s[i+r]s[i-l] = s[i+r] 即可。那么在本题每次单独跑 Manacher 时，我们只需要将判定改为判定中心 i 和半径 r （切比雪夫距离）的正方形外部环满足中心对称，由于有了哈希这一工具，我们直接判定该正方形中心对称即可， hash[x1..x2][y1..y2]==hash′[x1..x2][y1..y2]hash[x_1..x_2][y_1..y_2] == hash'[x_1..x_2][y_1..y_2] 。

代码（二）

  • 实测 3.3s 也比单哈快不了多少，可能是应为哈希比较方便编译器优化吧，还是我代码写臭了？
  • 注意上个解法使用了单哈，因为哈希函数被调用了 O(n2logn)O(n^2logn) 次，但正确性没有保障；这次可以放心使用，因为哈希函数只被调用了 O(n2)O(n^2) 次。
  • 前面 170 行都是哈希函数，请在文中找到 分割线 然后继续阅读。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
// Beautiful Matrix
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1  // Test Switch
#else
// #define TEST 1
#define LOCAL 1  // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 4005;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

#define HASH_DOUBLE  // 双哈开关
// #define HASH_NETURAL  // 自然溢出哈希开关
#define HASH_REV  // 逆序开关

#ifdef HASH_NETURAL
#define HASH_CODE uint64_t
#else
#define HASH_CODE int64_t
#endif

const int HX1 = 157, HY1 = 13331, HM1 = 1000000009;
#ifdef HASH_DOUBLE
const int HX2 = 131, HY2 = 10037, HM2 = 999999937;
#endif

HASH_CODE px1[MAX];
HASH_CODE py1[MAX];
HASH_CODE h1[MAX][MAX];
#ifdef HASH_DOUBLE
HASH_CODE px2[MAX];
HASH_CODE py2[MAX];
HASH_CODE h2[MAX][MAX];
#endif
#ifdef HASH_REV
HASH_CODE g1[MAX][MAX];
#ifdef HASH_DOUBLE
HASH_CODE g2[MAX][MAX];
#endif
#endif

#ifdef HASH_NETURAL
#define mm0(x, m) (x)
#define mm1(x, m) (x)
#define mm2(x, m) (x)
#else
#define mm0(x, m) (((x) % (m) + (m)) % (m))  // use for the uncertained x
#define mm1(x, m) (((x) + (m)) % (m))        // use while x must in [-m, inf)
#define mm2(x, m) ((x) % (m))                // use while x must in [0, inf)
#endif

void hash_init(int n) {
    px1[0] = 1, py1[0] = 1;
#ifdef HASH_DOUBLE
    px2[0] = 1, py2[0] = 1;
#endif
    for (int i = 0; i < n; i++) {
        px1[i + 1] = mm2(px1[i] * HX1, HM1);
        py1[i + 1] = mm2(py1[i] * HY1, HM1);
#ifdef HASH_DOUBLE
        px2[i + 1] = mm2(px2[i] * HX2, HM2);
        py2[i + 1] = mm2(py2[i] * HY2, HM2);
#endif
    }
}

void hash_it(const char s[MAX][MAX], int n, int m) {
    for (int i = 0; i <= n; i++) {
        h1[i][0] = 0;
#ifdef HASH_DOUBLE
        h2[i][0] = 0;
#endif
    }
    for (int j = 0; j <= m; j++) {
        h1[0][j] = 0;
#ifdef HASH_DOUBLE
        h2[0][j] = 0;
#endif
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            h1[i + 1][j + 1] = mm0((h1[i][j + 1] * HX1 + h1[i + 1][j] * HY1 + s[i][j] - mm2(h1[i][j] * HX1, HM1) * HY1), HM1);
#ifdef HASH_DOUBLE
            h2[i + 1][j + 1] = mm0((h2[i][j + 1] * HX2 + h2[i + 1][j] * HY2 + s[i][j] - mm2(h2[i][j] * HX2, HM2) * HY2), HM2);
#endif
        }
    }

#ifdef HASH_REV
    for (int i = n + 1; i >= 1; i--) {
        g1[i][m + 1] = 0;
#ifdef HASH_DOUBLE
        g2[i][m + 1] = 0;
#endif
    }
    for (int j = m + 1; j >= 1; j--) {
        g1[n + 1][j] = 0;
#ifdef HASH_DOUBLE
        g2[n + 1][j] = 0;
#endif
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            g1[i + 1][j + 1] = mm0((g1[i + 2][j + 1] * HX1 + g1[i + 1][j + 2] * HY1 + s[i][j] - mm2(g1[i + 2][j + 2] * HX1, HM1) * HY1), HM1);
#ifdef HASH_DOUBLE
            g2[i + 1][j + 1] = mm0((g2[i + 2][j + 1] * HX2 + g2[i + 1][j + 2] * HY2 + s[i][j] - mm2(g2[i + 2][j + 2] * HX2, HM2) * HY2), HM2);
#endif
        }
    }
#endif
}

// 截取子矩阵哈希. 0-index, 左闭右闭
inline int hash_sub(int x, int y, int xx, int yy, bool reverse = false) {
    if (x > xx) swap(x, xx);
    if (y > yy) swap(y, yy);
#ifdef HASH_REV
    if (reverse) {
        x++, y++, xx += 2, yy += 2;
        int s1 = mm0((g1[x][y] - g1[xx][y] * px1[xx - x] - g1[x][yy] * py1[yy - y] + mm2(g1[xx][yy] * px1[xx - x], HM1) * py1[yy - y]), HM1);
#ifdef HASH_DOUBLE
        int s2 = mm0((g2[x][y] - g2[xx][y] * px2[xx - x] - g2[x][yy] * py2[yy - y] + mm2(g2[xx][yy] * px2[xx - x], HM2) * py2[yy - y]), HM2);
        return s1 * HM2 + s2;
#else
        return s1;
#endif
    }
#endif
    xx++, yy++;
    int s1 = mm0((h1[xx][yy] - h1[x][yy] * px1[xx - x] - h1[xx][y] * py1[yy - y] + mm2(h1[x][y] * px1[xx - x], HM1) * py1[yy - y]), HM1);
#ifdef HASH_DOUBLE
    int s2 = mm0((h2[xx][yy] - h2[x][yy] * px2[xx - x] - h2[xx][y] * py2[yy - y] + mm2(h2[x][y] * px2[xx - x], HM2) * py2[yy - y]), HM2);
    return s1 * HM2 + s2;
#else
    return s1;
#endif
}

// 判断是否为回文串. 0-index, 左闭右闭
#ifdef HASH_REV
inline bool is_central_symmetry(int x, int y, int xx, int yy) {
    return hash_sub(x, y, xx, yy) == hash_sub(x, y, xx, yy, true);
}
#endif

// ================================================================================

char a[MAX][MAX];
char b[MAX][MAX];
int p[MAX][MAX];

void zoom(int n, int m) {
    for (int i = 0; i <= 2 * n; i++) {
        for (int j = 0; j <= 2 * m; j++) {
            b[i][j] = '#';
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            b[2 * i + 1][2 * j + 1] = a[i][j];
        }
    }
}

inline bool check(int x, int y, int r) {
    return is_central_symmetry(x - r, y - r, x + r, y + r);
}

void manacher(const char s[MAX][MAX], int n, int m) {
    for (int i = 0; i < n; i++) {
        int right_radius = -1, right_center = -1;
        for (int j = 0; j < m; j++) {
            int r = 1;
            if (j < right_radius)
                if (p[i][2 * right_center - j] < right_radius - j)
                    r = p[i][2 * right_center - j];
                else
                    r = right_radius - j;
            else
                r = 1;
            while (0 <= j - r and j + r < m and 0 <= i - r and i + r < n)
                if (check(i, j, r))  // 二维 Manacher 只需要改这个地方，然后在外面套个遍历行
                    r++;
                else
                    break;
            p[i][j] = r - 1;
            if (j + r > right_radius) {
                right_radius = j + r;
                right_center = j;
            }
        }
    }
}

inline int largest_central_symmetry_square(int x, int y, bool odd = true) {
    return p[x * 2 + 1 + (int)(not odd)][y * 2 + 1 + (int)(not odd)];
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    zoom(n, m);
    n = n << 1 | 1, m = m << 1 | 1;
    hash_it(b, n, m);
    manacher(b, n, m);
    int res = 0;
    n >>= 1, m >>= 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            res += (largest_central_symmetry_square(i, j) + 1) / 2;
            res += largest_central_symmetry_square(i, j, false) / 2;
        }
    }
    cout << res << endl;
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);

    hash_init(MAX - 1);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif
    return 0;
}