牛客组合数学专题解题报告

• star 1
• • NC19788 Travel
  • NC50039 kotori
  • ICPC线上赛模拟 A
• star 2
• • NC14735 美丽的项链
• star 3
• • NC15251 白兔的式子
  • NC14599 子序列
  • NC15550 箱庭的股市
  • NC16543 NC20824
  • NC15077
  • NC16537
• star 4
• star 5

star 1

NC19788 Travel

题意为：将n个节点的树分成m个连通块，并对每个连通块标号的方案数。
思路：初看这道题像树形dp，但一想转移方程和数据范围，感觉不可解。
换成组合数学的角度，将分成m个连通块转化为删去m-1条边，显然删去m-1条边的方案与分成m个连通块的方案是一一对应的，再将连通块标号，就是乘m的阶乘了。
因此答案为：
( n − 1 m − 1 ) ∗ m ! \dbinom{n-1}{m-1}*m! (m−1n−1​)∗m!

NC50039 kotori

题意：n个1-m之间的数排成一排，相邻数不能相等的方案数。
思路：直接给公式： m ∗ ( m − 1 ) n − 1 m*(m-1)^{n-1} m∗(m−1)n−1
关键是扩展：n个1-m之间的数排成一个圆，相邻数不能相等的方案数。
思路：可以发现上面的公式 m ∗ ( m − 1 ) n − 1 m*(m-1)^{n-1} m∗(m−1)n−1计算的是n个1-m之间的数排成一个圆且首尾不相等的方案数 a n a_n an​和n个1-m之间的数排成一个圆但首尾相等的方案数，首尾相等的情况可以看作是n-1个1-m之间的数排成一个圆的方案数 a n − 1 a_{n-1} an−1​。
因此，扩展后的公式为 a n + a n − 1 = m ∗ ( m − 1 ) n − 1 ( n > = 3 ) a_n+a_{n-1}=m*(m-1)^{n-1}(n>=3) an​+an−1​=m∗(m−1)n−1(n>=3)
由此解得 a n a_n an​的通项公式为：
a n = ( m − 1 ) n + ( m − 1 ) ∗ ( − 1 ) n − 2 ( n > = 2 ) a_n=(m-1)^{n}+ (m-1)*(-1)^{n-2}(n>=2) an​=(m−1)n+(m−1)∗(−1)n−2(n>=2)
a 1 = m a_1=m a1​=m
但是我们可以用更普遍的断环成链的做法得出答案，同样可以在 O ( l g n ) O(lgn) O(lgn)得出结果。
对于第一个数取k的情况，考虑 f [ i ] [ 1 ] f[i][1] f[i][1]为第i个数为k的方案数 f [ i ] [ 0 ] f[i][0] f[i][0]为第i个数不为k的方案数，转移方程如下：
f [ 0 ] [ 1 ] = 1 f[0][1]=1 f[0][1]=1
f [ i ] [ 1 ] = f [ i − 1 ] [ 0 ] f[i][1]=f[i-1][0] f[i][1]=f[i−1][0]
f [ i ] [ 0 ] = ( m − 1 ) ∗ f [ i − 1 ] [ 1 ] + ( m − 2 ) ∗ f [ i − 1 ] [ 0 ] f[i][0]=(m-1)*f[i-1][1]+(m-2)*f[i-1][0] f[i][0]=(m−1)∗f[i−1][1]+(m−2)∗f[i−1][0]
最后答案为 f [ n ] [ 1 ] ∗ m f[n][1]*m f[n][1]∗m，用矩阵加速即可达到目标复杂度。
再扩展：洛谷P1357
这道题同样是断环成链的方法，类似上题。
首先我们预处理出所有从状态k1转移到k2的情况。
然后，对于每一个初始状态 i i i，我们令 f [ 0 ] [ i ] = 1 f[0][i]=1 f[0][i]=1，其余为0，根据转移方程：
f [ i ] [ k 2 ] = ∑ j ∈ k 1 f [ i − 1 ] [ j ] f[i][k2]=\sum_{ {j\in{k1}}}f[i-1][j] f[i][k2]=∑j∈k1​f[i−1][j]，其中k1为所有转移到k2的状态集合。
利用矩阵加速求得 f [ n ] [ i ] f[n][i] f[n][i]，最后答案 a n s = ∑ i = 0 2 m − 1 f [ n ] [ i ] ans=\displaystyle\sum_{i=0}^{2^m-1}f[n][i] ans=i=0∑2m−1​f[n][i]

ICPC线上赛模拟 A

题意：求满足 x + y + z = k ( x ∈ [ 0 , a ] , y ∈ [ 0 , b ] , z ∈ [ 0 , c ] , k ∈ [ 0 , d ] ) x+y+z=k(x\in [0,a],y \in [0,b],z \in [0,c],k \in [0,d]) x+y+z=k(x∈[0,a],y∈[0,b],z∈[0,c],k∈[0,d])的解的个数。
思路：其实在写美丽的项链这题的时候已经想到了，通常求 x + y + z + … … = k x+y+z+……=k x+y+z+……=k类似的不定方程的做法都是转化为小球分区间的问题，但是如果加上范围，该如何做？
直接用组合公式做？容斥做？好像都不太行，我最后便选择了最暴力的枚举，枚举 k − z k-z k−z的值。
但这种方法最多只能支持4个未知数的求解，该算法复杂度随未知数的增多呈指数型增长。
该题的扩展：
利用反演的思想将复杂度降到根号级别。
暂时还没有想到好方法。

star 2

NC14735 美丽的项链

事实上这道题是一道基础DP题，我把它扩展了一下，算是复习一下多重排列。
题意（扩展后的）：n个盒子，每个盒子中取l[i]-r[i]个数，共取m个，组成圆排列的方案数。
思路：暴搜+多重圆排列公式。
多重排列公式： n ! n 1 ! n 2 ! … … n k ! \frac{n!}{ {n_1}!{n_2}!……{n_k}!} n1​!n2​!……nk​!n!​，再除个n就是圆排列的结果。

star 3

NC15251 白兔的式子

题意： f [ 1 ] [ 1 ] = 1 , f [ i ] [ j ] = a ∗ f [ i − 1 ] [ j ] + b ∗ f [ i − 1 ] [ j − 1 ] ( i > = 2 , 1 < = j < = i ) f[1][1]=1,f[i][j]=a*f[i-1][j]+b*f[i-1][j-1](i>=2,1<=j<=i) f[1][1]=1,f[i][j]=a∗f[i−1][j]+b∗f[i−1][j−1](i>=2,1<=j<=i)求 f [ n ] [ m ] f[n][m] f[n][m]
思路：直接推空间时间双炸，推到最后肯定推到 f [ 1 ] [ 1 ] f[1][1] f[1][1]，于是考虑能够推得多少个 f [ 1 ] [ 1 ] f[1][1] f[1][1]即，从 ( 1 , 1 ) (1,1) (1,1)到 ( n , m ) (n,m) (n,m)有多少条路径，找规律可得，直走 n − m n-m n−m次，斜走 m − 1 m-1 m−1次，直走每次乘 a a a,斜走每次乘 b b b。
于是，答案即为： ( n − 1 n − m ) ∗ a n − m ∗ b m − 1 \dbinom{n-1}{n-m}*{a}^{n-m}*{b}^{m-1} (n−mn−1​)∗an−m∗bm−1

NC14599 子序列

题意：给定一个小写字母字符串T求有多少长度为m的小写字母字符串S满足，T是S的一个子序列(不需要连续)设T的长度为n
思路：直接想式子，重复情况难剔除。再想DP，空间时间双炸。借鉴上面模拟赛A的解法，开始暴力枚举。
枚举S中刚好出现T的长度 i i i，第 i i i个字母就是T的最后一个字母，且前 i − 1 i-1 i−1个字母不含T， [ i + 1 , m ] [i+1,m] [i+1,m]之间可以随意放字母 2 6 m − i 26^{m-i} 26m−i。
为前 n − 1 n-1 n−1个字母在 i − 1 i-1 i−1的范围内选好位置， ( i − 1 n − 1 ) \dbinom{i-1}{n-1} (n−1i−1​).
最后 i − n i-n i−n个位置怎么放，怎么处理重复情况。
显然，第 k k k个位置上不能放之后第一个已经摆好位置的字母，于是有 2 5 i − n 25^{i-n} 25i−n个摆法，可以证明，不会有重复的情况（其实这里可以借鉴枚举的方式，即刚好出现这个字母）。
因此答案为： ∑ i = n m 2 6 m − i ∗ ( i − 1 n − 1 ) ∗ 2 5 i − n \displaystyle\sum_{i=n}^{m}26^{m-i}*\dbinom{i-1}{n-1}*25^{i-n} i=n∑m​26m−i∗(n−1i−1​)∗25i−n

NC15550 箱庭的股市

题意：太长了。。。
思路：先打表，找到以下的规律：
设 f [ i ] [ j ] f[i][j] f[i][j]为第 i i i天第 j j j秒的价格。
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − 1 ] ( i > 1 ) f[i][j]=f[i-1][j]+f[i-1][j-1](i>1) f[i][j]=f[i−1][j]+f[i−1][j−1](i>1)
f [ i ] [ j ] = p ( i = 1 ) f[i][j]=p(i=1) f[i][j]=p(i=1)
借鉴上面白兔的式子的做法，考虑路径数目，这里有一点不一样，所有第一行 ( i = 1 ) (i=1) (i=1)的点都可以作为终点。
因此答案即为： ∑ i = 0 y ( x i ) \displaystyle\sum_{i=0}^{y}\dbinom{x}{i} i=0∑y​(ix​)

NC16543 NC20824

话不多说，直接给处理这种组合数相乘的两个公式：
∑ i = 0 n ( n i ) 2 = ( 2 n n ) \displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^2=\dbinom{2n}{n} i=0∑n​(in​)2=(n2n​)
证明思路：考虑 ( 1 + x ) 2 n (1+x)^{2n} (1+x)2n中 x n x^n xn的系数与 ( 1 + x ) n ∗ ( 1 + x ) n (1+x)^n*(1+x)^n (1+x)n∗(1+x)n中 x n x^n xn的系数的计算方法。
∑ i = 0 k ( n i ) ∗ ( m k − i ) = ( m + n k ) \displaystyle\sum_{i=0}^{k}\dbinom{n}{i}*\dbinom{m}{k-i}=\dbinom{m+n}{k} i=0∑k​(in​)∗(k−im​)=(km+n​)
证明思路：上一个式子的扩展。
直接带就完事了。

NC15077

卡特兰数扩展：折线法。
这里只介绍这种方法的通式。
假如我要从 ( 0 , 0 ) (0,0) (0,0)走到 ( m + n , n − m ) (m+n,n-m) (m+n,n−m)，其中， n n n步斜向上走， m m m步斜向下走，条件是不能走到 y y y轴以下的部分。
利用容斥原理，总的方案数是 ( n + m n ) \dbinom{n+m}{n} (nn+m​)，扣除掉不合法的情况，即为 ( 0 , − 2 ) (0,-2) (0,−2)走到 ( m + n , n − m ) (m+n,n-m) (m+n,n−m)，其中， n + 1 n+1 n+1步斜向上走， m m m步斜向下走的方案数。
因此合法方案数为： ( n + m n ) − ( n + m n + 1 ) \dbinom{n+m}{n}-\dbinom{n+m}{n+1} (nn+m​)−(n+1n+m​)
这个方法在处理卡特兰数相关问题有极大的用处，尤其是栈的压入弹出操作的计数。

NC16537

先给出三个相关公式：
n n n条直线划分平面，最多划分出多少个部分？
n ( n + 1 ) / 2 + 1 n(n+1)/2 +1 n(n+1)/2+1
n n n个平面划分空间，最多划分出多少个部分？
( n 3 + 5 n + 6 ) / 6 (n^3+5n+6)/6 (n3+5n+6)/6
n n n条直线划分空间，最多划分出多少个部分？
( n ∗ ( n + 1 ) / 2 + 1 ) ∗ ( n 3 + 5 n + 6 ) / 6 (n*(n+1)/2+1) * (n^3+5n+6)/6 (n∗(n+1)/2+1)∗(n3+5n+6)/6
三个公式的证明方法都是直接递推找增加的部分。
但很可惜的是，这三个公式对这道题没有丝毫帮助。
考虑平面图上的欧拉公式 n − m + r = 2 n-m+r=2 n−m+r=2其中 n n n为顶点数， m m m为边数， r r r为面数。
要求 r r r的值。
首先看顶点数，完全图内每两条对角线交出一个点，有 ( n 4 ) \dbinom{n}{4} (4n​)个，加上圆周上的 n n n个。
再看边数，直接不好求，转化为顶点的度数除以2，完全图内的点的度数都是4，圆周上的点的度数都是 n + 1 n+1 n+1，总边数为 2 ∗ ( n 4 ) + ( n ) ∗ ( n + 1 ) / 2 2*\dbinom{n}{4}+(n)*(n+1)/2 2∗(4n​)+(n)∗(n+1)/2
这样 r r r的值就很好求了。

star 4

star 5