Link
Solution
不知道怎么就想到了……用 (G(x,y)) 表示恰好有 (x) 和 (y) 行没有 (1)，那么答案就是 (G(0,0))
用 (F(x,y)) 表示强制有 (x) 行 (y) 列没有 (1) ，剩下的随便填的可重方案，那么
[F(x,y)=inom{n}{x}inom{n}{y}k^{(n-x)(n-y)} imes k^{n^2-(n-x)(n-y)}
]
组合意义为先选 (x) 行 (y) 列没有 (1) ，对于这选了的部分，除去不能选 (1)，那么共有 ((k-1)^{n^2-(n-x)(n-y)}) 种，对于没有选的，可以随便填数。
容易发现
[F(x,y)=sum_{i=x}^n sum_{j=y}^n inom{i}{x}inom{j}{y}G(i,j)
]
反演一下，得到
[G(x,y)=sum_{i=x}^n sum_{j=y}^n (-1)^{i+j-x-y} inom{i}{x}inom{j}{y} F(i,j)
]
代入 (x=0,y=0) ，答案即为
[sum_{i=0}^n sum_{j=0}^n (-1)^{i+j} inom{n}{i}inom{n}{j} k^{(n-i)(n-j)} imes k^{n^2-(n-i)(n-j)}
]
(O(n^2log n)) 暴力求解即可。