[计数dp][组合数] JZOJ P1975 连边
2018-06-17 21:18:08来源:未知 阅读 ()
题解
-
设f(i,j)表示用i条边,使得j个点的度数为奇数的情况下连边的方法数。注意到所有的状态共用一个N。
-
首先,分类讨论第i条边连接的点的度数的奇偶性。
-
如果它连着两个奇数点,那么原来那两个点的度数是偶数,总奇数点个数比现在少2;
-
如果这条边连接的点是一奇一偶,那么奇数点的个数不变。
-
如果连接着两个偶数点,那么原来这两个点都是奇数点,总奇数点的个数比现在多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)
-
注意到这样转移的话无法保证没有重边。于是,让我们考虑第i条边和之前的第a条边重复的情况。a有i-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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P1358 扑克牌 2020-05-06
- CountingSort(计数排序)原理及C++代码实现 2020-01-14
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- C++引用计数设计与分析(解决垃圾回收问题) 2019-12-29
- JZOJ.1153【贪心算法】硬币交换 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash