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\n",f[k][0]);

}

} signed main() {Luitaryi::main(); return 0;}

2019.08.16

84

巴特西

BZOJ 2169 连边 DP

思路：DP

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

题解：

最新文章

热门文章