[计数dp][组合数] JZOJ P1975 连边

2018-06-17 21:18:08来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

5 1 4
1 2

Sample Output

13

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个点的度数为奇数的情况下连边的方法数。注意到所有的状态共用一个N

  • 首先,分类讨论第i条边连接的点的度数的奇偶性。

  • 如果它连着两个奇数点,那么原来那两个点的度数是偶数,总奇数点个数比现在少2

  • 如果这条边连接的点是一奇一偶,那么奇数点的个数不变。

  • 如果连接着两个偶数点,那么原来这两个点都是奇数点,总奇数点的个数比现在多2

  • 通过枚举这条边连接的两个点的奇偶情况,f(i,j)可以分别转移到 f(i-1,j)*(N-j)*jf(i-1,j-2)*C(j,2)f(i-1,j+2)*C(N-j,2)

  • 注意到这样转移的话无法保证没有重边。于是,让我们考虑第i条边和之前的第a条边重复的情况。ai-1种取值。除去第i条和第a条边,所有的点的度数的奇偶性不变,于是问题转化为f(i-2,j)。这样,我们知道了第i条边和之前的某些边重复的方法数是f(i-2,j)*(i-1)*C(N,2)

  • 于是,总的转移方程是

  • f(i,j)=f(i-1,j)*(N-j)*j+f(i-1,j-2)*C(j,2)+f(i-1,j+2)*C(N-j,2)-f(i-2,j)*(i-1)*C(N,2)

  • 答案就是f(K,A)/K!

  • 转移的时候要注意取模以及边界情况的讨论

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int du[1001],cnt,n,m,k,mo=10007;
 7 long long f[1001][1001],a[1001];
 8 long long C(int x){ if (x<2) return 0; return (x-1)*x/2; }
 9 int main()
10 {
11     cin>>n>>m>>k;
12     a[0]=1;a[1]=1;
13     for (int i=2;i<=1000;i++) a[i]=(mo-mo/i)*a[mo%i]%mo;
14     for (int i=1;i<=m;i++)
15     {
16         int u,v;
17         scanf("%d%d",&u,&v);
18         du[u]++;du[v]++;
19     }
20     for (int i=1;i<=n;i++) if (du[i]%2==1) cnt++;
21       f[0][cnt]=1;
22       for (int i=1;i<=k;i++)
23         for (int j=0;j<=n;j++)
24         {
25               if (j>=2) f[i][j]+=f[i-1][j-2]*C(n-j+2)%mo;
26               f[i][j]%=mo;
27               if (j+2<=n) f[i][j]+=f[i-1][j+2]*C(j+2)%mo;
28               f[i][j]%=mo;
29               f[i][j]+=f[i-1][j]*j*(n-j)%mo;
30               f[i][j]%=mo;
31               if (i>=2) f[i][j]-=f[i-2][j]*(C(n)-i+2)%mo;
32             f[i][j]=(f[i][j]+mo)%mo;
33               f[i][j]*=a[i];
34             f[i][j]%=mo;
35         }
36   cout<<f[k][0];
37 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:[luogu2048] [bzoj2006] [NOI2010] 超级钢琴 题解

下一篇:adb shell兼容VT100