组合计数_杂项

组合计数

收录一些题吧。

理论

定义式及基本性质：

$$\binom{n}{m}=\frac{n!}{m!(n-m)!},\binom{n}{m}=\binom{n}{n-m},\binom n m=\binom {n-1} {m}+\binom{n-1}{m-1}$$

由定义可得，组合恒等式：

$$\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1},m\binom n m=n\binom{n-1}{m-1}$$

范德蒙德卷积：

$$\sum_i\binom{n}{a+i}\binom{m}{b-i}=\binom{n+m}{a+b}$$

上下指标加起来为定值，且下指标枚举了所有位置，则可以使用。

经常与 $\binom{n}{m}=\binom{n}{n-m}$ 结合使用。

意义是从 $n+m$ 个物品任意选 $a+b$ 个物品相当于把原集合拆成 $n$ 集合和 $m$ 集合，并枚举每一种选择方案。

上指标卷积：

$$\sum_i\binom i a\binom {n-i}b=\binom{n+1}{a+b+1}$$

意义是考虑 $n$ 个物品按照所有方式分成左右两部分，左边选 $a$ 个右边选 $b$ 个，等价于插入一个分隔符在 $n+1$ 个物品中选 $a+b+1$ 个。

二项式定理：

$$(a+b)^k=\sum_i\binom{k}{i}a^ib^{k-i}$$

求法

求组合数最通用的方式是 $O(nm)$ 递推：

F(i,0,n) C[i][0]=1;
F(i,1,n) F(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;

但这个玩意太慢了，所以在取模质数且 $n,m\in[0,p)$ 的时候我们可以预处理阶乘及其逆元来求：

fac[0]=fac[1]=inv[0]=inv[1]=1;
F(i,2,n) fac[i]=fac[i-1]*i%p,inv[i]=(p-p/i)*inv[p%i]%p;
F(i,2,n) inv[i]=inv[i]*inv[i-1]%p;
ll C(ll n,ll m) {return n>=m?fac[n]*inv[m]%p*inv[n-m]%p:0;}

但如果 $n,m\ge p$ 就不是那么美妙，我们需要将其转化成 $n,m\in[0,p)$（Lucas 定理）。

ll C(ll n,ll m) {
    if(n<m) return 0;
    if(n<p) return c[n][m];
    return C(n/p,m/p)*c[n%p][m%p]%p;
}

组合数前缀和

需要求 $f_{n,m}=\sum\limits_{i=0}^{m} \binom n i$。

首先还是最通用的递推，这次我们只需要依赖一项：

$$f_{n,m}\gets f_{n,m-1}+\binom n m\\f_{n,m}\gets 2f_{n-1,m}-\binom {n-1} m$$

关于第二个式子的解释，是杨辉三角除了最后一项之外都被加了两遍。

由于你每次可以动一个端点，我们如果要大批量求组合数，可以使用莫队在 $\Theta(n\sqrt q)$ 的时间求出。

但如果你的模数很小，你可以使用 Lucas 科技：

ll F(ll n,ll m) {
    if(k<0) return 0;
    return (C(n/p,m/p)*f[n%p][m%p]+F(n/p,m/p-1)*f[n%p][p-1])%p;
}

解释：

设 $o=\lfloor\frac m p\rfloor=\frac{m-m\bmod p}p$，则：

$$\begin{aligned}F_{n,m}=&\sum_{i=0}^m\binom n i\\=&\sum_{i=0}^{op-1}\binom{n}{i}+\sum_{i=op}^m\binom n i\\=&\sum_{i=0}^{op-1}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{i}{p}\right\rfloor}\binom{n\bmod p}{i\bmod p}+\sum_{i=op}^{m}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{o}\binom{n\bmod p}{i\bmod p}\\=&\sum_{j=0}^{o-1}\sum_{i=0}^{p-1}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{jp+i}{p}\right\rfloor}\binom{n\bmod p}{i}+\binom{\left\lfloor\frac{n}{p}\right\rfloor}{o}\sum_{i=0}^{m\bmod p}\binom{n\bmod p}{i}\\=&\sum_{j=0}^{o-1}\sum_{i=0}^{p-1}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{j}\binom{n\bmod p}{i}+\binom{\left\lfloor\frac{n}{p}\right\rfloor}{o}f_{n\bmod p,m\bmod p}\\=&\sum_{i=0}^{p-1}\binom{n\bmod p}{i}\sum_{j=0}^{o-1}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{j}+\binom{\left\lfloor\frac{n}{p}\right\rfloor}{o}f_{n\bmod p,m\bmod p}\\=&f_{n\bmod p,n\bmod p}F_{\left\lfloor\frac{n}{p}\right\rfloor,o-1}+\binom{\left\lfloor\frac{n}{p}\right\rfloor}{o}f_{n\bmod p,m\bmod p}\end{aligned}$$

其中 $f$ 表示规模足够预处理的部分，$F$ 表示继续递归的部分。

两条线同时推导。

但我们并不满足于离线，很多时候我们需要在线组合数。

发现这个莫队保存的信息是 $\Theta(1)$ 的，所以我们可以直接撒点暴跳。

具体来说，每隔 $\Theta(\sqrt n)$ 行预处理一行，每次处理完了只保留间隔为 $\Theta(\sqrt n)$ 的那些点。

这样每次询问由最近的已知点推过来即可时间 $\Theta(\sqrt n)$，空间 $\Theta(n)$。

如果不计空间的话可以不用扔掉那些点，更简单的写法，更小的常数。

求前缀和例题 Tenka1 2014 Final D：

#include<bits/stdc++.h>
#define id(x) ((x)/B)
#define l(x) ((x)*B)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
using namespace std;typedef long long ll;
const int N=1e5+5,B=420,p=1e9+7;
ll fac[N],inv[N],f[B][N];
ll C(ll n,ll m) {return fac[n]*inv[m]%p*inv[n-m]%p;}
void pre(int n) {
    fac[0]=inv[0]=fac[1]=inv[1]=1;
    F(i,2,n) fac[i]=fac[i-1]*i%p,inv[i]=(p-p/i)*inv[p%i]%p;
    F(i,2,n) inv[i]=inv[i]*inv[i-1]%p;
    F(i,0,id(n)) {
        f[i][0]=1;
        F(j,1,n) f[i][j]=(f[i][j-1]+C(l(i),j))%p;
    }
}
ll S(ll n,ll m) {
    ll res=f[id(n)][m];
    F(i,l(id(n))+1,n) res=(2*res+p-C(i-1,m))%p;
    return res;
}

目前的可应用最低复杂度。

例题

U360425 括号序列

其中 $*$ 表示未知符号，可能是 $"("$ 或者 $")"$ 且概率相等。

我们设字符串 $A$ 是合法的，且它的权值是 $v $当且仅当存在权值为 $w$ 的字符串 $B$ ，满足

$$A=(B),v=w+1$$

$$A=B(),v=w$$

$$A=(),v=1$$

其中任意一种。

求 $A$ 的子序列中最大权值的期望值。

$n\le 10^6$。

首先转化为计数题，最后除以 $2^{num}$。

考虑答案应该在什么地方统计，答案是在左边的左括号数恰好等于右边的右括号数的空隙，显然这样的空隙有且仅有一个，且在此处统计答案一定不劣。

于是列出柿子，设左边有 $a$ 个左括号 $b$ 个未定，右边有 $x$ 个右括号 $y$ 个未定。

$$\begin{aligned}&\sum_dd\binom{b}{d-a}\binom{y}{d-x}=\sum_{i}(a+i)\binom{b}{i}\binom{y}{a+i-x}\\&=a\sum_{i}\binom{b}{i}\binom{y}{a+i-x}+\sum_{i}i\binom{b}{i}\binom{y}{a+i-x}\\&=a\sum_{i}\binom{b}{i}\binom{y}{a+i-x}+\sum_{i}b\binom{b-1}{i-1}\binom{y}{a+i-x}\\&=a\sum_i\binom b i\binom{y}{x+y-a-i}+b\sum_i\binom{b-1}{b-i}\binom{y}{a+i-x}\\&=a\binom{b+y}{x+y-a}+b\binom{b+y-1}{a+b-x}\end{aligned}$$

$\Theta(n)$ 计算即可。

技巧是当你化不掉前面的 $d$ 时不妨往下指标上凑，然后用组合恒等式消掉。

CF785D Anton and School - 2

给定一个长度为 $n$ 的括号序列，求该括号序列满足如下条件的子序列个数：

1. 长度为正偶数
2. 假设该子序列长度为 $2m$，则该子序列前 $m$ 个均为 (，后 $m$ 个均为 )。

对 $10^9+7$ 取模。

$n \le 2 \times 10^5$。

为了避免算重，我们在最后一个计入答案的左括号后面统计。

设左边 $a+1$ 个左括号（最后一个已经钦定），右边 $b$ 个右括号。

$$ans\gets\sum_m\binom{a}{m-1}\binom{b}{m}=\sum_m\binom{a}{m-1}\binom{b}{b-m}=\binom{a+b}{b-1}$$

与上题一样是范德蒙德卷积的应用。

2023.7.25 HIT集训 T2

Alice 和 Bob 正在玩游戏，Alice 初始生命值为 $n$，命中率为 $p\%$，Bob 初始生命值为 $m$，命中率为 $q\%$。

从 Alice 开始轮流攻击对方，如果命中则对方失去一点生命值，一旦有人生命值降为 $0$，游戏立即结束，生命值为 $0$ 的人失败，而另一人胜利。

求最终 Alice 获胜的概率，对 $998244353$ 取模。

$n,m\le 10^6$。

为什么我看到这个题会觉得这题就一个柿子就能解决呢。

一口吃不成胖子。

首先 $p\gets \frac p {100},q\gets \frac q {100}$。

直观地，设 $f_{i,j}$ 为 A 剩 $i$ 滴血，B 剩 $j$ 滴血，且当前 A 将要出牌的概率。

下面我们来看一个典型错误案例：

$$f_{i,j}=p(1-q)f_{i,j+1}+(1-p)qf_{i+1,j}+pqf_{i+1,j+1}+(1-p)(1-q)f_{i,j}$$

这个状态被我想到的一瞬间我就想到自己能转移到自己了，然后就觉得不可做。

注意我这里 $DP$ 转移没有写 $\gets$，而写了 $=$。

写出来才知道，这不是能移项吗！

$$f_{i,j}\gets \frac{p(1-q)f_{i,j+1}+(1-p)qf_{i+1,j}+pqf_{i+1,j+1}}{p+q-pq}$$

初始 $f_{n,m}=1,f_{无意义}=0$。

喜提 $O(nm)$ 做法。

看起来十分有道理，然后我就对着这个柿子写了一上午正解也没调出来。

哪里错了呢？

初始 $f_{n,m}=1,f_{无意义}=0$。

确实，游戏的最开始 $f_{n,m}=1$，但经过了若干轮游戏后游戏停止，$f_{n,m}$ 就不再为 $1$ 了。

为什么我们的柿子需要在游戏停止的时候才能转移呢？

不要忘了，自己能转移到自己，而我们移项后，就相当于碾碎了时间轴，一步直达最后时刻（尽管有可能到达无限轮）的概率。

所以我们的初始值不是 $f_{n,m}=1$，记住游戏规则：“一旦有人生命值降为 $0$，游戏立即结束。”

所以初始值 $\forall i,f_{0,i}=f_{i,0}=1$。

那问题又来了，我们上面那个无比正确的柿子是从后往前推的，你这没法转移啊！

这个时候就要换转移方程了。

注意我们两个状态间的关系是对等的，一个状态如果能往另一个状态贡献 $p$ 的概率，那反过来，另一个状态发生，那这个状态也会多 $p$ 的概率。

所以转移方程这么写：$$f_{i,j}\gets \frac{p(1-q)f_{i,j-1}+(1-p)qf_{i-1,j}+pqf_{i-1,j-1}}{p+q-pq}$$

（对上面的用不了转移方程进行数学推导也可以得出相同的结果。）

终于可以喜提 $O(nm)$ 做法了。

这个错误是在那个错误做法推了一上午还过不了样例之后发现的，惨痛的教训。

那怎么优化呢。

把 $i,j$ 抽象成坐标，那么柿子的意义相当于终点 $(n,m)$，每次往上走一步、往右走一步、往右上走一步选一个。

若 A 胜利，则起点为任意 $0\leq k\leq n$，$(k,0)$。

设走了上 $A$ 步，走了右 $B$ 步，走了右上 $C$ 步。

可得：$$\begin{cases}A+C=m\B+k+C=n\end{cases}$$

我们枚举 $C$，那么 $A=m-C$，$B\in [0,n-C]$。

设 $\frac{p(1-q)}{p+q-pq}=g_A,\frac{(1-p)q}{p+q-pq}=g_B,\frac{pq}{p+q-pq}=g_C$。

则：$$ans\gets num_{A,B,C}g_A^{A}g_B^{B}g_C^{C}$$

其中 $num_{A,B,C}$ 是 $A,B,C$ 这组数对应的走网格的方案数。

也就是 $\frac{(A+B+C)!}{A!B!C!}$（$\frac{全排列数}{各部分排列数乘积}$）。

枚举 $C$ 时 $B$ 的合法取值是一段前缀，预处理即可。

发现前面的系数不太好预处理。

设 $$\begin{aligned}s_C&=\sum_{B=0}^{n-C}\frac{(B+m)!}{(m-C)!B!C!}g_B^{B}\&=\sum_{B=0}^{n-C}\frac{(B+m)!}{m!B!}\frac{m!}{(m-C)!C!}g_B^{B}\&=\sum_{B=0}^{n-C}\binom{B+m}{B}\binom{m}{C}g_B^{B}\&=\binom{m}{C}\sum_{B=0}^{n-C}\binom{B+m}{B}g_B^{B}\end{aligned}$$

所以只需处理 $\sum_{B=0}^{n-C}\binom{B+m}{B}g_B^{B}$ 即可，剩余的 $\binom{m}{C}$ 在转移的时候乘上即可。

复杂度 $O(n+m)$。

别急着去码。

如果你真的把 $num_{A,B,C}$ 当作 $\frac{(A+B+C)!}{A!B!C!}$ 来算的话你就会发现怎么也过不去样例。

原因是什么呢。

原因是有一个蛋疼的问题：如果看作从 $(n,m)$ 走到 $(0,k)$，你最后一步不能往左走。

而我们对 $A,C$ 的各种分讨非常麻烦……

伟大的 lym 佬教了我一个策略：起点为任意 $1\leq k\leq n$，$(k,1)$。

最后再往左下走一步或者往下走一步。

（也就相当于在原来的思路上 $n\gets n-1,m\gets m-1,ans\gets ans\times ga\times gc$）

我在这个破地方卡了 $8$ 个小时，美好的一天从遇到这题结束。

ps：中间推柿子的时候把 $A$ 和 $B$ 搞反了，调了很久，感觉推柿子更像数学题，马虎错很少能场上检查出来，改错机会很少，要争取一遍对。

ps：共出现了三处难以调出来的重大错误：$A$ 和 $B$ 定义搞反、原始柿子错误、$n\gets n-1,m\gets m-1,ans\gets ans\times ga\times gc$。

每一个都是血与泪。