容斥专题

容斥专题:容斥专题题集
复习了一下容斥,发现原来容斥可以用位运算写,以前一直使用dfs写的。。弱爆了。。
这两种做法各有适用的场合。
重新做了一下zoj3687
dfs版的容斥
题意:n天n个章节,给你m个约束条件,一个约束条件d,c表示第d天不能复习第c章节。问总共有多少种复习的方式(答案mod 55566677)。
思路:典型的容斥题目。算出满足所有约束的方案数,最后n!减一下即可。以前做的时候忘了约束会有重复,这次做又忘了。。真是渣渣。首先完全相同的约束只保留一个,否则会多算。然后,如果d或c有重复,则说明这两个约束条件同时满足的方案数为0,不能递归下去了。

polya定理&&burnside引理

专题地址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=36645#overview
这里有更完整的:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=484
看了下大白书,做下上面的习题。两个定理叙述很简单,证明暂时没看,先把题做的差不多再说。。
一些小结:
1.置换。一对一的函数
2.置换的乘法:满足结合律,但不满足交换律
3.置换分解成几个循环的乘积,因为假如将一个置换看成一条有向边那么形成的图中每个点都是入度为1,出度为1.所以一定是若干个圈。
4.独立的循环之间的乘法满足交换律
5.设A是与元素个数为n的循环,则:
(1)若n为奇数,则A*A是一个n个元素的循环
(2)若n为偶数,则A*A是两个n/2个元素且相互独立的循环的乘积
6.引出:由5的性质可知:
(1)一个长度n为奇数的循环B,一定可以找到一个长度为n的循环A,满足A^2=B;
(2)两个长度都为n的不相交循环B和C,一定可以找到长度为2*n的循环A,使得A^2=B*C;
7.继续引出:
(1)长度n为奇数的循环既可以是两个长度为n的循环乘出来的,也可以是两个长度为2n的循环乘出来的。
(2)长度n为偶数的循环只可能是两个长度为2n的循环乘出来的。
下面是一些题目
UVA 10294 Arif in Dhaka (First Love Part 2)
数学推算。。

对组合排列问题的小结

(1)求组合排列数
问题一:
从n个不同数中取k个的组合数,排列数?
简单组合排列公式
问题二:
从n1个a1,n2个a2,n3个a3,……,nk个ak中(a1,a2……允许相等):
取k个数的组合方案数?(用母函数求解)
取k个的排列方案数?(指数型母函数)
(2)输出组合排列方案
问题三:
n个不同数取k个的全部组合?
可以使用dfs求解

从n个不同元素中取k个进行组合的方案

看了《组合数学及其应用》第一章之后用dfs实现了下输出从n个不同元素中取k个进行组合的方案,具体思想可参考这篇博文:http://masoi.blog.sohu.com/98842004.html
n个不同元素取k个,假设组合升序排列,则显然有如下性质:(输入数组a[]已升序排列)
(1)第k个数最大取到a[n],第k-1个数最大取到a[n-1]……第j个数最大取到a[n-(k-j)]……第1个数最大取到a[n-(k-1)]。
(2)第j个数比第j-1个数大。
根据以上两点不难写出dfs程序。
特别的,当从x,x+1,x+2,……,x+n-1这n个连续元素中取k个元素时有更特殊的解法。(这里的“连续元素”可以扩展,可以是等差数列,并不一定元素间只相差1,当然本人没实现过,不敢说这句话正确)