Problem:


Score : 500 points

Problem Statement

Snuke has two boards, each divided into a grid with N rows and N columns.
For both of these boards, the square at the i-th row from the top and the j-th column from the left is called Square (i,j).

There is a lowercase English letter written in each square on the first board. The letter written in Square (i,j) is S_{i,j}. On the second board, nothing is written yet.

Snuke will write letters on the second board, as follows:

First, choose two integers A and B ( 0 \leq A, B < N ).

Write one letter in each square on the second board.
Specifically, write the letter written in Square ( i+A, j+B ) on the first board into Square (i,j) on the second board.
Here, the k-th row is also represented as the (N+k)-th row, and the k-th column is also represented as the (N+k)-th column.

After this operation, the second board is called a good board when, for every i and j ( 1 \leq i, j \leq N ), the letter in Square (i,j) and the letter in Square (j,i) are equal.

Find the number of the ways to choose integers A and B ( 0 \leq A, B < N ) such that the second board is a good board.

Constraints

1 \leq N \leq 300

S_{i,j} ( 1 \leq i, j \leq N ) is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

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}

Output

Print the number of the ways to choose integers A and B ( 0 \leq A, B < N ) such that the second board is a good board.

Sample Input 1

2
ab
ca

Sample Output 1

2

For each pair of A and B, the second board will look as shown below:

The second board is a good board when (A,B) = (0,1) or (A,B) = (1,0), thus the answer is 2.

Sample Input 2

4
aaaa
aaaa
aaaa
aaaa

Sample Output 2

16

Every possible choice of A and B makes the second board good.

Sample Input 3

5
abcde
fghij
klmno
pqrst
uvwxy

Sample Output 3

0

No possible choice of A and B makes the second board good.



Sample input:
2
ab
ca


Sample output:
2

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[list(input()) for i in range(N)]
def issym(IL):
    for i in range(N):
        for j in range(i+1,N):
            if IL[i][j]!=IL[j][i]:
                return False
    return True
def changelist(A,B):
    T=[["" for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            T[i][j]=S[(i+A)%N][(j+B)%N]
    return T
ans=0
for i in range(N):
    L=changelist(i,N-1-i)
    if issym(L):
        ans+=N
print(ans)

Submission status: Wrong Answer

Solution code:
# your code goes here
N = int(input())
S = [input() for i in range(N)]

ans = 0
for i in range(N):
	flag = 1
	for j in range(N-1):
		for k in range(j+1,N):
			if S[j][(k+i)%N] != S[(k+i)%N][j]:
				flag = 0
	if flag == 1:
		ans += N

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
s = np.array([list(input()) for _ in range(n)])

ans = 0
for i in range(n):
    t = np.append(s[i:], s[:i], axis=0)
    for j in range(n):
        u = np.append(t[:, j:], t[:, :j], axis=1)
        if np.array_equal(u, u.T):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# N <= 300 O(n ** 3)まで
# 何通り dp or combo
N = getN()
# 1つ目の譜面
B = []
for i in range(N):
    q = list(input())
    B.append(q * 2)
B += B
# 2つ目にはなにも書かれてない
# 2つ目の盤面に縦にi、横にjずらして数字を記入する

# 対角線に対して線対称なものの数を求める
# 整数a, bの選び方が何通りあるか

def judge(a, b):
    """
    res = [[''] * N for i in range(N)]
    # 盤面１のB[i][j]を盤面2に書き込む
    for i in range(N):
        for j in range(N):
            res[(i + a) % N][(j + b) % N] = B[i][j]
    """

    for i in range(N):
        for j in range(i, N):
            if B[i + a][j + b] != B[j + a][i + b]:
                return 0
        else:
            continue
        break
    else:
        return 1

# 全てのa, bについて調べるなら１つの(a, b)についてO(N)で求める必要がある
# 判定する際、節約出来ないか？

# N * N のゾーンをずらしていく
# a [b  a] b
# c [a  c] a
# a  b  a  b
# c  a  c  a 対称軸がずれる 軸は2N - 1本ある
# 良い盤面になる条件

# 斜めにずらしていくことで前の結果を利用できる
# 1本の軸について判定した時、1つの盤面が良い盤面なら他全ても良い盤面
# 軸に刺さっている盤面の数を求めればいい

# 軸は2N - 1本ある
# 縦に対角線をずらす
ans = 0
for i in range(N):
    # 軸(0, i)にはN - i本の盤面が連なっている
    # 連なっている全ての盤面は全てTrueか全てFalse
    ans += (N - i) * judge(i, 0)

# 横に対角線をずらす
for i in range(1, N):
    ans += (N - i) * judge(0, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# N <= 300 O(n ** 3)まで
# 何通り dp or combo
N = getN()
# 1つ目の譜面
B = [list(input()) for i in range(N)]
# 2つ目にはなにも書かれてない
# 2つ目の盤面に縦にi、横にjずらして数字を記入する

# 対角線に対して線対称なものの数を求める
# 整数a, bの選び方が何通りあるか

def judge(a, b):
    res = [[''] * N for i in range(N)]
    # 盤面１のB[i][j]を盤面2に書き込む
    for i in range(N):
        for j in range(N):
            res[(i + a) % N][(j + b) % N] = B[i][j]

    for i in range(N):
        for j in range(N):
            if res[i][j] != res[j][i]:
                return 0
        else:
            continue
        break
    else:
        return 1

# 全てのa, bについて調べるなら１つの(a, b)についてO(N)で求める必要がある
# 判定する際、節約出来ないか？

# N * N のゾーンをずらしていく
# a [b  a] b
# c [a  c] a
# a  b  a  b
# c  a  c  a 対称軸がずれる 軸は2N - 1本ある
# 良い盤面になる条件

# 斜めにずらしていくことで前の結果を利用できる
# 1本の軸について判定した時、1つの盤面が良い盤面なら他全ても良い盤面
# 軸に刺さっている盤面の数を求めればいい

# 軸は2N - 1本ある
# 縦に対角線をずらす
ans = 0
for i in range(N):
    # 軸(0, i)にはN - i本の盤面が連なっている
    # 連なっている全ての盤面は全てTrueか全てFalse
    ans += (N - i) * judge(i, 0)

# 横に対角線をずらす
for i in range(1, N):
    ans += (N - i) * judge(0, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 最も単純にやると
# 盤面の移動のしかたはN^2通り
# それぞれに対して、対称行列かの判定はO(N^2)個の条件を確認する必要がある
# したがってO(N^4)である。間に合わない。
# しかし、対称行列であれば、1行1列を右下に移動しても対称行列である。
# これより、行またはだけを移動した場合について確認すれば良い。O(N^3)。

n = int(input())
masume = [input() for i in range(n)]

count = 0
for diff in range(n):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            if masume[(i+diff)%n][j] != masume[(j+diff)%n][i]:
                flag = False
                break
        if not flag:
            break
    count += flag

print(count * n)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [list(input()) for i in range(n)]
ans = 0
for a in range(n):
    check = True
    for x in range(n):
        for y in range(x):
            if s[(x+a)%n][y] != s[(y+a)%n][x]:
                check = False
                break
        if check == False:
            break
    if check:
        ans += n
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [list(input()) for i in range(n)]
count = [0]*26
for i in s:
    for j in i:
        count[ord(j)-ord("a")] += 1
if max(count) == n**2:
    print(n**2)
    exit()
ans = 0
for a in range(n):
    for b in range(n):
        check = True
        for x in range(n):
            for y in range(x):
                if s[(x+a)%n][(y+b)%n] != s[(y+a)%n][(x+b)%n]:
                    check = False
                    break
            if check == False:
                break
        if check:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list()
for i in range(N):
  L.append(list(input())*2)
L=L*2
ans=0
for o in range((2*N)-1):
  a=0
  if o<N:
    i=0
    j=o
    omomi=N-j
  else:
    j=0
    i=o-N+1
    omomi=N-i
  for t in range(N):
    for q in range(t):
      if L[i+t][j+q]!=L[i+q][j+t]:
        a=1
        break
    if a==1:
      break
  if a==0:
    ans+=omomi
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list()
for i in range(N):
  L.append(list(input())*2)
L=L*2
ans=0
for i in range(N):
  for j in range(N):
    a=0
    for t in range(N):
      for q in range(t):
        if L[i+t][j+q]!=L[i+q][j+t]:
          a=1
          break
      if a==1:
        break
    if a==0:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline

def chr2ord(c):
  return ord(c) - ord('a')

N = int(input())
S = []
for i in range(N):
  wk = list(input())
  S.append(wk)

ANS = 0
# A=0として、0<=B<Nをためす。
# こたえはN倍。
for b in range(N):
  cnt = 0
  B = [['X' for _ in range(N)] for _ in range(N)]
  for i in range(N):
    for j in range(N):
      B[i][j] = S[i][(j+b)%N]
  #print(B)
  for i in range(N):
    for j in range(N):
      if B[i][j] == B[j][i]:
        cnt += 1
  
  if cnt == N*N:
    ANS += N
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8


def run():
    N = int(input())
    S_ = []

    for i in range(N):
        s = input()
        s = [ord(ss)-96 for ss in s] * 2
        S_.append(s)

    #for s in S_:
    #    print(s)
    S = []
    for s in S_:
        S.append(s)
    for s in S_:
        S.append(s)

    #for s in S:
    #    print(s)


    axises = [(i, 0) for i in range(N)]
    for i in range(1, N):
        axises.append((0, i))

    ans = 0

    #print(axises)
    for axis in axises:
        ci, cj = axis
        done = False
        for i in range(N):
            if done:break
            for j in range(i, N):
                if S[ci+i][cj+j] == S[ci+j][cj+i]:continue
                else:
                    #print((ci, cj), (i, j))
                    done=True
                    break
        if not done:
            ans += min(N-ci, N-cj)


    print(ans)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
from numba import jit

INF = 1 << 50
EPS = 1e-8
@jit
def solve(S):
    count = 0
    N, _ = S.shape
    N //= 2
    #print(N)
    #print(S.shape)
    #print(S)
    for i in range(N):
        for j in range(N):
            cut_S = S[i:i+N, j:j+N]
            #print(cut_S)
            if (cut_S == cut_S.T).all():
                count+=1
    return count



def run():
    N = int(input())
    S = []

    for i in range(N):
        s = input()
        s = [ord(ss)-96 for ss in s]
        S.append(s)
    S = np.array(S, dtype=np.int32)

    S = np.tile(S, (2,2))
    print(solve(S))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n = ni()
    mat = [list(sys.stdin.readline()) for _ in range(n)]

    ans = 0
    for i in range(n):
        tmp = [[mati[(i + j) % n] for j in range(n)] for mati in mat]
        flg = True
        for y in range(n):
            for x in range(n):
                if tmp[y][x] != tmp[x][y]:
                    flg = False
        ans += flg * n
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = [list(input()) for _ in range(N)]
ans = 0

for A in range(N):
    sym = True
    for i in range(N):
        for j in range(i+1, N):
            if S[(i+A)%N][j] != S[(j+A)%N][i]:
                sym = False
                break
        else:
            continue
        break
    if sym:
        ans += N

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
S = [list(input()) for _ in range(N)]
ans = 0

for A in range(N):
    sym = True
    for i in range(N):
        for j in range(i+1, N):
            if S[(i+A)%N][j] != S[(j+A)%N][i]:
                sym = False
                break
        else:
            continue
        break
    if sym:
        ans += N

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
S = [list(input()) for _ in range(N)]
S = copy.copy(S) + copy.copy(S)
ans = 0

for A in range(N):
    sym = True
    for i in range(N):
        for j in range(i+1, N):
            if S[i+A][j] != S[j+A][i]:
                sym = False
                break
        else:
            continue
        break
    if sym:
        ans += N

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s - ord('a') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    grid = in_map2(N)

    cnt = 0
    for i in range(N):
        tmp_grid = [[0] * N for _ in range(N)]
        for y in range(N):
            for x in range(N):
                tmp_grid[(y + i) % N][x] = grid[y][x]

        # print(tmp_grid)

        flag = True
        for y in range(N):
            for x in range(N):
                if tmp_grid[y][x] != tmp_grid[x][y]:
                    flag = False

        if flag:
            cnt += N

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	G=[]
	for _ in range(n):
		s=input().rstrip().decode()
		G.append(list(s*2))

	ans=0
	for x in range(n):
		f=1
		for i in range(n):
			if f==0:
				break
			for j in range(n):
				#print(i,j)
				if G[i][j]!=G[j-x][i+x]:
					f=0
					break
		else:
			#print(x)
			ans+=n
	print(ans)










if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
fs = []
for _ in range(n):
    r = list(input())
    r = [ord(s) - ord("a") for s in r]    
    fs.append(r)
fs = np.array(fs)
sym = np.zeros((n,n))
cnt = 0
# di,dj とdi+1,dj+1が同値
# dj側は0で固定して良い
for di in range(n):
    for i in range(n):
        for j in range(n):
            sym[(i+di)%n][j] = fs[i][j]
    flg = True
    for i in range(n):
        for j in range(i+1,n):
            if sym[i][j] != sym[j][i]:
                flg = False
                break
    if flg:
        cnt += n
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
fs = []
for _ in range(n):
    r = list(input())
    r = [ord(s) - ord("a") for s in r]    
    fs.append(r)
fs = np.array(fs)
sym = np.zeros((n,n))
cnt = 0
# di,dj とdi+1,dj+1が同値
# dj側は0で固定して良い
for di in range(n):
    for i in range(n):
        for j in range(n):
            sym[(i+di)%n][j] = fs[i][j]
    if (sym == sym.T).all():
        cnt += n
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# 愚
import numpy as np
n = int(input())
fs = []
for _ in range(n):
    r = list(input())
    r = [ord(s) - ord("a") for s in r]    
    fs.append(r)
fs = np.array(fs)
sym = np.zeros((n,n))
cnt = 0
for di in range(n):
    for dj in range(n):
        for i in range(n):
            for j in range(n):
                sym[(i+di)%n][(j+dj)%n] = fs[i][j]
        if (sym == sym.T).all():
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def check(N, S, a, b):
    nS = [[S[(i+a)%N][(j+b)%N] for j in range(N)] for i in range(N)]
    return all(all(e==te for e, te in zip(l, tl)) for l, tl in zip(nS, zip(*nS)))

def solve(N: int, S: "List[str]"):
    ans = 0
    for a in range(N):
        if check(N, S, a, 0):
            ans += N
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    print(solve(N, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
  for j in range(n):
    a=ss[i:i+n,j:j+n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[list(input()) for _ in range(n)]
ss=[si+si for si in s]
ss=ss+ss
ans=0
for i in range(n):
  for j in range(n):
    a=[si[j:j+n] for si in ss[i:i+n]]
    flg=True
    for k in range(n-1):
      a1=a[k][k+1:]
      a2=[a[i+1][k] for i in range(k,n-1)]
      if a1!=a2:
        flg=False
        break
    if flg:ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[list(input()) for _ in range(n)]
ss=[si+si for si in s]
ss=ss+ss
ans=0
for i in range(n):
  for j in range(n):
    a=[si[j:j+n] for si in ss[i:i+n]]
    flg=True
    for k in range(n):
      for l in range(n):
        if a[k][l]!=a[l][k]:
          flg=False
          break
      if not flg:
        break
    if flg:ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[input()for _ in range(n)]
def check(s,t):
  for i in range(n):
    for j in range(n):
      if s[(i+t)%n][j]!=s[(j+t)%n][i]:return False
  return True
ans=0
for i in range(n):
  if check(s,i):ans+=n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[input()for _ in range(n)]
def check(s):
  for i in range(n):
    for j in range(n):
      if s[i][j]!=s[j][i]:return False
  return True
ans=0
for i in range(n):
  if check(s):ans+=n
  s=s[1:]+s[:1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[[0] for _ in range(n)]
for i in range(n):
    s[i]=input()

ans=0
for p in range(n):
    cnt=0
    t=[[0] for _ in range(n)]
    for i in range(n):
        t[i]=s[(i+p)%n]
    for r in range(n):
        for l in range(n):
            if t[r][l]==t[l][r]:
                cnt+=1
    if cnt==n**2:
        ans+=1
print(ans*n)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    S2 = [0]*N
    for i in range(N):
        S2[i] = input()
    ans = 0
    for k in range(N):
        cum = [[0]*(N+1) for _ in range(N+1)]
        for i in range(1,N+1):
            for j in range(1,N+1):
                cum[i][j] = cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]+(S2[i-1][j-1]==S2[(j-1+k)%N][(i-1-k)%N])
                if i==N and j==N:
                    ans += (cum[i][j]==N*N)*N
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    S2 = [0]*N
    for i in range(N):
        S2[i] = input()
    cum = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N)]
    ans = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(N):
                cum[k][i][j] = cum[k][i-1][j]+cum[k][i][j-1]-cum[k][i-1][j-1]+(S2[i-1][j-1]==S2[(j-1+k)%N][(i-1-k)%N])
    for k in range(N):
        ans += (cum[k][-1][-1]==N*N)*N
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    S2 = [0]*N
    for i in range(N):
        S2[i] = input()
    cum = [[[0]*(N+1) for _ in range(N+1)] for _ in range(2*N)]
    ans = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(N):
                cum[k][i][j] = cum[k][i-1][j]+cum[k][i][j-1]-cum[k][i-1][j-1]+(S2[i-1][j-1]==S2[(j-1+k)%N][(i-1-k)%N])
    for k in range(-N+1,N):
        ans += (cum[k][-1][-1]==N*N)*N
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
    N = int(input())
    S2 = [0]*N
    for i in range(N):
        S2[i] = input()
    check = defaultdict(lambda: [[0]*(N+1) for _ in range(N+1)])
    cum = defaultdict(lambda: [[0]*(N+1) for _ in range(N+1)])
    for i in range(N):
        for j in range(N):
            for k in range(-N+1,i+1):
                check[k][i+1][j+1] = S2[i][j]==S2[(j+k)%N][(i-k)%N]
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(-N+1,N):
                cum[k][i][j] = cum[k][i-1][j]+cum[k][i][j-1]-cum[k][i-1][j-1]+check[k][i][j]
    ans = 0
    for k in range(-N+1,N):
        ans += (cum[k][-1][-1]==N*N)*N
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
    N = int(input())
    S2 = [0]*(2*N)
    for i in range(N):
        S2[i] = input()*2
        S2[i+N] = S2[i]
    check = defaultdict(lambda: [[0]*(2*N) for _ in range(2*N)])
    cum = defaultdict(lambda: [[0]*(2*N) for _ in range(2*N)])
    for i in range(2*N-1):
        for j in range(2*N-1):
            for k in range(max([-N+1,i+1-2*N,-j]),min([N,2*N-j,i+1])):
                check[k][i+1][j+1] = S2[i][j]==S2[j+k][i-k]
    for i in range(1,2*N):
        for j in range(1,2*N):
            for k in range(-N+1,N):
                cum[k][i][j] = cum[k][i-1][j]+cum[k][i][j-1]-cum[k][i-1][j-1]+check[k][i][j]
                if i>=N+1:
                    cum[k][i][j] -= check[k][i-N][j]
                if j>=N+1:
                    cum[k][i][j] -= check[k][i][j-N]
                if i>=N+1 and j>= N+1:
                    cum[k][i][j] += check[k][i-N][j-N]
    ans = 0
    for k in range(-N+1,0):
        A,B = -k+N,N
        while A<2*N:
            if cum[A-B][A][B]==N*N:
                ans += 1
            A += 1
            B += 1
    for k in range(N):
        A,B = N,k+N
        while B<2*N:
            if cum[A-B][A][B]==N*N:
                ans += 1
            A += 1
            B += 1
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    S2 = [0]*(2*N)
    for i in range(N):
        S2[i] = input()*2
        S2[i+N] = S2[i]
    check = [[[0]*(2*N) for _ in range(2*N)] for _ in range(2*N-1)]
    cum = [[[0]*(2*N) for _ in range(2*N)] for _ in range(2*N-1)]
    for i in range(2*N-1):
        for j in range(2*N-1):
            for k in range(-N+1,N):
                if j+k>=0 and j+k<=2*N-1 and i-k>=0 and i-k<=2*N-1:
                    check[k][i+1][j+1] = S2[i][j]==S2[j+k][i-k]
    for i in range(1,2*N):
        for j in range(1,2*N):
            for k in range(-N+1,N):
                cum[k][i][j] = cum[k][i-1][j]+cum[k][i][j-1]-cum[k][i-1][j-1]+check[k][i][j]
                if i>=N+1:
                    cum[k][i][j] -= check[k][i-N][j]
                if j>=N+1:
                    cum[k][i][j] -= check[k][i][j-N]
                if i>=N+1 and j>= N+1:
                    cum[k][i][j] += check[k][i-N][j-N]
    ans = 0
    for k in range(-N+1,0):
        A,B = -k+N,N
        while A<2*N:
            if cum[A-B][A][B]==N*N:
                ans += 1
            A += 1
            B += 1
    for k in range(N):
        A,B = N,k+N
        while B<2*N:
            if cum[A-B][A][B]==N*N:
                ans += 1
            A += 1
            B += 1
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve():
    N = int(input())
    S2 = [0]*(2*N)
    for i in range(N):
        S2[i] = input()*2
        S2[i+N] = S2[i]
    check = [[[0]*(2*N) for _ in range(2*N)] for _ in range(2*N-1)]
    cum = [[[0]*(2*N) for _ in range(2*N)] for _ in range(2*N-1)]
    for i in range(2*N-1):
        for j in range(2*N-1):
            for k in range(-N+1,N):
                if j+k>=0 and j+k<=2*N-1 and i-k>=0 and i-k<=2*N-1:
                    check[k][i+1][j+1] = S2[i][j]==S2[j+k][i-k]
    for i in range(1,2*N):
        for j in range(1,2*N):
            for k in range(-N+1,N):
                cum[k][i][j] = cum[k][i-1][j]+cum[k][i][j-1]-cum[k][i-1][j-1]+check[k][i][j]
                if i>=N+1:
                    cum[k][i][j] -= check[k][i-N][j]
                if j>=N+1:
                    cum[k][i][j] -= check[k][i][j-N]
                if i>=N+1 and j>= N+1:
                    cum[k][i][j] += check[k][i-N][j-N]
    ans = 0
    for k in range(-N+1,0):
        A,B = -k+N,N
        while A<2*N:
            if cum[A-B][A][B]==N*N:
                ans += 1
            A += 1
            B += 1
    for k in range(N):
        A,B = N,k+N
        while B<2*N:
            if cum[A-B][A][B]==N*N:
                ans += 1
            A += 1
            B += 1
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve():
    N = int(input())
    S2 = [0]*(2*N)
    for i in range(N):
        S2[i] = input()*2
        S2[i+N] = S2[i]
    check = np.zeros((2*N-1,2*N-1,2*N-1))
    cum = np.zeros((2*N-1,2*N,2*N))
    for i in range(2*N-1):
        for j in range(2*N-1):
            for k in range(-N+1,N):
                if j+k>=0 and j+k<=2*N-1 and i-k>=0 and i-k<=2*N-1:
                    check[k,i,j] = S2[i][j]==S2[j+k][i-k]
    for i in range(1,2*N):
        for j in range(1,2*N):
            for k in range(-N+1,N):
                cum[k,i,j] = cum[k,i-1,j]+cum[k,i,j-1]-cum[k,i-1,j-1]+check[k,i-1,j-1]
                if i>=N+1:
                    cum[k,i,j] -= check[k,i-N-1,j-1]
                if j>=N+1:
                    cum[k,i,j] -= check[k,i-1,j-N-1]
                if i>=N+1 and j>= N+1:
                    cum[k,i,j] += check[k,i-N-1,j-N-1]
    ans = 0
    for k in range(-N+1,0):
        A,B = -k+N,N
        while A<2*N:
            if cum[A-B,A,B]==N*N:
                ans += 1
            A += 1
            B += 1
    for k in range(N):
        A,B = N,k+N
        while B<2*N:
            if cum[A-B,A,B]==N*N:
                ans += 1
            A += 1
            B += 1
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
  S=input()
  A.append(S)
ans=0
for i in range(N):
  x=0
  for j in range(N):
    for k in range(N):      
      if A[j][k-i]!=A[k][j-i]:
        x=1
  if x==0:
    ans+=1
print(ans*N)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [input() for _ in range(n)]
    ans = 0
    for j in range(n):
        f = True
        for i in range(n-1):
            for k in range(i+1, n):
                if a[(0+i)%n][(j+k)%n] != a[(0+k)%n][(j+i)%n]:
                    f = False
                    break
            if not f:
                break
        if f:
            ans += n
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [input() for _ in range(n)]
    ans = 0
    for j in range(n):
        f = True
        for i in range(n):
            for k in range(n):
                if a[(0+i)%n][(j+k)%n] != a[(0+k)%n][(j+i)%n]:
                    f = False
                    break
            if not f:
                break
        if f:
            ans += n
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [input() for _ in range(n)]
    ans = 0
    for i in range(n):
        a[i] += a[i][:-1]
    for j in range(n):
        f = True
        for i in range(n):
            for k in range(n):
                if a[0+i][j+k] != a[0+k][j+i]:
                    f = False
                    break
            if not f:
                break
        if f:
            ans += n
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n = int(input())
a = np.array([list(input().rstrip()) for i in range(n)])
ans = 0
for i in range(n):
  c = np.roll(a,i,axis=0)
  for j in range(n):
    d = np.roll(c,j,axis=1)
    if np.array_equal(d,d.T):
      ans += 1
print(ans)