BZOJ 2169 连边 DP

思路：DP

提交：(1)次（课上刚讲过）

题解：

如果不管重边的话，我们设(f[i][j])表示连了(i)条边，(j)个点的度数是奇数的方案数，那么显然我们可以分三种状态转移：
(f[i][j]+=f[i-1][j-2]*C_{n-j+2}^2;)连了两个偶点
(f[i][j]+=f[i-1][j]*j*(n-j);)连了一奇一偶
(f[i][j]+=f[i-1][j+2]*C_{j+2}^2;)连了两个奇点
考虑如何处理重边：我们设(f[i][j])表示连了(i)条边，(j)个点的度数是奇数，并且没有重边方案数，那么除了上面的转移，还要多一个：
(f[i][j]-=f[i-2][j]*(C_n^2-(i-2))),含义是任选一条边，假设被连了两次，那就相当于他没有连（不改变奇偶点的数量）。
由于此时的(DP)的加边方案是有序的，即我们的 (DP) 限制了 (i) 这条边的出现，所以在转移完后要对方案数除以 (i) 。

#include<cstdio>
#include<iostream>
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0;
	register I f=1; register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=1010,M=10007;
int n,m,k,tot,Inv[M],c[N],ans;
int f[N][N];
inline int C(int n) {return 1ll*n*(n-1)*Inv[2]%M;}
inline void main() {
	g(n),g(m),g(k); Inv[1]=1; for(R i=2;i<=min(k,M-1);++i) Inv[i]=M-M/i*Inv[M%i]%M;
	for(R i=1,u,v;i<=m;++i) g(u),g(v),++c[u],++c[v]; for(R i=1;i<=n;++i) tot+=(c[i]&1); 
	f[0][tot]=1; for(R i=1;i<=k;++i) for(R j=0;j<=n;++j) {
		if(j>=2) f[i][j]+=f[i-1][j-2]*C(n-j+2)%M;
		f[i][j]+=f[i-1][j]*j%M*(n-j)%M;
		f[i][j]+=f[i-1][j+2]*C(j+2)%M;
		if(i>=2) f[i][j]+=M-f[i-2][j]*(C(n)-(i-2))%M;
		f[i][j]=1ll*f[i][j]*Inv[i%M]%M;
	} printf("%d
",f[k][0]);
}
} signed main() {Luitaryi::main(); return 0;}

2019.08.16
84