Description
有N个点（编号1到N）组成的无向图，已经为你连了M条边。请你再连K条边，使得所有的点的度数都是偶数。求有多少种连的方法。要求你连的K条边中不能有重边，但和已经连好的边可以重。不允许自环的存在。求连边的方法数。我们只关心它模10007的余数。
Input
输入的第一行有三个自然数，分别表示点数N，已经连好的边数M，和你要连的边数K。保证K≤N(N-1)/2 接下来M行每行两个整数x,y，描述了一条连接x和y的边。 30%的数据满足： N≤200 100%的数据满足： N≤1000，M≤N，K≤1000，K≤N(N-1)/2
Output
输出一个整数，表示连边的方法数模10007的余数
Sample Input
1 2
Sample Output
HINT
【样例说明】
以下是13种连边的方法（只显示你连的边）：
{(1,2),(1,3),(1,4),(3,4)}
{(1,2),(1,3),(1,5),(3,5)}
{(1,2),(1,4),(1,5),(4,5)}
{(1,2),(2,3),(2,4),(3,4)}
{(1,2),(2,3),(2,5),(3,5)}
{(1,2),(2,4),(2,5),(4,5)}
{(1,2),(3,4),(3,5),(4,5)}
{(1,3),(2,4),(3,5),(4,5)}
{(1,3),(2,5),(3,4),(4,5)}
{(1,4),(2,3),(3,5),(4,5)}
{(1,4),(2,5),(3,4),(3,5)}
{(1,5),(2,3),(3,4),(4,5)}
{(1,5),(2,4),(3,4),(3,5)}
题解
我们令$f[i][j]$表示有序地添入$i$条边后还剩$j$个奇点的方案数。
易推出
1.$f[i][j]+=f[i-1][j-2]*{C^2 _{n-j+2}}$ （第$i$条边连接了两个非奇点）
2.$f[i][j]+=f[i-1][j]*j*(n-j)$ （第$i$条边连接一个奇点一个非奇点）
3.$f[i][j]+=f[i-1][j+2]*{C^2 _{j+2}}$ （第$i$条边连接两个奇点）
但除此之外，我们还没有考虑不能连接相同的边。
由容斥原理得：
4.$f[i][j]-=f[i-2][j]*({C^2 _n}-(i-2))$ （总共${C^2 _n}$条边，我们已经排除$i-2$条一定不重复）。
这样$f[i][j]$的转移方程就列完了，然而，题目要求的并不是有序的我们还需要将$f[i][j]/=i$使$f$代表无序。
综上，若$f[i][j]$表示无序地添入$i$条边后还剩$j$个奇点的方案数：
$f[i][j] = {1 \over i}(f[i-1][j-2]*{C^2 _{n-j+2}}$$+f[i-1][j]*j*(n-j)$$+f[i-1][j+2]*{C^2 _{j+2}}$$-f[i-2][j]*({C^2 _n}-(i-2)))$
//It is made by Awson on 2017.9.23
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define LL long long
using namespace std;
const int N = ;
const int MOD = ; int n, m, k, u, v;
bool odd[N+];
int f[N+][N+]; int quick_pow(int a, int b) {
int c = ;
while (b) {
if (b&) c = a*c%MOD;
a = a*a%MOD;
b >>= ;
}
return c;
}
int C2(int n) {
return n*(n-)/%MOD;
} void work() {
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= m; i++) {
scanf("%d%d", &u, &v);
odd[u] = !odd[u];
odd[v] = !odd[v];
}
int cnt = ;
for (int i = ; i <= n; i++) cnt += odd[i];
f[][cnt] = ;
for (int i = ; i <= k; i++)
for (int j = ; j <= n; j++) {
if (j >= ) f[i][j] = (f[i][j]+f[i-][j-]*C2(n-j+)%MOD)%MOD;
f[i][j] = (f[i][j]+f[i-][j]*j%MOD*(n-j)%MOD)%MOD;
if (j+ <= n) f[i][j] = (f[i][j]+f[i-][j+]*C2(j+)%MOD)%MOD;
if (i >= ) f[i][j] = (f[i][j]+MOD-f[i-][j]*(C2(n)-(i-))%MOD)%MOD;
f[i][j] = f[i][j]*quick_pow(i, MOD-)%MOD;
}
printf("%d\n", f[k][]);
}
int main() {
work();
return ;
}