计数专题

· · 个人记录

打了不少模拟赛了，发现计数题，经常，老是，总是不会写，现特开一专题总结计数相关问题，尤其是序列计数和排列计数问题。

一 错排数

求不存在 i=p_i 的排列 P_n 的个数。

递推式：

D_0=1,D_1=0 D_i=nD_{i-1}+(-1)^{n}

错排数增长极快，与阶乘只有常数级别的差距。随机排列形成错排的概率接近： \large \frac{1}{e}

二 Raney 引理

一个**整数数列** $A_n$，记 $s_n$ 为其前缀和。若 $s_n=1$，则 $A_n$ 的所有循环位移中，有且仅有唯一一个循环位移，使得 $$\large \forall_i,s_i>0$$ --- ### 应用 1 给你一个非负整数数列，满足 $s_m=m$，求其所有排列中，满足$(P)$ 的方案数。 $$\large \forall_i, s_i-i \ge 0$$ - [P6672 [清华集训2016] 你的生命已如风中残烛](https://www.luogu.com.cn/problem/P6672)。 我们把那个 $-i$ 均摊到每一项中去，这样就把它消掉了影响。但是这时候还不能直接用 $Raney$ 引理，因为此时 $s'_n =0$ 且 不等号是 $\ge$ 而不是 $>$。 强制在数列最后加上一个 $-1$，再把数列翻转，所有符号取反，这是全等变换的。 “ 1. 前缀和大于等于 $0$，且数列总和为 $0$，说明数列的后缀和小于等于 $0$； 2. 在数列末端插入 $-1$，新数列的后缀和小于等于 $-1$； 3. 倒转数列，新数列的前缀和小于等于 $-1$； 4. 符号取反，不等号方向改变，新数列的前缀和大于等于 $1$，即大于 $0$。 ” 这时候此题已被完美转化成了 $Raney$ 引理的 样子了，答案为 $\frac{(m+1)!}{m+1}= m!$ 吗？ 不是的，我们加了一个$-1$，这个 $-1$ 会和原来 $m-n$ 个从 $0$ 被均摊到 $-1$ 的数产生重复的排列贡献，这时候还要除强制加入 $-1$ 的贡献，答案即 $\large \frac{m!}{m-n+1}

三 组合计数

任意模数组合数·扩展卢卡斯定理。

应用 1

由插板法，答案即为 $\large C_{n+m-1}^{n-1} $。直接上扩展卢卡斯模板。 ### 应用 2 一个 $n*n$ 的棋盘，每个格子可以等概率随机染上 $[1,m]$ 的颜色，每个格子的颜色都不相同，再给定参数 $k$，从 $m$ 中随机选取 $k$ 中颜色，将棋盘中出现在这 $k$ 种颜色之中的格子标记，若有 $r$ 行 $c$ 列格子被全部标记，则得到 $2^{r+c}$，求期望，答案对 $10^{99}$ 取 $\min$。$n\le 300,n^2 \le k \le m\le 100000$. 神仙题，看不懂题解，经过和 [Carotrl 巨佬](https://www.luogu.com.cn/user/223699) 讨论后终于明白了。 1. 考虑 $2^{r+c}$ 的组合意义，不难发现，这个对应的是选出来 $r$ 行 $c$ 列的子集数，反向考虑，也可以对应的是钦定行和列后，对全局包含钦定的行和列的所有子集的贡献。 2. 我们发现，每个格子具体染什么颜色是 **无关紧要的**。由于求的是期望，且颜色之间没有本质区别，所以我们可以钦定每个格子的颜色就是格子的 **标号**。 3. 枚举钦定关键的行数和列数，记为 $i,j,t=(i+j)n-ij$，那么这个的答案即为 $$\large \frac{C_{n}^{i}C_{n}^{j}C_{m-t}^{k-t}}{C_{m}^{k}} $$ 考虑这个式子为什么是对的，由 $1$，我们已经把 $2^{i+j}$ 这种东西均摊掉了，由期望的定义，这整个式子应该就是一个概率。看似概率里面会有什么 $C_{m}^{n^2}$类似这种东西，但是并不是，因为我们前面已经强制钦定每个格子的颜色了，这时候这个 $C_{n}^{i}C_{n}^{j}$ 就已经把关键格子的颜色情况确定过了，$C_{m-t}^{k-t}$ 为剩下格子乱选的方案，最后除以总概率即可，答案为 $$\large \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n}\frac{C_{n}^{i}C_{n}^{j}C_{m-t}^{k-t}}{C_{m}^{k}} $$ 最后 $ex$ 的就是对 $10^{99}$ 取最小值，组合数直接就乘爆了，我们用 $double$ 来存，递推处理，合并一些项就可以了。 ```cpp scanf("%d%d%d",&n,&m,&k); c1[0]=1; for(int i=1;i<=n;i++) c1[i]=c1[i-1]/i*(n-i+1); c2[0]=1; for(int i=1;i<=k;i++) c2[i]=c2[i-1]/(m-i+1)*(k-i+1); double ans=0; for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ int t=(i+j)*n-i*j; if(t<=k) ans+=c1[i]*c1[j]*c2[t]; } } if(ans>1e99) ans=1e99; ``` --- ## 四 组合意义 --- ### 应用 1 $$\large \sum \limits_{p\ is\ a\ permutation}\frac{1}{(A_{p_1})(A_{p_1}+A_{p_2})(A_{p_1}+A_{p_2}+A_{p_3})···} \ \mod \ 998244353$$ 我们考虑题目中要求的式子代表了什么，考虑一个有 $n$ 个有编号的桶子，编号为 $i$ 的桶子有 $A[i]$ 个有编号的球，如果每个桶子中随机抽出一个球，问每个桶子都抽到给定的球的概率，显然它是 $$\large \frac{1}{A_1 \cdot A_2 \cdot A_3···A_n}$$ 那么我们换一个种抽法考虑，如果我们每次抽球是在剩下的所有桶子中抽一个，抽到这个后将这个桶子扔掉，那么正好抽到每个桶子指定的球的概率还是与之前的式子是相等的，因为方案总数相等。那么对于这一种方法怎么计算概率呢？我们先枚举抽到的桶子的顺序，那么对于一个顺序即排列 $p$，正好抽到这 $n$ 个球的概率即为原式。