题目大意
给定一个 $n$ 个点 $m$ 条边的图，要在图上加 $k$ 条互不相同的边（新边可以和旧边相同），使得新图的每个点的度数都是偶数。求方案数 $\bmod 10^4 + 7$ 的结果。
数据范围：$m \le n \le 10^3, k \le 10^3$。
思路分析
首先发现加的边只和原图每个点度数的奇偶性有关。所以先求出旧图每个点度数的奇偶性，假设 $n$ 个点中有 $m$ 个点的度数是奇数。
令 $f(i, j)$ 表示加了 $i$ 条边，有 $j$ 个点度数为奇数的方案数。假设第 $i$ 条边可以和之前的重复，那么我们有：
考虑减去重复的方案数。$i$ 与之前的边重复等价于从前 $i - 1$ 条边中选一条和第 $i$ 条相同，然后确定第 $i$ 条边是什么。由于第 $i$ 条边和选中的那条边不能和前 $i - 1$ 条边中没被选中的边相同，所以共有 $\binom{n}{2} - (i - 2)$ 种选法。而从 $i - 1$ 条边中选一条边的方案数为 $i - 1$。所以重复的总方案数是 $(i - 1) \times (\binom{n}{2} - (i - 2)) \times f(i - 2, j)$，我们把 $f(i, j)$ 减去这个数即可。时间复杂度 $O(nk)$。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 1e3, mod = 1e4 + 7; |
5 | int n, m, k, c, a[maxn + 3], dp[maxn + 3][maxn + 3]; |
6 | |
7 | int f(int i, int j) { |
8 | return j < 0 || j > n ? 0 : dp[i][j]; |
9 | } |
10 | |
11 | int qpow(int a, int b) { |
12 | int c = 1; |
13 | for (; b; b >>= 1, a = a * a % mod) { |
14 | if (b & 1) c = a * c % mod; |
15 | } |
16 | return c; |
17 | } |
18 | |
19 | int main() { |
20 | scanf("%d %d %d", &n, &m, &k); |
21 | for (int u, v; m--; ) { |
22 | scanf("%d %d", &u, &v); |
23 | a[u] ^= 1, a[v] ^= 1; |
24 | } |
25 | for (int i = 1; i <= n; i++) { |
26 | c += a[i]; |
27 | } |
28 | dp[0][c] = 1; |
29 | for (int i = 1; i <= k; i++) { |
30 | for (int j = 0; j <= n; j++) { |
31 | dp[i][j] = ((n - j + 2) * (n - j + 1) / 2 % mod * f(i - 1, j - 2) + (n - j) * j % mod * f(i - 1, j) + (j + 1) * (j + 2) / 2 % mod * f(i - 1, j + 2)) % mod; |
32 | if (i > 1) { |
33 | dp[i][j] = (dp[i][j] + ((n * (n - 1) / 2) - (i - 2)) % mod * (mod - (i - 1)) % mod * f(i - 2, j)) % mod; |
34 | } |
35 | } |
36 | } |
37 | int ans = dp[k][0]; |
38 | for (int i = 2; i <= k; i++) { |
39 | ans = ans * qpow(i, mod - 2) % mod; |
40 | } |
41 | printf("%d\n", ans); |
42 | return 0; |
43 | } |