首先,安利一篇博文,Codeforces 上的一些组合计数问题。
这是一些CF上的simple??的组合计数题。QAQ
第一波-2017.8.24
CF57C。给定$n$,求存在多少长度为$n$的序列满足:所有数在$1$到$n$之间,这个序列是非递增或非递减的。$n<=100000$
组合数的格路模型。不失一般性,我们考虑序列是非递减的方案数。可以注意到,假设最后一个数字是$n$,其等价于从$(0,0)$走到$(n-1,n-1)$的方案数。为什么呢?我们可以把向右走看作是到下一个数,向上走可以看成是当前位置的数$+1$,并且,序列的数是非递增的。最后一个数可以是$[1,n]$,同理求出。
CF689E。给定$n$和$K$,然后给定$n$个区间,在$n$个区间中选择$K$个,求它们的交集总和。$n<=100000$
离散化,贡献。本题似乎难以直接穷举所有的情况,考虑离散化,并计算每一条线段被多少个区间覆盖。假设某一段被$x$条线段覆盖,那么,我们只需要从这$x$条中选取$K$个,就会对答案产生贡献。即为$len \times C_{x} ^{K}$。
CF28C。有$n$个人等概率随机进入$m$个房间,一个房间可以有多个人,第$i$个房间有$ai$个水龙头,在一个房间的人要去排队装水,他们会使得最长的队尽可能小,求所有房间中最长队列长度的期望。$n,m<=50$
概率,动态规划。注意到,一个房间内原来有多少人到达最长是无法记录在状态中的,所以直接求概率十分困难。考虑概率的原始定义:方案数除以总方案数。也就是说我们求出状态的方案数即可。
用$f(i,j,l)$表示已经分配了前$i$个房间和$j$个人,最长队列长度为$l$的方案数。首先$f(i,0,0)=1$。
状态可以有两种决策转移,一种是当前房间队列到达$l$,前面的房间任意;另一种是前面有房间队列到达$l$,但当前的房间任意,于是,
$$\large f(i,j,l) = \sum {k=0} ^{l} \left( ^{n-j+p} {\ \ \ \ p} \right) f(i-1,j-p,k) \ \large + \sum {k=0} ^{\min p -1} \left( ^{n-j+k} {\ \ \ \ \ k} \right) f(i-1,j-k,l)$$
其中$p$为使得第$i$个房间队列长度为$l$的数的集合,需要枚举。
CF15E。给定一个整数$N$,当$N=12$的时候是这样一幅图:
然后你要从最上面的$H$点出发,走一条道路,这条道路中间不包括任何灰色三角形,最后回到$H$。$N$是偶数,$n<=10^6$,问有多少情况,答案对$1e9+9$取模。
递推。为了方便起见,我们以下图所示的阶段划分。
由于整个图是对称的,所以我们考虑左半部分。除去几种特殊情况,我们都需要从绿点出发回到紫点,方案数记为$g[1]$。令$f[i]$表示陷进去$i$层的方案数(强制不能从洞口经过,防止重复计数)。令$g[i]$表示第i个蓝点到红点的方案数,于是显然有,
$$\large f[0] = 0,\ f[1] = 4,\ f[i] = 4 + 2 \times f[i-1]$$
通过$f[]$我们可以很容易地递推出$g[]$。首先,
$$\large g[n/2] = 1$$
$g[i]$可以从哪些方面转移呢,第一种是从蓝点$i$不经过蓝点$i+1$回到红点$i$,根据是否进入洞穴来分;第二种是经过了蓝点$i+1$。综上,即为,
$$\large g[i] = 3 \times f[i-1] + 4 + g[i+1] \times (f[i-1]+1)$$
如何根据$g[1]$来计算答案?可以注意到,一种是从绿点到紫点再到绿点;一种是从绿点到紫点再直接回去;还有$2$种情况是不经过绿点。于是答案即为:
$$\large ans = 2 \times (g[1] \times g[1] + 2 \times g[1] + 2)$$
CF40E。给出一个$n\times m$的矩阵,每个元素都是$1$或$−1$,其中有$k$个位置元素已经确定,并且这个矩阵满足每一行、每一列元素的乘积都是$−1$,问有多少种不同的矩阵。$1≤n,m≤1000,0≤k<\max(n,m)。$
组合,观察。注意到乘积为$-1$的等价条件为$-1$有奇数个。需要注意一个条件$k<\max(n,m)$,这意味至少存在一行(或列)是空的。这是极其重要的一条性质。
假设空的一行为$x$,我们可以先去填上其他行。此后满足其他行的乘积都为$-1$,这个可以通过组合数很容易地算出来。然后,我们要求列的乘积也是$-1$,不难发现,第$x$的每一个数都是唯一确定的。也就是是说,其他行方案的乘积就是总的方案数。
但是这样还没有完,我们仍需要保证第$x$行的乘积是负数,如何确定呢。注意到,所有数的乘积是$(-1)^m$,如果$(-1)^m \not= (-1)^n$则一定无解,否则第$x$行的乘积一定是负数。
CF830D。给定$n$,现有深度为$n$的满二叉树,对于一个节点,给它与它的所有父亲连一条边。 问得到的新的图有多少条不同的简单路径(1->2和2->1算不同路径) 。$n≤400$
树形DP,巧妙非常规的状态定义。首先考虑一个错误的算法,通过对错误的分析,可以得到正确的算法。
假设状态$f[i]$表示深度为$i$的满二叉树,方案的个数为$f[i]$。我们考虑按照是否通过根结点来讨论。一种是根经过根据所在子树不同,有$f[i-1] \times f[i-1] \times 4$种情况,一种是从根出发或结束,有$f[i-1] \times 4$种情况,还有一种是不经过根$f[i-1] \times 2$,当然,只包含$1$的简单路径也算,就是要$+1$。
可以发现,这比答案大很多。问题出在哪里呢?可以发现,如果我从左子树到根再到左子树,就会发生方案不合法,同时注意到$n$比较小,考虑附加一些状态来避免非法。
我们需要在同一个子树中选择两个不相交的路径,然后与根相连。此后不相交的路径条数会不变或减小。
这就启发我们还要记录一个状态:此时树中有多少个不相交路径。即$f[i,j]$表示从深度为$i$的树中,选出$j$条不相交的路径的方案数。那么答案就是$f[k,1]$,按照根所在路径,枚举$f[i-1,j]$和$f[i-1,k]$转移如下:
- 如果让根成为单独的一条路径,那么$f[i,j+k+1]\ += f[i−1,j] × f[i−1,k] $
- 如果不选根,那么$f[i,j+k] += f[i−1,j] × f[i−1,k] $
- 让根与左儿子中的一条路径结合或和右儿子中的一条路径结合,那么$f[i,j+k] += f[i−1,j] × f[i−1,k] × 2 × (j+k)$
- 从$j+k$条边中选出两条,让这两条边与根结合形成新的一条边,那么$f[i,j+k−1] += f[i−1,j] × f[i−1,k] × C(j+k, 2) × 2$
真的是一道DP神题!