codeforces 439 C – The Intriguing Obsession (和图有关的计数,组合数学)

题意:

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) )

对于其他 两对同理。

 

bzoj 1008: [HNOI2008]越狱(对立事件,组合数学)

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

6

HINT

  6种状态为(000)(001)(011)(100)(110)(111)

思路:越狱的情况很多,考虑不越狱的情况。

答案为:m^n – m*(m-1)^(n-1)

 

 

hdu 4451 Dressing (计数,思维题)

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的答案即可。

poj 1322 chocolate (指数型母函数 )

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比较大,滚动一下应该可以… 然后看到别人的题解里写到当n>1000的时候已经趋向平衡(达到了要求的精度)… 这道题dp写起来的确容易,也不是很难想。

不过作为dp废宁愿选择数学方法,指数型母函数。

 

分析可知,取过偶数次的巧克力消失,只有取过奇数次的巧克力会留在桌子上。

那么要剩余m个巧克力,也就是有m种巧克力取了奇数次,剩下的c-m种巧克力取了偶数次。

对应的的生成函数(母函数)分别是(e^x-e(-x))/2和(e^x+e(-x))/2  (推倒类似)hdu2065红色病毒解题报告

总事件个数为c^n

根据古典概型,所求概率为 (Gn*n!*C[c][m])/(c^n)  其中Gn*n!为生成函数,C[c][m]是因为不确定c种巧克力中的哪m种取了奇数个。

现在的问题就成了求Gn中x^n的系数。。我就是因为这个卡了两天这道题。。。

 

其实模拟就好,复杂度O(c^2)而已。。主要是好久没写二项式定理。。。有点忘了(手动智力-2)

 

hdu 1028 Ignatius and the Princess III(整数拆分,母函数模板题)

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

具体解释见代码注释。

hdu 5145 NPY and girls

http://acm.hdu.edu.cn/showproblem.php?pid=5145
题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

思路:正好刚刚听完学堂在线上的组合数学的那一节,讲到有重复元素的不重复排列的个数的计算方法:可以先将所有元素看成不重复,再除以每个元素的重复度的阶乘(重复度定义为每个元素个数)。

增加一个元素的影响是,乘一个增加的长度,并且除以该元素的重复度(因为每增加一个元素就要除以以此重复度,那么当同一元素c增加到第i次时,除以的就是i的阶乘),减少一个元素的影响正相反。 两种改变都可以O(1)实现,因此可以上莫队。

之前要预处理下逆元。

 

 

 

codeforces #334 div 2 D.Moodular Arithmetic

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

HUST team contest #2 C Divisible Subsequences ||poj 3844 (剩余类)

算是签到帖,竟然卡住了。

我数学还是太差了。。

然后去找题解。。竟然看不懂!

我数学真的有这么差嘛。。。

然后多亏了队友 @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]的和为 sum[j]-sum[i-1]

也就是(sum[j]-sum[i-1] )%d==0

也就是sum[j] 和 sum[i-1] 关于 d 同余

如果我们在处理得到前缀和的时候就%dshuxue

那么就是sum[j]==sum[i-1]

所以我只要对于d的每一个剩余类有多少个统计出来。

然后对于每个剩余类,只需要任意取出两个,就是一种答案。

需要注意的是如果只有一个0,也是一种答案。

我们可以定义sum[i] = 0

还有一个需要注意的是要开long long

codeforces 569 D. Symmetric and Transitive (组合数学 第二类斯特林数 贝尔数)

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 important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.

A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair , in this case we use a notation .

Binary relation is equivalence relation, if:

  1. It is reflexive (for any a it is true that );
  2. It is symmetric (for any ab it is true that if , then );
  3. It is transitive (if  and , than ).

Little Johnny is not completely a fool and he noticed that the first condition is not necessary! Here is his “proof”:

Take any two elements, a and b. If , then  (according to property (2)), which means  (according to property (3)).

It’s very simple, isn’t it? However, you noticed that Johnny’s “proof” is wrong, and decided to show him a lot of examples that prove him wrong.

Here’s your task: count the number of binary relations over a set of size n such that they are symmetric, transitive, but not an equivalence relations (i.e. they are not reflexive).

Since their number may be very large (not 0, according to Little Johnny), print the remainder of integer division of this number by 109 + 7.

Input

A single line contains a single integer n (1 ≤ n ≤ 4000).

Output

In a single line print the answer to the problem modulo 109 + 7.

Sample test(s)
input

output

input

output

input

output

Note

If n = 1 there is only one such relation — an empty one, i.e. . In other words, for a single element x of set A the following is hold: .

If n = 2 there are three such relations. Let’s assume that set A consists of two elements, x and y. Then the valid relations are ,ρ = {(x, x)}, ρ = {(y, y)}. It is easy to see that the three listed binary relations are symmetric and transitive relations, but they are not equivalence relations.

 

给出n个元素的集合上满足传递律,交换律,但不满足自反律的二元关系个数.

还以为是我离散数学没认真听才没做出来...

题解:http://blog.csdn.net/mengzhengnan/article/details/47424295

 

贝尔数(集合的划分数目)

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数列
Bn基数n集合划分数目。集合S的一个划分是定义为S的两两不相交的非空子集的族,它们的并是S。例如B3 = 5因为3个元素的集合{abc}有5种不同的划分方法:
  • {{a}, {b}, {c}}
  • {{a}, {bc}}
  • {{b}, {ac}}
  • {{c}, {ab}}
  • {{a, b, c}}

B0是1因为空集

正好有1种划分方法。划分的定义要求空集的划分中的每个成员都是非空集合,而它们的并是

本身。所以

是它自身的唯一划分。(这是定义所允许的因为

2公式编辑

贝尔数适合递推公式:
它们也适合“Dobinski公式”:

期望值为1的泊松分布的”n”次

它们也适合“Touchard同余”:若p是任意质数,那么
每个贝尔数都是”第二类Stirling数”的和
Stirling数S(n, k)是把基数为n的集划分为正好k个非空集的方法的数目。
把任一概率分布的n次矩以首n个累积量表示的多项式,其系数和正是第n个贝尔数。这种数划分的方法不像用Stirling数那个方法粗糙。
贝尔数的指数母函数

3贝尔三角形编辑

用以下方法建构一个三角矩阵(形式类似杨辉三角形):
(1) 第一行第一项是1(a_{1,1} = 1)

(2) 对于n>1,第n行第一项等同第n-1行最后一项。(

(3) 对于m,n>1,第n行第m项等于它左边和左上方的两个数之和。(

结果如下:(OEIS的A011971数列[2] )
每行首项是贝尔数。每行之和是第二类Stirling数
这个三角形称为贝尔三角形、Aitken阵列或Peirce三角形(Bell triangle, Aitken’s array, Peirce triangle)。