Matrix is Fun (Розбір)

Розв'язок Зсуви ніколи не змішують стовпці, тож кожен стовпець незалежний. Стовпець $j$ має в підсумку містити j+1,\,j+1+m,\,\dots,\,j+1+(n-1)m, а циклічний зсув лише зберігає циклічний порядок, тому він є Perfect тоді й лише тоді, коли є ротацією цієї прогресії. Якщо повернути мінімальний елемент нагору, це канонізує стовпець, тож достатньо й необхідно перевірити, що всі сусідні різниці дорівнюють $m$ і що (col_0-1)\bmod m=j. Складність O(n\cdot m).

def solve():
    n,m=map(int,input().split())
    a=[list(map(int,input().split())) for _ in range(n)]
    ans=0
    for j in range(m):
        col=[a[i][j] for i in range(n)]
        p=min(range(n),key=col.__getitem__)
        col=col[p:]+col[:p]
        ok=((col[0]-1)%m==j and all(col[i+1]-col[i]==m for i in range(n-1)))
        if(ok):
            ans+=1
    print(ans)
        
for _ in range(int(input())):
    solve()