题目链接：Codeforces 1228 E

你有一个 $n \times n$ 的网格和一个整数 $k$，在每个格子中都填入一个整数，满足如下条件：

• 所有格子中的整数都介于 $1$ 到 $k$ 之间。
• 第 $i$ 行的最小值为 $1$（$1 \le i \le n$）。
• 第 $j$ 列的最小值为 $1$（$1 \le j \le n$）。

请求出填数的方案数，答案对 $10 ^ {9} + 7$ 取模。

数据范围：$1 \le n \le 250$，$1 \le k \le 10 ^ {9}$。

Solution

算法 1

设 $f(i, j)$ 表示已经填完了前 $i$ 行，有 $j$ 列已经包含 $1$ 了。枚举上一行填了 $k$ 个 $1$ 则有：

• $f(0, 0) = 1$。
• $f(i, j) = f(i - 1, j) \cdot \left (k ^ {j} - (k - 1) ^ {j} \right ) \cdot (k - 1) ^ {n - j}$，其中第二项表示这 $j$ 个位置至少需要有一个 $1$，则可以用全集减去补集表示。
• $f(i, j) = f(i - 1, k) \cdot \binom{n - k}{j - k} \cdot (k - 1) ^ {n - j}$ 其中 $0 \le k < j$。

时间复杂度：$\mathcal O(n ^ 3)$。

算法 2

考虑容斥。我们枚举至少 $i$ 行和 $j$ 列没有 $1$。那么答案为：

$$ \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {n} (-1) ^ {i + j} \binom{n}{i} \cdot \binom{n}{j} \cdot (k - 1) ^ {n(i + j) - ij} \cdot k ^ {(n - i)(n - j)} \tag{1} $$

时间复杂度：$\mathcal O(n ^ {2}) \sim \mathcal O(n ^ {2} \log n)$。

算法 3

我们对 $(1)$ 进行化简，具体方法为：对第二重 $j$ 求和根据二项式定理展开，最终得到的式子为：

$$ \sum_{i = 0} ^ {n} (-1) ^ {i} \cdot \binom{n}{i} \cdot \left (k ^ {n-i} \cdot (k - 1) ^ {i} - (k - 1) ^ {n} \right ) ^ {n} $$

时间复杂度：$\mathcal O(n \log n)$。

Code

算法 1

#include <cstdio>

const int N = 250;
const int MOD = 1e9 + 7;

int n, k, p[N + 5], q[N + 5], c[N + 5][N + 5], f[N + 5][N + 5];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
int add(int x) {
    return x >= MOD ? x - MOD : x;
}
int sub(int x) {
    return x < 0 ? x + MOD : x;
}
void init(int n) {
    p[0] = q[0] = c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = 1LL * p[i - 1] * k % MOD;
        q[i] = 1LL * q[i - 1] * (k - 1) % MOD;
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            c[i][j] = add(c[i - 1][j] + c[i - 1][j - 1]);
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    init(n);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k <= j; k++) {
                if (j == k) {
                    add(f[i][j], 1LL * f[i - 1][k] * sub(p[j] - q[j]) % MOD * q[n - j] % MOD);
                } else {
                    add(f[i][j], 1LL * f[i - 1][k] * p[k] % MOD * c[n - k][j - k] % MOD * q[n - j] % MOD);
                }
            }
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}

算法 2

#include <cstdio>

const int N = 250;
const int MOD = 1e9 + 7;

int n, k, fac[N + 5], ifac[N + 5], pw1[N * N + 5], pw2[N * N + 5];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
int pow(int x, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1, x = 1LL * x * x % MOD) {
        if ((k & 1) == 1) ans = 1LL * ans * x % MOD;
    }
    return ans;
}
int inv(int x) {
    return pow(x, MOD - 2);
}
int binom(int n, int m) {
    return n < m ? 0 : 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i <= n * n; i++) {
        pw1[i] = 1LL * pw1[i - 1] * (k - 1) % MOD;
        pw2[i] = 1LL * pw2[i - 1] * k % MOD;
    }
}
int main() {
    scanf("%d%d", &n, &k);
    init(n);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            int x = (n - i) * (n - j);
            int now = 1LL * binom(n, i) * binom(n, j) % MOD * pw1[n * n - x] % MOD * pw2[x] % MOD;
            (((i + j) & 1) == 0 ? add : sub)(ans, now);
        }
    }
    printf("%d\n", ans);
    return 0;
}

算法 3

#include <cstdio>

const int N = 250;
const int MOD = 1e9 + 7;

int n, k, fac[N + 5], ifac[N + 5], p[N + 5], q[N + 5];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
int mod(int x) {
    return x < 0 ? x + MOD : x >= MOD ? x - MOD : x;
}
int pow(int x, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1, x = 1LL * x * x % MOD) {
        if ((k & 1) == 1) ans = 1LL * ans * x % MOD;
    }
    return ans;
}
int inv(int x) {
    return pow(x, MOD - 2);
}
int binom(int n, int m) {
    return n < m ? 0 : 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
    p[0] = q[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = 1LL * p[i - 1] * k % MOD;
        q[i] = 1LL * q[i - 1] * (k - 1) % MOD;
    }
}
int main() {
    scanf("%d%d", &n, &k);
    init(n);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        int now = 1LL * binom(n, i) * pow(mod(1LL * q[i] * p[n - i] % MOD - q[n]), n) % MOD;
        ((i & 1) == 0 ? add : sub)(ans, now);
    }
    printf("%d\n", ans);
    return 0;
}