← 返回题目列表

AtCoder · agc023_b

B. 求对称性

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

Snuke 有两块板,每块板分为一个网格, N 行和 N 列。 对于这两个板,位于 i从顶部开始的第行和 j从左边算起的第列称为 Square (i,j).

第一块棋盘的每个方格内都写有一个小写英文字母。写在方格上的信 (i,j) is S_{i,j}。第二块板上还没有写任何东西。

Snuke会在第二块板上写下字母,如下:

  • 首先,选择两个整数 A 和 B ( 0 \leq A, B < N ).
  • 在第二块板上的每个方格中写一个字母。 具体来说,写下用 Square 写的字母 ( i+A, j+B ) 第一块板进入广场 (i,j) 在第二块板上。 在这里, k- 第行也表示为 (N+k)第行,以及 k第列也表示为 (N+k)- 第列。

执行此操作后,第二块板被称为 好 登机时,对于每 i 和 j ( 1 \leq i, j \leq N ),方格中的字母 (i,j) 和方格中的字母 (j,i) 相等。

求选择整数的方法数 A 和 B ( 0 \leq A, B < N )使得第二块板是一块好板。

约束

  • 1 \leq N \leq 300
  • S_{i,j} ( 1 \leq i, j \leq N ) 是一个小写英文字母。

输入

输入由标准输入按以下格式给出:

N
S_{1,1}S_{1,2}..S_{1,N}
S_{2,1}S_{2,2}..S_{2,N}
:
S_{N,1}S_{N,2}..S_{N,N}

输出

打印选择整数的方法数 A 和 B ( 0 \leq A, B < N )使得第二块板是一块好板。


示例输入 1

2
ab
ca

示例输出 1

2

对于每对 A 和 B,第二块板将如下所示:

第二块板是一块好板,当 (A,B) = (0,1) or (A,B) = (1,0),因此答案是 2.


示例输入 2

4
aaaa
aaaa
aaaa
aaaa

示例输出 2

16

每种可能的选择 A 和 B 使第二块板很好。


示例输入 3

5
abcde
fghij
klmno
pqrst
uvwxy

示例输出 3

0

无法选择 A 和 B 使第二块板很好。