921 . 召喚大神 2

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

蔡兆豐
大家好，我是蔡兆豐。我們今天要介紹的書是我兒佳比。這本書是在講述一個名叫科。克萊爾的傳奇故事。他本來居住在童話社區，每個人都被要求。要一樣。

User's AC Ratio

87.5% (14/16)

Submission's AC Ratio

39.0% (23/59)

Tags

ioicamp ioicamp-2025

Description

小魚在做一道極其困難的題目，他已經做了好幾個月，但仍然做不出來。

「這題太難了啦，真希望有大神能助我一臂之力。」小魚自言自語地說道。

剛好路過的精靈小波聽到小魚的哀號聲，決定送給他一個神奇的道具。「試試看這個吧！」

精靈小波邊說邊遞給小魚一支筆。

「這支筆可不是一般的筆，只要用這支筆在地上畫出一個合法的魔法陣，就能召喚出大神來。」精靈小波解釋道。

「真的假的，謝謝你精靈小波。」小魚像是終於從枷鎖中解脫般不斷向精靈小波道謝。

一個合法的魔法陣是一個 $K \times K$ 的表格，其中 $K$ 可以是任意 $\geq 3$ 的正整數，同時每個格子上都有一個正整數。為了保證魔法陣能正常的啟動，還有幾個特殊的條件：

  • 四個角落的數字必須是相同的。
  • 在四個邊上且不是角落的 $4K − 8$ 個數字必須是相同的。
  • 剩下的所有數字都必須是相同的。

舉例來說，下圖兩個皆為可以正常啟動的魔法陣，特別注意到角落、邊界與內部的數字可以相同。

8118
1771
1771
8118
1111
1441
1441
1111


小魚他已經在地上畫了一個 $N \times M$ 表格，每個格子上都有一個正整數。但小魚患有選擇障礙症，他知道這個表格有很多子方陣是能正常啟動的合法魔法陣，但他不知道要選哪一個。請幫幫小魚計算有幾種子方陣是能正常啟動的合法魔法陣，兩種選法不同若且唯若兩個子方陣的大小不一樣，或是兩個矩陣的左上角的格子是從不同行或不同列來的。

Input Format

輸入第一行有兩個正整數 $N, M$，代表表格有幾個橫列與幾個直排。

接下來 $N$ 行，第 $i$ 行有 $M$ 個正整數 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, M}$，其中 $a_{i, j}$ 代表第 $i$ 個橫列的第 $j$ 格的數字是什麼。

  • $3 \leq N, M \leq 2000$
  • $1 \leq a_{i, j} \leq NM$

Output Format

請輸出一行，該行有一個整數代表有幾個子方陣是能正常啟動的合法魔法陣。

Sample Input 1

5 5
1 2 2 2 1
2 3 3 3 2
2 3 3 3 2
2 3 3 3 2
1 2 2 2 1

Sample Output 1

2

Sample Input 2

4 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output 2

8

Sample Input 3

6 7
2 1 2 1 2 1 1
1 1 1 1 1 2 1
2 1 2 1 2 1 2
1 2 1 2 1 2 1
1 1 1 1 1 1 1
1 2 1 2 1 2 1

Sample Output 3

5

Sample Input 4

10 10
1 2 2 1 1 7 3 3 3 7
2 1 1 2 1 3 2 2 2 3
2 1 1 2 7 3 2 2 2 3
1 2 2 5 1 3 2 2 2 3
1 1 5 5 1 7 3 3 3 7
1 7 1 1 7 1 6 4 4 6
7 5 7 1 1 1 4 8 8 4
5 2 5 7 4 7 4 8 8 4
7 5 7 4 1 4 6 4 4 6
1 1 1 7 4 7 1 1 1 1

Sample Output 4

5

Hints

Problem Source

NPSC 2023 國中組決賽 pF 改

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 4~8 $a_{i, j} = 1$ 5
3 9~18 $N = 3$ 3
4 0~3, 19~33 $1 \leq N, M \leq 50$ 10
5 0~3, 19~54 $1 \leq N, M \leq 500$ 26
6 4~8, 55~67 對於所有能正常啟動的合法魔法陣的子方陣，該子方陣內的數字皆相同 23
7 0~89 無額外限制 33

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1 4 5 7
1 3000 1048576 65536 1 4 5 7
2 3000 1048576 65536 1 4 5 7
3 3000 1048576 65536 1 4 5 7
4 3000 1048576 65536 2 6 7
5 3000 1048576 65536 2 6 7
6 3000 1048576 65536 2 6 7
7 3000 1048576 65536 2 6 7
8 3000 1048576 65536 2 6 7
9 3000 1048576 65536 3 7
10 3000 1048576 65536 3 7
11 3000 1048576 65536 3 7
12 3000 1048576 65536 3 7
13 3000 1048576 65536 3 7
14 3000 1048576 65536 3 7
15 3000 1048576 65536 3 7
16 3000 1048576 65536 3 7
17 3000 1048576 65536 3 7
18 3000 1048576 65536 3 7
19 3000 1048576 65536 4 5 7
20 3000 1048576 65536 4 5 7
21 3000 1048576 65536 4 5 7
22 3000 1048576 65536 4 5 7
23 3000 1048576 65536 4 5 7
24 3000 1048576 65536 4 5 7
25 3000 1048576 65536 4 5 7
26 3000 1048576 65536 4 5 7
27 3000 1048576 65536 4 5 7
28 3000 1048576 65536 4 5 7
29 3000 1048576 65536 4 5 7
30 3000 1048576 65536 4 5 7
31 3000 1048576 65536 4 5 7
32 3000 1048576 65536 4 5 7
33 3000 1048576 65536 4 5 7
34 3000 1048576 65536 5 7
35 3000 1048576 65536 5 7
36 3000 1048576 65536 5 7
37 3000 1048576 65536 5 7
38 3000 1048576 65536 5 7
39 3000 1048576 65536 5 7
40 3000 1048576 65536 5 7
41 3000 1048576 65536 5 7
42 3000 1048576 65536 5 7
43 3000 1048576 65536 5 7
44 3000 1048576 65536 5 7
45 3000 1048576 65536 5 7
46 3000 1048576 65536 5 7
47 3000 1048576 65536 5 7
48 3000 1048576 65536 5 7
49 3000 1048576 65536 5 7
50 3000 1048576 65536 5 7
51 3000 1048576 65536 5 7
52 3000 1048576 65536 5 7
53 3000 1048576 65536 5 7
54 3000 1048576 65536 5 7
55 3000 1048576 65536 6 7
56 3000 1048576 65536 6 7
57 3000 1048576 65536 6 7
58 3000 1048576 65536 6 7
59 3000 1048576 65536 6 7
60 3000 1048576 65536 6 7
61 3000 1048576 65536 6 7
62 3000 1048576 65536 6 7
63 3000 1048576 65536 6 7
64 3000 1048576 65536 6 7
65 3000 1048576 65536 6 7
66 3000 1048576 65536 6 7
67 3000 1048576 65536 6 7
68 3000 1048576 65536 7
69 3000 1048576 65536 7
70 3000 1048576 65536 7
71 3000 1048576 65536 7
72 3000 1048576 65536 7
73 3000 1048576 65536 7
74 3000 1048576 65536 7
75 3000 1048576 65536 7
76 3000 1048576 65536 7
77 3000 1048576 65536 7
78 3000 1048576 65536 7
79 3000 1048576 65536 7
80 3000 1048576 65536 7
81 3000 1048576 65536 7
82 3000 1048576 65536 7
83 3000 1048576 65536 7
84 3000 1048576 65536 7
85 3000 1048576 65536 7
86 3000 1048576 65536 7
87 3000 1048576 65536 7
88 3000 1048576 65536 7
89 3000 1048576 65536 7
Submit
Back to Top