容斥

给定一个 $N \times N$ 的正方形网格和一个整数 $K$。请计算有多少种合法的填数方案，满足所有数字都在 $1$ 到 $K$ 之间，且每行、每列的最小值均为 $1$。

• $f(i, j)$：恰好有 $i$ 行和 $j$ 列满足某种性质的方案数。
• $g(n, m)$：强制选定 $n$ 行和 $m$ 列，并让它们必须满足该性质，而对其余元素不作任何限制的方案数。

$$\begin{aligned} g(n, m) &= \sum_{i=n}^{N} \sum_{j=m}^{M} \binom{i}{n} \binom{j}{m} f(i, j) \\ f(n, m) &= \sum_{i=n}^{N} \sum_{j=m}^{M} (-1)^{(i-n) + (j-m)} \binom{i}{n} \binom{j}{m} g(i, j) \end{aligned}$$

本题中，

$$g(n, m) = \binom{N}{n} \binom{N}{m} (K-1)^{N^2 - (N-n)(N-m)} K^{(N-n)(N-m)}$$

欲求 $f(0, 0)$，直接代入计算即可。

$$f(0, 0) = \sum_{i=0}^{N} \sum_{j=0}^{N} (-1)^{i+j} \binom{N}{i} \binom{N}{j} (K-1)^{N^2 - (N-i)(N-j)} K^{(N-i)(N-j)}$$