Codeforces Round #589 (Div. 2) E. Another Filling the Grid dp/容斥

自以为dp水平很强，然后竟然一直想容斥写这题，没写出来是真的丢脸…
E. Another Filling the Grid

题意：有一个n*n的矩阵，矩阵每个位置你可以填1到k之间任何数，要求填完后每行至少有一个数字1，每列至少有一个数字1，问有多少种填数方案。

解法：设 $dp[i][j]$为填完了前 $i$行数，有 $j$列存在数字1的方案数，对于下一行的状态 $dp[i + 1][p]$，分两种情况：

一种是 $p=j$，即并没有增加新的存在数字1的列，那么 $j$个格子可以填任何数但是必须要有至少一个1，方案数为 $k^{j}-(k-1)^{j}$，剩余的 $n-j$个格子不能填1，方案数为 $(k-1)^{n-j}$，把这些数相乘记为 $res$，那么 $dp[i+1[p]+=dp[i][j]*res$

一种是 $p!=j$，因为新增了 $p-j$列存在数字1，那么原来的 $j$列可以填任意数，方案数为 $k^{j}$，新增的 $p-j$列可以用组合数求方案数： $C_{n-j}^{p-j}$，剩余 $n-p$个格子不能填1，方案数同上，后面亦同理

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
ll p[300], inv[300], d[255][255], P[300], P2[300];
ll ksm(ll x, int y) {
    ll res = 1;
    while (y) {
        if (y & 1)
            res = res * x % mod;
        x = x * x % mod;
        y /= 2;
    }
    return res;
}
void add(ll &x, ll y) {
    x += y;
    if (x >= mod)
        x -= mod;
    if (x < 0)
        x += mod;
}
ll C(int n, int m) {
    return p[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
    p[0] = inv[0] = 1;
    for (int i = 1; i <= 250; i++)
        p[i] = p[i - 1] * i % mod, inv[i] = ksm(p[i], mod - 2);
    int n, k;
    cin>>n>>k;
    P[0] = P2[0] = 1;
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] * k % mod;
        P2[i] = P2[i - 1] * (k - 1) % mod;
    }
    for (int i = 1; i <= n; i++)
        d[1][i] = C(n, i) * P2[n - i] % mod;
    for (int i = 2; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        for (int p = j; p <= n; p++) {
            ll res = C(n - j, p - j) * P2[n - p] % mod * P[j] % mod;
            if (j == p)
                res = (P[p] - P2[p] + mod) % mod * P2[n - p] % mod;
            add(d[i][p], d[i - 1][j] * res % mod);
        }
    }
    cout<<d[n][n];
}