首页 > 其他分享 >组合数学与计数原理

组合数学与计数原理

时间:2022-11-12 17:01:36浏览次数:66  
标签:le dbinom 组合 min max sum 计数 数学 考虑

排列数

\(P_n^m = \cfrac{n!}{(n-m)!}\)

组合数

\(\dbinom{n}{m} = \cfrac{n!}{(n-m)!m!}\)

抽屉原理

\(n\) 个球放在 \(m\) 个箱子中,每个箱子至少有 \(\lceil\cfrac{n}{m}\rceil\) 个球。

容斥原理

若有集合 \(S = s_1 \bigcup s_2 \bigcup ... \bigcup s_n\),那么 \(|S| = \sum \limits_{T \subseteq S} (-1)^{|T|-1} |\bigcap\limits_{x \in T} x| (T \neq \varnothing)\)

min-max 容斥

对于 \(x\) 和 \(y\) 我们有 \(E(x) + E(y) = E(x + y)\)。
但是我们没有 \(\max\{E(x), E(y)\} = E(\max(x,y))\)。\(min\) 同理。那么我们需要计算后面这个东西怎么办呢?

考虑 \(\max(S)\) 表示 \(S\) 集合中的最大值,\(\min(S)\) 相反。那么有

\[\max(S) = \sum \limits_{T \subseteq S} (-1)^{|T|-1} \min(T) \\ \min(S) = \sum \limits_{T \subseteq S} (-1)^{|T|-1} \max(T) \\ (T \neq \varnothing) \]

为什么呢?考虑对于 \(\max(S)\),如果它等于 \(\min(T)\),那么 \(T = \{\max(s)\}\)。
对于其他集合,证明它们都会被抵消。考虑 \(T = \{x, y_1, ...,y_k\}\),其中 \(x = \min(T)\)。那么考虑 \(y\) 为 \(S\) 中第一个大于 \(x\) 的数。考虑 \(T'\),如果 \(y \in T\),那么 \(T' = T\) 排除 \(y\)。否则 \(T' = T \cup \{y\}\)。容易证明 \(T\) 和 \(T'\) 一一对应,并且求和之后为 \(0\)。
因此一共 \(2^n - 1\) 个真子集,减去一个 \(T = \{\max(s)\}\) 之外所有集合都可以两两配对,最后消掉。
因此结论成立。

如果知道其中一个,就可以 \(O(2^n)\) 知道另一个。

HDU4336

【题意】
有 \(n\) 种卡片,每开一个袋子,有 \(p_i\) 的概率开出第 \(i\) 种。保证 \(\sum p_i \le 1\)。求要集齐所有卡片至少一张的期望开卡次数。
\(n \le 20\)

【分析】
考虑 \(x_i\) 为收集到第一张 \(i\) 卡片的期望开卡次数。那么我们要求 \(E(\max\{x_i\})\)。
而我们有 \(E(\min\{x_i\}) = \cfrac{1}{\sum p_i}\)。于是可以做了。

捆绑法/插空法

\(20\) 个人排队,\(A\) 和 \(B\) 相邻。求方案数?

将他们两个人捆绑在一起视为一个人,答案为 \(19! \times 2!\)。

\(20\) 个人排队,\(A\) 和 \(B\) 不相邻。求方案数?

考虑其他 \(18\) 个人先排,然后 \(A\) 和 \(B\) 分别插进空里。答案为 \(18! \times P_{19}^2\)。

P3166

【题意】
给定一个 \(N×M\) 的网格,请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

\(N,M\le 1000\)
【分析】
考虑容斥。横着和竖着共线是容易的。考虑斜着共线怎么算。

考虑枚举 \(i,j\),那么 \((0,0)\) 和 \((i,j)\) 这两个点和 \(\gcd{(i,j)} - 1\) 个不同的点共线。注意为什么 \(-1\),因为不能是和 \((i,j)\) 共线。

时间复杂度 \(O(n^2)\)。

有 \(O(n)\) 做法,需要用到莫比乌斯反演和欧拉反演。待补

https://www.luogu.com.cn/blog/emptyset/solution-p3166

卡特兰数

递推式:\(C_n = \sum \limits_{i=0}^{n-1} C_i C_{n-1-i}\)

什么意义?考虑 \(n\) 个节点形成的二叉树的形态数。一个根,左子树 \(0 \sim n-1\) 个节点,右子树 \(n-1-i\) 个节点。

还有什么意义?\(n\) 对括号形成合法括号序列的方案数。考虑第一个括号和哪一个括号匹配,这两个括号中间和后面分成两个区域。

还有什么意义?\(n\) 边形三角划分数,这一块还需要加 \(n-2\) 条边,加了一条边之后分成了两块。

考虑其通项公式:\(C_n = \dbinom{n}{2n} - \dbinom{n+1}{2n}\)。

考虑从 \((0,0)\) 开始一步只能往右边或上面走,走到 \((n,n)\) 并且不能超过对角线的方案数,容易证明它等于卡特兰数。

考虑容斥。对于没有不能超过对角线的性质,方案数是 \(\dbinom{n}{2n}\)。

对于超过对角线的方案,在第一次超过之后每一次都取反,最后一定走到 \((n-1,n+1)\)。因为这个点在对角线上方,容易证明这样的方案与原方案一一对应。方案数是 \(\dbinom{n+1}{2n}\)。

也可以换一个形式,\(C_n = \cfrac{\dbinom{n}{2n}}{n+1}\)。

卢卡斯定理

当 \(p\) 是素数时,

\(\dbinom{n}{m} \mod p = \dbinom{n/p}{m/p} \dbinom{n \bmod p}{m \bmod p} \mod p\)

可以用来求解 \(n,m \ge p\) 的 \(\dbinom{n}{m}\)。时间复杂度 \(O(p + \log_p n)\)。

当 \(p\) 不是素数时,有扩展卢卡斯定理。待补

https://oi-wiki.org/math/number-theory/lucas/

P4478

【题意】
小B 所在的城市的道路构成了一个方形网格,它的西南角为 \((0,0)\),东北角为 \((N,M)\)。

小B 家住在西南角,学校在东北角。现在有 \(T\) 个路口进行施工,小B 不能通过这些路口。小B 喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小B又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小B 只需要让你求出路径数 \(\bmod P\) 的值。
\(N,M\le 10^9, P = 1000003\) 或者 \(1019663265=3 \times 5 \times 6793 \times 10007, T \le 100\)
【分析】
先对障碍按 \((x,y)\) 排序,这样一定只会从前面的障碍跳到后面的障碍。
令 \(f_i\) 表示到第 \(i\) 个点且不经过任何障碍的方案数。
\(g_{i,j}\) 表示第 \(i\) 个点走到第 \(j\) 个点的方案数。这个是卡特兰数,需要卢卡斯定理算组合数。
然后有:

\[f_i = g_{0, i} - \sum g_{j, i} \times f_i \]

不会算重是因为“不经过任何障碍”。

矩阵优化计数

矩阵乘法是“行 × 列”原则,也就是答案矩阵的第 \(i\) 行第 \(j\) 列是由左矩阵的第 \(i\) 行乘以右矩阵的第 \(j\) 列得到。

对于 \(n\) 阶 \(k\) 层递推,时间复杂度为 \(O(n^3 \log k)\)。

实际上可以用 FFT 优化到 \(O(n \log n \log k)\),但是现在不需要会(也差不太多)。

主要是代码实现问题需要注意。

P3216

【题意】

小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题:

给定正整数 \(n,m\),要求计算 \(\text{Concatenate}(n) \bmod \ m\) 的值,其中 \(\text{Concatenate}(n)\) 是将 \(1 \sim n\) 所有正整数 顺序连接起来得到的数。

例如,\(n = 13\) , \(\text{Concatenate}(n) = 12345678910111213\)。小C 想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。
\(n \le 10^{18}, m \le 10^9\)

【分析】
考虑线性递推。
我们有:\(f_i = f_{i - 1} \times 10^k + i\),其中 \(k \in [1,18]\)。
考虑怎么转化为矩阵递推式:

\[\begin{bmatrix}10^k&1&1\\0&1&1\\0&0&1\end{bmatrix} \begin{bmatrix}f_{i-1}\\i-1\\1\end{bmatrix} = \begin{bmatrix}f_{i}\\i\\1\end{bmatrix} \]

分 \(18\) 块处理,剩下的问题在于实现。

行列式

代数余子式:对于 \(1 \le i,j \le n\),在 \(n\) 阶行列式中所有不属于第 \(i\) 行也不属于第 \(j\) 列的元素按照原来的顺序组合成一个 \(n-1\) 阶余子式,它叫做 \(A_{i,j}\) 也就是原矩阵中元素 \(M_{i,j}\) 的代数余子式。
一个 \(n\) 阶行列式的值等于:

\[\sum \limits_{i/j=1}^n a_{i,j}(-1)^{i+j} A_{i,j} \]

其中 \(i,j\) 其中一个任选。也就是说,任意行(或者列)的元素与之对应的代数余子式乘积之和。

性质:

  • 交换某两行/列,行列式的值 *= -1。
  • 一行(列)加上另一行(列),行列式的值不变。
  • 一行/列乘上 \(k\),行列式的值 *= k。

标签:le,dbinom,组合,min,max,sum,计数,数学,考虑
From: https://www.cnblogs.com/Zeardoe/p/16884139.html

相关文章

  • 算法题不等式计数问题常见解法-归并排序
    类型1:单个边界范围f(i)<d(j)这种格式的不等式,算法题经常询问我们满足这样的数对有多少。中间的符号也可换成任何等号不等号,也同样适用怎么计算呢?本质上,使用归并排序就是下面......
  • 2023-李林六套卷-数学一
    2023-李林6-1T11恒等变换\(\arctan\dfrac{1+x}{1-x}=\dfrac\pi4+\arctanx\),另外再补充一个\(\arctanx+\arctan\dfrac1x=\begin{cases}\frac\pi2&,\,x>0\\-\frac\pi2&......
  • 2022-李林六套卷-数学一
    2022-李林6-1T3条件收敛,则奇和、偶和发散;\(∑奇偶项之差=∑(-1)^ⁿa_n\)T6快速求正负惯性系数——不做行变换地将\(A\)阶梯化T8\(|P(AB)-P(A)P(B)|<\frac{1}{4}......
  • 2022-李林四套卷-数学一
    2022-李林4-1T14\(\iiint(x+y+z)\,\mathrm{d}v\),注意轮换对称性(另外对于这种一次方的,也要注意能不能用上形心)T16\(Y={\rme}^X\)(或类似的严格单调函数),则关于\(Y\)求......
  • 2022-方浩十套卷-数学一
    2022-方浩10-1本来只打算做小题,但小题仿佛没啥可讲的。。T16在\(X=\dfrac14\)的条件下,\(Y\)的条件概率密度函数表达式为\(f_{Y|X}(y|x=\dfrac14)\)——按规范这么......
  • 2023-李艳芳三套卷-数学一
    2023-李艳芳3(1)-1T1\(\sqrt{x+\sqrt{x}}\nsim\sqrt{x},\,\tan(x+\sqrt{x})\nsimx\),直接无脑令\(\sqrt{x}=t\)出错可能性会小一点T3\(\displaystyle\int_0^{\frac1......
  • 2022-李艳芳三套卷-数学三
    2022-李艳芳3(3)-1T3比较几个值的大小,也有可能是二重积分——\(\displaystyle\sqrt{2\pi(1-{\rme}^{-1})}=\sqrt{\iint_{x^2+y^2\leqslant2}{\rme}^{-\frac{x^2+y^2......
  • 2022-李艳芳三套卷-数学二
    2022-李艳芳3(2)-1T1数列求极限,见到诸如\((n+1)^k-n^k\)的,可以考虑Lagrange中值定理T2易错:洛必达可用的前提是导函数连续(不连续时不一定可用),尤其在选择题中可能会设......
  • 2022-李艳芳三套卷-数学一
    2022-李艳芳3(1)-1T6\(A\)的零化多项式\(f(\lambda)=0\)无重根,则\(A\)可对角化T9\(X,\,Y\)独立,充要条件是\(X,\,Y\)的联合分布两行成比例T11Stolz定理T14做......
  • 51单片机定时器/计数器中断
    51单片机定时器/计数器中断一、定时器/计数器1-1定时器❤CPU时序相关知识点振荡周期:为单片机提供定时信号的振荡源的周期状态周期:2个振荡周期为1个状态周期,其中振......