poj 2356 Find a multiple (剩余类,抽屉原理)

 

http://poj.org/problem?id=2356

题意:有n个数,从中选取若干个(1..n),和能被n整除。问是否有解,无解输出0,有解的话,输出个数以及选择的a[i]( 不是i)

由抽屉原理可知一定有解:
做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n
n个数,sum[i]最多有n种。
如果某个sum[i]为0,那么表示从1到i的和能被n整除。
如果所有的sum[i]不为0,那么一共有n个sum[i],n-1个值(1..n-1),一定有sum[i]==sum[j](i<=j)
那么a[i]到a[j]的和一定能被n整除。

hdu 1205 吃糖果 (鸽笼原理)

http://acm.hdu.edu.cn/showproblem.php?pid=1205
题意:有n种糖果,第i种糖果有a[i]个,相邻两次不能吃一样的糖果,问能否有办法吃完所有糖果…
思路:如果第i种糖果有k个的话,那么其他所有种类的糖果之和至少有k-1个,才可能吃完。复杂度O(n)
看到有人说是抽屉原理…..大概。。。?不过不太明显。。直接想就好吧

hdu 1796 How many integers can you find (容斥原理)

hdu1796
题意:给出n(<=2^31)以及m(<=10)个元素组成的无重复元素集合,集合元素0<=a[i]<=20,问有多少个小于n的数能至少被集合中的一个元素整除。

思路:容斥,找到能被一个元素的,被两个元素的…加加减减。
一个元素的最小公倍数定义成自己,然后多个元素的就两个两个算…

一个坑点是,a[i]有0,而一个数除以0没有意义。。。所以读入的时候处理下。。。把0删掉(个人觉得这个坑点毫无技术含量。。。。0不能作为除数这种事情呵呵呵)  并且如果只有一个数且为0,那么删掉后集合就为空了,特判输出0.

 

另一个坑点是,别看每个数都很小。。但是求多个数的最小公倍数的时候会爆int…

虽然最后结果没有爆,但是中间量会爆掉,要开long long 

 

20160305update:也写个递归版本的,好简洁有木有。

hdu 4336 Card Collector (2012多校 #4) (容斥原理模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4336

题意:有n种卡片,买一包干脆面得到第i种卡片的概率是p[i],每包干脆面最多有一张卡片,问收集齐所有卡片要买的干脆面的包数的数学期望。

思路:容斥模板题。1.0/p[i]就是拿到某张卡片需要买的包数的数学期望

注意体会这种具体应用容斥的模拟方法,把1<<n转化成二进制来模拟有1个元素的集合,有2个元素的集合…有n个元素的集合。
核心代码:

 

20160305update:前几天有道题没写递归形式tle掉了。。。所以来学习一下容斥原理的递归形式。

以及这道题用递归的形式写了一遍。

poj 3734 Blocks (指数型母函数,泰勒级数展开)

http://poj.org/problem?id=3734

题意+思路同hdu2065红色病毒解题报告

hdu 2065 “红色病毒”问题 (指数型母函数,泰勒级数展开)

http://acm.hdu.edu.cn/showproblem.php?pid=2065
题意:a,b,c,d四种元素,a,c只能出现偶数次(包括0次),b,d没有限制,问n个(2^64)个元素有多少种不同的组合。
思路:指数型母函数。。。n大的没办法用之前的办法做。

先来看下我们要求的式子:A=(1+x/1!+x^2/2!+x^3/3!……)^2*(1+x^2/2!+x^4/4!+x^6/6!……)^2.

其实一共四个式子相乘,但是a和c的情况相同,b和d的式子相同。

我们要求的是x^n的系数。。。n太大了。。直接搞肯定不行。

想到微积分学的泰勒展开。

e^x=1+x/1!+x^2/2!+x^3/3!+… (|x|<oo)

其实这里x的范围没有意义,因为母函数关注的是系数,不会代入x的值,所以可以不用考虑收敛性。

那么第一项(1+x/1!+x^2/2!+x^3/3!……)^2就可以换成(e^x)^2

第二项没有奇数项,很容易想到可以写成((e^x+e^(-x))/2)^2

继续化简:4*A=(e^x)^2*((e^x+e^(-x))/2)^2

4*A = (e^(4x)+2*e^(2x)+1)

我们要的是x^n的系数,再正向泰勒展开,得到x^n的系数应该是 (4^n+2*2^n)/4,也就是4^(n-1)+2^(n-1)

因为只要后两位的结果,其实就是结果%100.快速幂搞之。

以及,2^64 long long 存不下,应该用unsigned long long ,类型说明符是 %llu

 

 

 

 

bzoj 1610 [Usaco2008 Feb]Line连线游戏 (计算几何)

http://www.lydsy.com/JudgeOnline/problem.php?id=1610
题意:给出n个点,问有多少条直线,这些之间之间都不平行。
思路:求斜率(注意考虑斜率不存在),看有多少种斜率。
妈蛋。。。。斜率不存在是横坐标相等啊,不是纵坐标啊。。。蠢哭了好么。。。。。。

妈蛋。。。。斜率不存在是横坐标相等啊,不是纵坐标啊。。。蠢哭了好么。。。。。。

 

妈蛋。。。。斜率不存在是横坐标相等啊,不是纵坐标啊。。。蠢哭了好么。。。。。。

 

 

选区_024

 

太他妈惨了。。。。

 

 

 
null

bzoj 1607 [Usaco2008 Dec]Patting Heads 轻拍牛头 (筛法)

http://www.lydsy.com/JudgeOnline/problem.php?id=1607

题意:n个数,求对于每个数来说,其他n-1个数中是它约数的数的个数。

思路:类似筛法,从小到大处理,数i对其所有倍数的数的答案有cnt[i]的贡献 。最后记得把自己是自己的约数的情况减掉。

 

 

 

hdu 1521 排列组合 (指数型母函数模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=1521

题意:有n种物品,并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B,并且数量都是1,从中选2件物品,则排列有”AB”,”BA”两种。

思路:指数型母函数。
对于相同的元素,需要去掉该元素的重复度,即为元素个数的阶乘。具体做法是用double类型存储(方案数除以重复度),然后在最后把阶乘乘回来四舍五入取整(为什么是四舍五入?)

普通型母函数总结

从这里母函数(Generating function)详解学习了普通型母函数

① 、首先对c1初始化,由第一个表达式(1+x+x^2+..x^n)初始化,把质量从0到n的所有砝码都初始化为1.

② 、 i从2到n遍历,这里i就是指第i个表达式,上面给出的第二种母函数关系式里,每一个括号括起来的就是一个表达式。

③、j 从0到n遍历,这里j就是(前面i個表达式累乘的表达式)里第j个变量,(这里感谢一下seagg朋友给我指出的错误,大家可以看下留言处的讨论)。如(1+x)(1+x^2)(1+x^3),j先指示的是1和x的系数,i=2执行完之后变为

(1+x+x^2+x^3)(1+x^3),这时候j应该指示的是合并后的第一个括号的四个变量的系数。

④ 、 k表示的是第j个指数,所以k每次增i(因为第i个表达式的增量是i)。

⑤ 、把c2的值赋给c1,而把c2初始化为0,因为c2每次是从一个表达式中开始的。

讲得不错,之前第三点注释有问题没想到现在已经改过来了2333.

 

说说我的理解:母函数其实形式上就是函数…但是关注的是系数。。就像一排挂衣架一样。

普通型母函数的作用就是通过模拟多项式乘法的方式解决一类组合计数问题。

一般能由普通型母函数解决的问题也能由dp或者递推来解决,但是母函数可能更容易理解(对我个人来说

这类问题呢,一般有如下几种问法。

一种是对于每类物品的个数,可能每类个数有限,也可能无限。

如果无限个,那么就根据n的大小作为一个循环的上限,因为n+1以及以后的指数肯定对答案没有贡献。

比如这道题: hdu1028解题报告

如果每类都有限,那么就根据每类物品作为上限。这时j那一层循环要不断累加(变量cur)当前能得到的最大价值(也就是多项式的最大指数) 比如这道hdu1085解题报告
也可能不仅要求上限,还要求有下限,也就是要求每类物品的个数必须在一个范围内。比如这道hdu2152解题报告

也可能两种要同时考虑。比如这道hdu2082解题报告 不过如果就算把所有数量算上也不会太大(数组存不下)的话,不考虑也可以(我懒)

还有,每种元素并不一定像整数拆分一样是连续的,可能像硬币问题一样只有1分,2分,5分的硬币,或者只能是平方数hdu1398解题报告 只能是素数hdu2189解题报告

还有一点,不一定所有元素对答案都是正的贡献,也可能是负的贡献。 这类问题主要是和天平有关。给你若干砝码,问你能称量出多少的重量。由于砝码可以放左边也可以放右边,所以每个对答案有正负两种贡献(不放就是没贡献)
比如这道hdu1709解题报告和这道hdu5616解题报告

最后就是稍微难一点的一类问题:对单个元素的个数没有限制,但是对所有元素的总个数有限制。这类题我们需要增加一维。现在用a[i][j]表示由j个元素组成价值为i的方案数。具体见这里:hdu2069解题报告

 

20160303 update: 还有一种当个数特别多。。以至于不可能通过循环来实现的情况。需要通过泰勒展开来化简。比较经常用的一个式子是 1+x+x^2+..+x^n=(1-x^(n+1))(1-x)

比如这道题:
codeforces451EDevu and Flowers解题报告

hdu 1284 铅笔兑换问题(母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=1284
题意:有1分,2分,3分的钱若干,问组成n(n<=32767)分钱的方案数。
思路:母函数.

需要注意的是多组数据。每次都搞会TLE,可以先预处理出来存到数组里,每次直接调用。如果预处理时间也还是慢的话,可以先跑出来,然后打表。这算一个小tip吧2333

 

hdu 2082 找单词 (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=2082
题意:26个字母,第i个字母有x[i]个,价值为i.问能组成多少个价值不超过50的单词(注意这里的单词只考虑字母的组成,不考虑字母之间的顺序)
思路:母函数。

BC #70 B || hdu 5616 Jam’s balance (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=5616
题意:有n个(n<=20)砝码,第i个重量为w[i],给出m个查询,每个查询一个重量,问这个重量能否被称量出。 思路:暴力(没美感),01背包(不会),母函数(瞬间成了傻逼题)和这题很像 hdu1709 balance
hdu1709解题报告

hdu 2152 Fruit (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=2152

题意:中文题目,大概是说有n(<=100)种水果,第i种至少拿l[i]个,最多拿r[i]个,现在挑选m种水果组成一个果盘,问方案数。

思路:母函数,之前的题目都是只对上界有限制,其实对下界有限制是一样的。以及。。。一开始以为是拿100元买。。。后来发现是“一打百元大钞”23333  其实再出难点可以对个数以及钱数都有限制。。。。

 

 

hdu 2069 Coin Change(母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=2069

题意:有1,5,10,25,50面值的硬币若干,问组成n元钱有多少种不同的方案。一个额外的要求是硬币的总是不能超过100.(那句 your program should be able to handle up to 100 coins.真的是这个意思。。。?感觉好坑。。。)

思路:还是母函数,但是由于有了多硬币总数的限制条件,需要加一维.a[i][j]表示j个硬币组成i元钱的方案数(越来越想dp了) 如果转移的时候需要需要加一层硬币的个数。具体见代码。