题意： 3个岛屿群，每个岛屿群有若干岛屿。现在要在岛屿之间连桥，桥的长度是1，规定2个属于相同岛屿群的岛屿的距离要大于等于3. 思路： 一直在纠结大于等于3的距离的事情。。。其实这句话等价于，同一个岛屿，对于另外两个岛屿群，都最多只能连接1个岛屿。 那么其实，对于每一对岛屿群，是相互独立的。 对于任意一对岛屿群，设两边岛屿的数量分别为a,b 我们可以从两边各取0个，1个，最多取min(a,b) 需要注意的是，选取了端点之后有顺序的区别。 所以对于该对岛屿，答案是SUM{C[a][k] * C[b][k] * k!} (k属于0..min(a,b) ) 对于其他 两对同理。 /* …

1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 8165 Solved: 3486 [Submit][Status][Discuss] Description 　监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果 相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱 Input 　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12 Output 　可能越狱的状态数，模100003取余 Sample Input 2 3 Sample Output …

http://acm.hdu.edu.cn/showproblem.php?pid=4451 题意：N clothes, M pants and K shoes，然后给出p个不合法的搭配，形式是“clothes x pants y” or “pants y shoes z”.” 问有多少种合法的方案。 思路：一开始觉得是容斥。。当然可以。。但是实际上，不合法的搭配的形式比较简单，每种不合法的发配都是两个两个的不合法，以及每种不合法的形式都有pants,那么我们就可以通过先确定pants，对于每种pants，方案数就是能和当前pants搭配的clothes数，乘以能和当前pants搭配的shoes数，然后累加每种pants的答案即可。 …

http://poj.org/problem?id=1322 题意： 思路：别看n,m很大。。。但是想一下。。m显然不可能大于c(如果大于c，那么根据抽屉原理，至少存在一种巧克力大于一个，然而大于一个就会被取走...矛盾) 这样概率为0.m也不可能大于n，因为最好的情况就是取出的巧克力都放在了桌子上，如果总共取的还不到n个，又怎么可能剩下m（m>n）个呢。此外，还需要n,m奇偶性相同，否则设n-m=2K+1 ,说明如果要剩余m个，那么就要减少2k+1个，但是巧克力是两个两个减少的，减少的个数一定是偶数，因此矛盾。所以n,m奇偶性相同。 接下来可以用概率dp做，由于n比较大，滚动一下应该可以... 然后看到别人的题解里写到 …

http://acm.hdu.edu.cn/showproblem.php?pid=1028 题意：求整数拆分数。 思路：母函数模板题。关于母函数的学习：http://www.cnblogs.com/syxchina/archive/2011/07/07/2197205.html http://www.cppblog.com/tanky-woo/archive/2010/08/02/121969.html 具体解释见代码注释。 /* *********************************************** Author :111qqz Created Time :2016年02月25日 星期四 21时53分43 …

http://acm.hdu.edu.cn/showproblem.php?pid=5145 题意：有n个女孩，编号1..n,第i个女孩在第a[i]个教室,m次访问，每次访问编号[L,R]的女孩，处于同一个教室的女孩一次只能访问一个，问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。 思路：正好刚刚听完学堂在线上的组合数学的那一节，讲到有重复元素的不重复排列的个数的计算方法：可以先将所有元素看成不重复，再除以每个元素的重复度的阶乘（重复度定义为每个元素个数）。 增加一个元素的影响是，乘一个增加的长度，并且除以该元素的重复度（因为每增加一个元素就要除以以此重复度，那么当同一元素c增加到第i次时，除以的就是i的阶乘），减少一 …

http://codeforces.com/contest/604/problem/D 题意：一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数，且满足x对于定义域为0..p-1的p的整数，值域也在0..p-1范围（不一定一一对应）。问满足题意的f有多少个。 思路： f(0)=0,对于其他的值，当f（x）确定时，f（kx%p）也随之确定，那么把kx%p看做新的x,f（kkx%p）也随之确定...相当于【1，p-1】被分为r个小环，确定每个环可以任选一个数字，ans=p^r。环的个数可以用dfs跑一遍得到r. 注意当k=1的时候是特殊情况，f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1)，每一个 …

算是签到帖，竟然卡住了。 我数学还是太差了。。 然后去找题解。。竟然看不懂！ 我数学真的有这么差嘛。。。 然后多亏了队友 @zcy 妹子的讲解。。 其实很好理解啊。。。 不过数到底还是数学太差了== 今天七夕，废话有点多== 这道题的题意是，找序列中连续的一段，使得和 可以整除d 我们观察到数列中的数的范围是1..1 000 000 000 的 而d只有1 000 000 我们考虑余数相同，读入的时候就可以直接先 % 掉 d 因为只会和余数有关。 我们可以先处理出来一个前缀和数组sum[i]，表示前i个元素的和。 如果有一段序列从a[i] 到 a[j] 满足题意 根据题意那么这段序列的和一定%d=0 a[i] 到 a[j] …

D. Symmetric and Transitive time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very …

http://baike.baidu.com/link?url=kw5Kxe3nSvRJR0TpJUpMrORcQL8fyZFpJlT9_o0RlGYOy0bKFobabPPSj3LxGfy7o1qGVycrYK4Iags3hMFq0a 在组合数合里，贝尔数给出了集合划分的数目，以数学家埃里克·坦普尔·贝尔（Eric Temple Bell）命名，是组合数学中的一组整数数列。[1] 以B0= B1=1为始， 首几项的贝尔数为：1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …（OEIS的A000110数列） _B__n_是基数为_n_的集合划分数目。集合S_的一个划分是定义 …