Codeforces1228E Another Filling the Grid

发表于 | 更新于 | 分类于 | 阅读次数：

Codeforces1228E Another Filling the Grid

Description

给定一个$n \times n(1 \le n \le 250)$的矩阵，用$1 \sim k(1 \le k \le 10 ^ 9)$的数进行填充，每行每列最小值为$1$

求方案数

Solution

$f(i, j)$为至少有$i$行$j$列没有$1$的方案数

没有$1$的位置有$n (i + j) - i \cdot j$个，随便填的位置有$n ^ 2 - n(i + j) + i \cdot j$个

考虑全集$U$，即全部随便填，方案数为$k^{n ^ 2}$，即$f(0, 0)$

但这样不满足限制，需减去至少有一行或一列没有$1$的方案数，以满足一行（列）的限制

因为行列枚举必然会有重复，我们要再次加上重复的部分…以此类推

进行容斥，不难得到
$$
ans = \sum_{i = 0} ^n \sum_{j = 0} ^n f(i, j) \ =\sum _{i = 0} ^n \sum _{j = 0} ^n (-1) ^ {i + j} \cdot \binom {n} {i} \cdot \binom {n} {j} \cdot k ^ {n ^ 2 - n(i + j) + i \cdot j} \cdot (k - 1) ^ {n (i + j) - i \cdot j}
$$
这个时候已经可以$\mathcal {O}(n ^ 2 \log n)$做了，但是我们可以将其优化到$\mathcal {O}(n \log n)$

然而我太菜了不会优化，留个坑

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
 
const int N = 1e3, Mod = 1e9 + 7;
int n, K, fac[N + 5], D1[N + 2][N + 2], D2[N + 2][N + 2], com[N + 2], ans;
 
inline int qpow(int x, int y) {
    int res = 1;
    for (; y; x = 1LL * x * x % Mod, y >>= 1)
        if (y & 1) res = 1LL * res * x % Mod;
    return res;
}
 
inline int Inv(int x) {
    return qpow(x, Mod - 2);
}
 
inline int C(int n, int m) {
    return 1ll * fac[n] * Inv(fac[m]) % Mod * Inv(fac[n - m]) % Mod;
}
 
signed main() {
    scanf("%d%d", &n, &K);
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1ll * i * fac[i - 1] % Mod;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            int tmp = 1LL * qpow(K, i * j) * C(n, i) % Mod * C(n, j) % Mod * qpow(K - 1, n * n - i * j) % Mod;
            if ((i + j) & 1) ans = (ans - tmp + Mod) % Mod;
            else ans = (ans + tmp) % Mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}