以下の解説において、次の用語を用います。

• \(A_i\neq -1\) となる \(i\) に対して、\((i, A_i)\) を「禁止マス」と呼ぶ
• 禁止マス \((i, A_i)\) に対して \(P_i = A_i\) を満たす順列のことを、単に「順列」と呼ぶ
• どの禁止マスも通らない 経路のことを、単に「経路」と呼ぶ
• 順列 \(P\) と経路 \(X\) とマス \((i,j)\) に対して、\(P_i = j\) かつ \(X\) は \((i,j)\) を通るとき、「\(P\) と \(X\) は \((i,j)\) で衝突する」という

禁止マスの個数を \(K\) と書くことにします。また、行番号・列番号がともに \(1\) 以上 \(N\) 以下であるマス全体の集合を \(S\) と書くことにします。

---

◆包除原理の適用

計算対象 \(\sum_P f(P)\) は「順列 \(P\) と、経路 \(X\) の組合せ \((P, X)\) であって、どの \((i,j)\in S\) においても衝突しないものの個数」という形に読み替えることができます。これを包除原理により数えることにします。

\(T\subset S\) および順列 \(P\)、経路 \(X\) に対して、次の条件を衝突条件と呼ぶことにします。

• \((i,j)\in T\) ならば、\(P\) と \(X\) は \((i,j)\) において衝突している

固定した \(T\) に対して衝突条件を満たす \((T, P, X)\) の個数を \(g(T)\) と書けば、包除原理により、答は \(\sum_T (-1)^{|T|} g(T)\) です。

したがって、答を計算するためには、衝突条件を満たす組 \((T, P, X)\) の個数を \(|T|\) ごとに数えられればよいです。

---

◆\(P\) の数え上げ

衝突条件を満たす組 \((T, P, X)\) の数え上げ問題を考えていきます。\(T\subset S\) と経路 \(X\) の組 \((T, X)\) は、以下の条件を満たすとき valid であるということにします。

• \(T\subset X\)
• \(T\) は禁止マスと同じ行・列にあるマスは含まない
• \(T\) は同じ行・同じ列にある \(2\) マスを同時に含まない

valid ではない \((T, X)\) に対しては、衝突条件を満たす \((T, P, X)\) は存在しません。よって \((T, X)\) としては、valid なものだけを考えればよいです。

\((T, X)\) が valid なとき、衝突条件を満たす \((T, P, X)\) はいくつあるでしょうか？これは、互いに矛盾しない \(P_i = j\) の形の \(K + |T|\) 個の条件のもとでの順列の個数と等しいです。よって、その個数は \((N - K - |T|)!\) と計算できます。

特に \(P\) の個数は、\(|T|\) のみから定まります。結局、衝突条件を満たす組 \((T, P, X)\) を数え上げる問題は、valid な組 \((T, X)\) を \(|T|\) ごとに数え上げる問題に帰着されました。

---

◆dp による計算

valid な組 \((T, X)\) を \(|T|\) ごとに数え上げる問題を考えます。これは、次のような dp により計算できます。

• マス \((i,j)\) まで至る経路 \(X\) と、集合 \(T\subset S\cap X\) の組 \((T, X)\) であって、valid なもののうち、\(|T| = n\) を満たすものの個数を考える。
• このうちさらに、第 \(i\) 行から \(T\) の要素を選んだか、第 \(j\) 列から \(T\) の要素を選んだかに応じて \(2\) つの bool 値 \(\text{row}, \text{col}\in \{0,1\}\) を定める。
• そのような組 \((T, X)\)の個数を \(\text{dp}[i, j, n, \text{row}, \text{col}]\) として、これをマス \((i,j)\) に関する適当なトポロジカル順序により順に計算していく。

以上をまとめると、この問題は全体として \(O(N^3)\) 時間で解くことができることが分かります。