组合计数 杂题

· · 个人记录

组合数学

CF1523E Crypto Lights

思路

设 f_i 表示点亮 i 盏灯然后立即结束的概率，那么期望答案应该等于 \sum_{i\in [1,n]}i\cdot f_i。

定义 g_i=\sum_{j\in [i,n]}f_j，那么答案也可以表示为 \sum_{i\in [1,n]}g_i。

有 $$ g_i=\dfrac{\dbinom{n-(i-1)-(i-2)(k-2)+2-1}{i-1}}{\dbinom{n}{i-1}}=\dfrac{\dbinom{n-(k-1)(i-2)}{i-1}}{\dbinom{n}{i-1}} $$ 即先放出来在 $i-1$ 个，再在 $i-1$ 个的空隙中插入不放的，每个空至少插入 $k-1$ 个，两边的空可以不放。经典的插板法。 ## P7481 梦现时刻 ### 思路 首先，形象化地，$F(a,b)\ (a,b\le m)$ 可以看作是 $n$ 个球，前 $b$ 个球中选出任意个（可以不选），再从剩下的球中选出 $a$ 个的方案数。 设 $f_{i,j}=F(j,i)\ (i,j\le m)$，即 $n$ 个球，前 $i$ 个球中选出任意个（可以不选），再从剩下的球中选出 $j$ 个的方案数。 为了方便转移，设 $g_{i,j}$ 为 $f_{i,j}$ 在不选第 $i+1$ 个球时的方案数。 $$ f_{i,j}=f_{i-1,j}+g_{i-1,j} $$ $$ g_{i,j}=f_{i,j}-g_{i,j-1} $$ $f_{i.j}$ 若不选第 $i$ 个，答案为 $f_{i-1,j}$，后边还可以再选第 $i$ 个；若选，答案为 $g_{i-1,j}$，后边就不能再选了。 $g_{i,j}$ 就是总方案数减去选第 $i+1$ 个的方案数 $g_{i,j-1}$。 $$ \binom{n}{i}=\dfrac{n!}{(n-i)!\ i!}=\dfrac{n!}{(n-i+1)!\ (i-1)!}\cdot \dfrac{n-i+1}{i} $$ ## P4071 [SDOI2016] 排列计数 ### 思路 赤裸裸的错排模板。 公式：$f_{i}=(i-1)(f_{i-1}+f_{i-2})$。 证明：考虑 $f_i$，若 $a_1=j$，此时若 $a_j=1$，答案为 $f_{i-2}$；若否，答案为 $f_{i-1}$。 ## P6189 [NOI Online #1 入门组] 跑步 / 【模板】分拆数 ### 思路 DP……也算计数吧。 朴素的完全背包 $\mathcal{O}(n^2)$：设 $f_i$ 表示和为 $i$ 的方案数，初始 $f_0=1$。 令 $m=\sqrt{n}$，把 $n$ 看作小于 $m$ 的和大于等于 $m$ 的数拼出来。 计算小于 $m$ 的数的贡献可以直接背包，时间复杂度 $\mathcal{O}(n\sqrt{n})$。 再算大于等于 $m$ 的数的贡献。 结论：序列 $\{a_i\}\ (a_i\ge m)$，一定可以看作是由下面两种操作产生的，且若序列 $a\ne b$，则 $a$ 的操作序列 $\ne $ $b$ 的操作序列。 1. 将 $m$ 插入到 $a$ 的末尾； 1. 把所有的 $a_i$ 加 $1$。 于是就可以 DP 了，$g_{i,j}$ 表示用 $i$ 个大于等于 $m$ 的数拼出 $j$ 的方案数，显然 $i\le \sqrt{m}$。 $g_{0,0}=1$，$g_{i,j}=g_{i,j-i}+g_{i-1,j-m}$，对应上面两种操作。 最终答案等于 $$ \sum_{i\in [0.n]} f_i \sum _{j\in [0,m]} g_{j,n-i} $$ ## P4448 [AHOI2018 初中组] 球球的排列 ### 思路 评价：毒瘤。 不能相邻的关系具有传递性，即若 $a$ 与 $b$ 不可以相邻，$b$ 与 $c$ 不可以相邻，则 $a$ 与 $c$ 不可以相邻。 不能相邻的球组成了若干个连通块，并查集合并一下，对每个连通块规定一个颜色，按所在连通块的颜色排序。 DP，设 $f_{i,j,k}$ 表示前 $i$ 个球组成的排列中，满足颜色不等于第 $i$ 个球且同色相邻的有 $j$ 对，颜色等于第 $i$ 个球且相邻的有 $k$ 对时，排列的方案数。答案就是 $f_{n,0,0}$。 对颜色第一次出现的球和不是第一次出现的球分讨转移一下就行了，具体见 [xcxcli's luogu blog](https://www.luogu.com.cn/blog/xcxcli/P4448)。