Codeforces 上的一些组合计数问题

Codeforces 15E. Triangles

Problem:给出一个有规律的金字塔(如图),黑色的边是可以走路径,要求求出包含 H 点的简单回路(不经过一个顶点两次)的条数,并且这个回路围住的部分不可以包含灰色的三角形,答案对 10^9+9 取模,其中 n \leq 10^6,并且一定是一个偶数

5945210be972aa5fe947f3b8a3a0378a4cade844

Example:当 n = 2 时,一共有 10 种方案,其中 5 种是这样,另外的是顺时针顺序地走

5E-triangles

Solution:首先第 1 层是最特殊的,因为这里没有灰色的三角形,然后注意到灰色的部分把整个金字塔分成了左部和右部

5E-triangles-level1

路径现在可以分成三个部分

  • 在第一层移动,这一共 10 种(见样例)
  • 进入左部或右部后直接回到 H
  • 进入左部(右部)后经过 E 点进入右部(左部)

对于第二种情况,在第一层的部分走法可以是(只有逆时针部分,实际上有 8 种)

  • A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow F \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow D \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A

对于第三种情况,在第一层(原来图中的两层现在算一层,也就是下面的 n 是题目中 n\frac{1}{2})的部分走法有 2 种,左部到右部和右部到左部

现在要统计的就是在左部和右部内有多少种方案,因为左部右部对称,所以答案是一样的,我们来考虑左部

S_n 表示在有 n 层的金字塔中,走左部的方案数,因为走进左部后每一层都会遇到凹进去的部分,这部分只要枚举一下走了多远可以统计出第 n 层一共有 2\sum_{i=1}^{n-2} 2^i + 1 = 2^n - 3 这么多的情况

然后要走到第 n 层后就是 \prod_{i=2}^{n} (2^i - 3) 种情况,然后走回去的路径有 4 种选择,因此

 S_n = \sum_{i=2}^{n} 4\prod_{j=2}^i (2^j - 3)

答案是 2S_n^2 + 8S_n + 10

Codeforces 382E. Ksenia and Combinatorics

Problem:有一棵 n(n \leq 50) 个节点的树,节点标号为 1, 2, \cdots, n,除了 1 号节点最多会与其它 2 个节点连边外,其余节点最多会与其它 3 个节点连边,两棵树是相同的,当且仅当每个节点的相邻节点都相同,问有多少种不同的这样的树,满足它的最大匹配是 k,答案对 10^9 + 7 取模

Solution:我们可以用 f(n, k, \{0, 1\}) 来表示有 n 个节点的树,它的最大匹配是 k 并且根节点是否在匹配中的方案数

现在和普通的二叉树计数一样,考虑枚举左右子树大小和最大匹配数,由于这树的节点是有标号的,假设左子树大小是 n_1,那么就有 {n - 1} \choose n_1 种方案分配节点,然后还有 n_1(n - n_1 - 1) 种方案分配根结点

为了避免重复统计,我们可以限制左子树的大小不超过右子树,特别的,当左右子树大小相同的时候,强制限定最小的那个节点在左子树,这样就可以避免重复了

假设根结点在匹配中,那么一定要有一个子树的根节点不在匹配中,这样才可以匹配

假设根节点不在匹配中,那么左右子树的根结点一定都要匹配,否则就不是最大匹配,因此只能从这里转移

Codeforces 28C. Bath Queue

Problem:有 n 个人等概率随机进入 m 个房间,一个房间可以有多个人,第 i 个房间有 a_i 个水龙头,在一个房间的人要去排队装水,他们会使得最长的队尽可能小,求所有房间中最长队列长度的期望

其中 1 \leq n, m \leq 50, 1 \leq a_1, a_2, \cdots, a_m \leq 50

Solution:由于要求期望,我们可以先求出最长队列长度为 l 的有多少种方案。用 f(i, j, l) 表示已经分配了前 i 个房间和 j 个人,最长队列长度为 l 的方案数

首先什么人都没有的情况 f(i, 0, 0) = 1

现在答案可以从两个地方统计,一是当前房间队列达到 l,前面的房间任意,二是前面有房间队列达到 l,但是当前没有达到,那么可以列出方程

 \begin{eqnarray*} f(i, j, l) &=& \sum_{k = 0}^l {{n - j + p_i} \choose {p_i}} f(i - 1, j - p_i, k)\\&+& \sum_{k=0}^{\min p_i - 1} {{n - j + k} \choose k} f(i - 1, j - k, l) \end{eqnarray*}

这里 p_i 是使得第 i 个房间队列长度为 l 的数的集合,也是要求枚举的

Codeforces 9D. How many trees?

Problem:题目要求统计有多少棵二叉树满足有 n 个节点,并且高度不小于 h,其中 n, h \leq 35

Solution:这题和上题有些相似之处,可以用 f(n, h) 表示有 n 个节点,高度恰好h 的方案数,那么考虑左右子树哪一棵高度是 h - 1 来转移

 f(n, h) = \sum_{i = 0}^{n-1}\sum_{j = 0}^{h-1}f(i, h - 1)f(n - i - 1, j) + \sum_{i = 0}^{n-1}\sum_{j = 0}^{h-2}f(i, h - 1)f(n - i - 1, j)

最后的答案是

 \text{ans} = \sum_{i \geq h} f(n, i)

这样的话复杂度是 \mathcal O(n^4) 的,注意到里面的求和是一个前缀和,记 s(n, h) = \sum_{i=0}^h f(n, i),那么式子就可以变成

 f(n, h) = \sum_{i = 0}^{n-1}f(i, h - 1)s(n - i - 1, h - 1) + \sum_{i = 0}^{n-1}f(i, h - 1)s(n - i - 1, h - 2)

这样复杂度变成了 \mathcal O(n^3),实际上,注意到求和是个卷积的形式,用快速傅里叶变换,可以优化为 \mathcal O(n^2\log n)

我这里只给出用了前缀和优化的代码

Codeforces 37D. Lesson Timetable

Problem:有编号为 1, 2, \cdots, m 一共 m 个教室和编号为 1, 2, \cdots, n 一共 n 组学生,每一组学生要上 2 节课,要求第一节上课的教室编号不能大于第二节上课的教室编号

i 个教室还需要满足

  • 第一节课必须恰好X_i 组学生在这里上课
  • 同一时间不能有超过 Y_i 组学生在该教室上课

答案对 10^9 + 7 取模,数据保证 1 \leq m, X_i, Y_i \leq 100X_i \leq Y_i

Example:当 n = 3, X = Y = (1, 1, 1) 时,一共有 3! = 6 种,因为所有人都不能够移动教室

Solution:我们先考虑对于第一节课确定的一种方案有多少种第二节课的安排,因为有只能往后移动教室这个限定,这个问题就有了明显的阶段性,用 f(i, j) 表示前 i 间教室,已经有 j 组第二节课已经确定完教室了的方案数,为了方便,记 S_n = \sum_{i=1}^n X_i,这样考虑 f(i, j) 可以给谁贡献答案,枚举第 i + 1 个教室有多少人第二节会在这里上,假设有 k 个,那么

 f(i + 1, j + k) \leftarrow {{S_{i + 1} - j} \choose k}f(i, j)

枚举的 k 的范围是 [0, \min ( Y_i, S_{i + 1} - j ) ]

然后最后还要计算出有多少种不同的第一节课方案,这乘上一个多项式系数就好了

 \text{ans} = {S_n \choose {X_1, X_2, \cdots, X_n}}f(n, S_n)

Codeforces 51E. Pentagon

Problem:给出一个有 n (n \leq 700) 个点 m 条边的无向图,统计有多少个五元环

Solution:可以考虑枚举一个五元环上的两个点,如果能够找到两条长度为 23 的不相交路径,那么就认为找到了一个五元环

因此可以先用 A_{u, v} 表示 uv 有多少条长度为 1 的路径,用 B_{u, v} 表示有多少条长度为 2 的路径,用 C_{u, v} 表示有多少条长度为 3 的路径(这里把 u \rightarrow a \rightarrow u \rightarrow v 这样的路径也算进去)

因为 B 可以由 AA 组合而成,C 可以由 AB 组合而成,因此用类似 Floyd 的方法,可以在 \mathcal O(n^3) 算出它们

然后来考虑如何统计答案,枚举五元环上两个点 u, v 直接计算 \sum_u \sum_v B_{u, v}C_{u, v},然后因为这样一个五元环会被重复计算 10 次,再除以 10,然而这样是会有不合法的情况,比如说下面这样

51E-Pentagon

我们会发现不合法的情况本质上是走了一次像 v \rightarrow a \rightarrow v 这样的路径,再加上一个三元环

或者说是一个三元环外面再伸出一条边,或者直接就是一个三元环

对于前面一种情况,我们枚举三元环,然后算一下伸出去多少条边,后面一种情况直接统计三元环个数,然后扣掉它们就好了

Codeforces 40E. Number Table

Problem:给出一个 n \times m 的矩阵,每个元素都是 1-1,其中有 k 个位置元素已经确定,并且这个矩阵满足每一行、每一列元素的乘积都是 -1,问有多少种不同的矩阵

数据范围是 1 \leq n, m \leq 1000, 0 \leq k < \max(n, m)

Solution:这题很关键的一点是注意到 k 严格小于 \max(n, m),这就意味着有一行或一列是完全空的,我们假设 n \geq m,那么就是存在一行完全空的,这样其它行可以无视列乘积为 -1 随便填数,最后用空的这一行补齐,可以知道只有唯一一种方案来补齐这个要求,这样问题就降了一维,只要求行乘积为 -1,如果当前行还有 s 个空格,已经有了奇数个 -1,那么方案数是

 \sum_{0 \leq i \leq s, 2 \nmid i} {s \choose i} = 2^{s - 1}

同样的,如果有偶数个 -1,那么方案数是 2^{s - 1},最后乘起来就好了

特别的情况是 nm 的奇偶性不同的时候是不存在方案的,还有就是已经确定的有一整行或者列都是 1,那么也不存在方案

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/06/codeforces-combinatorics-and-probabilities-problem

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

3 thoughts on “Codeforces 上的一些组合计数问题

  1. 不得不说,博主的每篇文章都用了通俗易懂的语言教会了蒟蒻我不少东西,O(∩_∩)O谢谢,良心博客,学习了^_^!

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.