排列组合

Vision271 · 2022-07-23 15:30:24 · 个人记录

概述

排列数

• 从定义来求。A_n^m=n\times (n-1)\times \dots \times (n-m+1)=\dfrac{n!}{(n-m)!}

组合数：

• 可以借助 A。C_n^m=\dfrac{n\times (n-1)\times \dots \times (n-m+1)}{A_m^m}=\dfrac{n!}{m!(n-m)!}

简单性质

• 排列只谈一个：错位排列。

  • 求错位排列数。

    • 显然可以容斥但是也显然不可接受，考虑一种递推做法。

    • 记 D_i 为 1\sim i 的错位排列数，对于 D_{i+1}，容易看出，我们有：

    • 证明如下：

    • 考虑新增的一个数往哪里放。

    • 如果其原本就是一个完整的错排，那么我们可以将 i+1 与任意一个数交换。

    • 如果其本身不是一个完整的错排，那么必然只存在一个 j\ s.t.\ a_j=j，否则不可能在只处理新增的 i+1 的前提下将之化为一个 i+1 的错排。

    • 从而其“对排处”有 i 种选择，综上，证毕。

• 以下都是组合性质。鉴于组合有着极为优异的递推性，我们往往把排列问题化归成组合-阶乘问题。

组合数，杨辉三角与二项式定理

• 我们先来看一张杨辉三角。为了符合信竞的习惯，坐标轴已经做过了调整，左上角的第一个为 C(0,0)。

• 我们知道，杨辉三角的实质是组合数，其具有如下的性质：(i,j)=(i-1,j-1)+(i-1,j)。

• 这实质上可以通过 dp 得到。考虑我们已经有了 C_i，如何求 C_{i+1}^j？

• 分两种情况讨论：

  • 选第 i+1 个数，则方案数相当于在前 i 个数中选 j-1 个数的方案数，即 C_i^{j-1}。

  • 不选第 i+1 个数，则方案数相当于在前 i 个数中选 j 个数的方案数。

  • 综上，我们有 C_i^j=C_{i-1}^{j-1}+C_{i-1}^j。

• 利用这一性质，我们可以进行如下的简单求和：

  • 求对角线和（杨辉三角的对角线定义为平行于斜边的线），即求 \sum\limits_{k=0}^lC_{i+k}^{j+k}。

    • 考虑配凑一个。

    • 配首项 C_i^j 左边的那一项 C_i^{j-1}，从而两者相加得到 C_{i+1}^{j}，恰为第二项 C_{i+1}^{j+1} 的左边一项，从而全部合并。

    • 从而我们有 \sum\limits_{k=0}^{l}C_{i+k}^{j+k}=C_{i+l+1}^{i+l}-C_i^{j-1}。

  • 求列和，即求 \sum\limits_{k=0}^lC_{i+k}^j。

    • 同上，配首项的右项 C_i^{j_+1}。

    • 从而我们有 \sum\limits_{k=0}^lC_{i+k}^j=C_{i+l+1}^{j+1}-C_i^{j+1}。

  • 求行和，即求 \sum\limits_{k=0}^l C_i^{j+k}。

    • 这个真没法直接求，但我们可以 O(1) 地从当前行递推到下一行。

    • 容易看出，2\sum\limits_{k=0}^l C_{i-1}^{j+k} 合并后为 \sum\limits_{k=0}^l C_i^{j+k}-C_i^j+C_{i-1}^j+C_{i-1}^{j+l}。

    • 从而有 \sum\limits_{k=0}^l C_i^{j+k}=2\sum\limits_{k=0}^l C_{i-1}^{j+k}+C_i^j-C_{i-1}^j-C_{i-1}^{j+l}。

    • 单次递推无法 O(1)，但如果是连续递推的话，我们可以存下上次的边界处理结果，从而根据组合数的定义式可以很容易地递推新的边界处理。

• 二项式定理：(a+b)^n=\sum\limits_{k=0}^nC_n^ia^kb^{n-k}。

  • 证明比较显然，毕竟拆括号相当于任意对位乘。而其中 a 的次数为 k 的就相当于选了 k 个括号取 a。

  • 二项式定理的结果展开后，如果按 a 降次排序，系数恰为 n 行的杨辉三角（注意杨辉三角最上面那行是第 0 行）。

各种实际解题里面可能用到的奇怪模型

• 以下所有结论都可以通过暴力推式子得到，但不建议那么做。

• 同一个式子有很多种化法，但关键的是它们的实际意义。这才是我们需要的。

• 咕了。

可重组合

• 从 n 个数中可重地选出 k 个数的方案数为 C(n+k-1,k)。

• 不妨将第 i 个数被选取的次数记为 x_i，则该问题等价于求方程 x_1+x_2+\dots+x_n=k(x_i\geqslant 0) 的解集数。

• 则可以将之视为把 k 个球用 n-1 个隔板分成 n 段的方案数。C(n+k-1,n-1)=C(n+k-1,k)，得证。

• 可重排列显然是 n^k，故不予讨论。

• 可重集的排列组合，目前我会的方式主要是 DP，即转化成 \sum\limits_{i=1}^m x_i(0\leqslant x_i \leqslant a_i)=k 来做，其中 m,a_i,x_i 分别为元素种数，第 i 种元素的个数和选的个数。

  • 组合有生成函数解法，但 NTT，故略。

  • 排列的话，DP 中需要不断 C 出插进去的系数。

求组合数

• 杨辉三角，O(n^2)。

• 极大时唯一解法是质因数分解。

• 如果是在 \bmod\ p 意义下的，较小的可以求阶乘的逆元，较大的可以利用下面的

Lucas 定理：

• 别问，问就不会证。

• 式右首项可以递归求解。

• 从而总复杂度为预处理 O(p)，单次 O(\log_p n)。

• 是广义组合数，如果待选项比需选项少就是 0。

例题

• 这里大概放一些和计数相关的例题。

[ABC281G] Farthest City

• 题意略。

• 容易想到设计 dp 状态为 dp_{i,j} 表示 i 个点构成的图，最深层有 j 个点的方案数。初始化为 dp_{1,1}=1，但发现好像没法转移：

• 新加一个点加到第 k 层怎么办呢，即使我们只要求往最后一层加点，似乎也没法整啊...这需要倒数第二层的点数，然后又可能要在这一维上转移，又需要倒数第三层...无穷递归了。

• 发挥 DP 的思想：最优子结构。已有的子结构，你不要去动它。每次暴力转移一整层新的出来！

• 转移系数：层内随意连边，层间每个点至少有一个连。即，dp_{i,j}\to dp_{i+k,k}(2^{C_k^2}\times (\sum\limits_{l=1}^j C_j^l)^k)。

• 实际上推一下组合意义（当然暴力化式子也行）会发现 \sum\limits_{l=1}^j C_j^l=2^j-1，即爱连不连但不许全都不连。

• 那么注意到 2^j 可以预处理，于是两个系数都可以随着 k 的增大 O(1) 递推到新系数，没有 \log，很优秀（事实上带 \log 实现精细也容易过）。

P3773 [CTSC2017] 吉夫特

• 题意略。

• 我会暴力 DP！注意到“是奇数”相当于“所有 2 全部消掉”，且发现所求的式子可以化为 \dfrac{a_{b_1}!}{a_{b_k}!\prod_{i=1}^{k-1} (a_{b_i}-a_{b_{i+1}})!}，于是设计如下 DP：

  • 状态设计：dp_{i,j} 表示考虑了前 i 个元素，包含 i 且含 j 个 2 的所有“半序列”个数。

    • 所谓半序列，即只计算了分子和分母中的后一项，在尾部还有端口的子序列。

  • 初始化：dp_{i,get2(a_i!)}=1。注意到其实 get2() 就是 ctz()，但阶乘太大，不过我们可以预处理，直接把 ctz() 连乘就好啦。

  • 状态转移：

• 分析一下复杂度，发现对于 n=2017 这一档分绰绰有余（打表发现第二维的大小至多 2010），O(n^2) 暴力即可获得 70 分！

• 但这和正解毫无关系（自豪）！正解的话...我们得抛弃“奇偶性”。