🔥

AGC023 B - Find Symmetries

2021/01/16に公開

問題概要

N×Nの行列が与えられる
この行列をA行、B列ずらして対称行列にしたい
A, Bとして考えられるものは何通りあるか

A, Bをすべてためそうとすると、
試すのに $N^2$ 、判定で $N^2$ かかって間に合わない

よくよく考えると、ある行列が対称行列ならば、
それを同じ行、同じ列ずらした行列も対称行列になることがわかる

つまりは全ての(i, j)について $A_{i, j} = B_{j, i}$ のとき
$A_{i+k \mod N, j+k \mod N} = B_{j+k \mod N, i+k \mod N}$ となる
これは直感的にわかる

よってA, Bが条件を満たすならば $A-B, 0 \pmod N$ も条件を満たすといえる
なので行をずらす処理をすべて試せばいい

ある $(A, 0)$ が条件を満たすのであれば $(A, 0), (A+1, 1), (A+2, 2), ... (A+N-1, N-1)$ (mod N略)のすべてが条件を満たすので
一つ条件を満たすものが見つかったときに答えに+Nすればいい