关于为什么有 $\gcd(r, c) = 1$ 的限制，考虑这相当于一个 $x + 1, x + 2, \dots, x + y(= n), 1, 2,\dots x$ 的排列（把相同行/列的视作同一个），注意到这个东西相当于 $i$ 向 $(i + x) \mod (x + y = n)$ 连边，且是把原来的一个环拆开所以显然只能有一个环。