二项式反演

本文原在 2024-05-23 13:52 发布于本人洛谷博客。

一、简单介绍

1. 钦定与恰好

如在 $5$ 个苹果中选择 $3$ 个，钦定选择 $3$ 个意为选定某 $3$ 个后，剩下 $2$ 个可选可不选；而恰好选择 $3$ 个则意味着选定某 $3$ 个后，其他都不能选。

2. 公式

设 $g(x)$ 表示恰好 $x$ 个条件满足的答案，$f(x)$ 表示钦定 $x$ 个条件满足的答案。

$$f(x)=\sum _{i=x}^n(\genfrac{}{}{0ex}{}{i}{x})g(i)\iff g(x)=\sum _{i=x}^n(-1{)}^{i-x}(\genfrac{}{}{0ex}{}{i}{x})f(i)$$

设 $g(x)$ 表示恰好 $x$ 个条件满足的答案，$f(x)$ 表示钦定 $(n-x)$ 个条件不满足的答案（即至多 $x$ 个条件满足的答案）：

$$f(x)=\sum _{i=0}^x(\genfrac{}{}{0ex}{}{x}{i})g(i)\iff g(x)=\sum _{i=0}^x(-1{)}^{x-i}(\genfrac{}{}{0ex}{}{x}{i})f(i)$$

二、应用

1. 字符串匹配

给定 $n$ 个长度相同的字符串 $s_i$，如果一个字符串 $T$ 每一位都和 $s_i$ 相同（其中 ? 代表和任何字母都相同），那么就称这两个字符串匹配。

求 $T$ 恰好能匹配 $k$ 个字符串的方案数。

$1\le k\le n\le 15$。

设 $f(i)$ 表示钦定匹配某 $i$ 个字符串的方案数， $g(i)$ 表示恰好匹配某 $i$ 个字符串的方案数。

考虑求 $f(i)$。

用二进制枚举枚举不同字符串的组合，然后判断这 $cnt$ 个字符串能否用一个 $T$ 来匹配，如果可以的话，那么就对 $f(cnt)$ 有贡献，如果 $T$ 中每出现一位可以为 ? 的位，那么贡献值就要乘上 $26$（可以选 a~z）的任何数。

然后二项式反演即可，$g(k)=\sum _{i=k}^n(-1{)}^{i-k}(\genfrac{}{}{0ex}{}{i}{k})f(i)$

for (int mask = 0; mask < 1 << n; mask++) {
    int cnt = 0;
    bool b = false;
    string t = "";
    for (int i = 0; i < l; i++) t += '?';
    for (int i = 0; i < n; i++) {
        if ((1 << i) & mask) {
            cnt++;
            for (int j = 0; j < l; j++) {
                if (s[i][j] == '?' or t[j] == s[i][j]) continue;
                else if (t[j] == '?') t[j] = s[i][j];
                else {
                    b = true;
                    break;
                }
            }
        }
        if (b) break;
    }
    if (b) continue;
    int res = 0;
    for (int j = 0; j < l; j++)
        if (t[j] == '?') res++;
    f[cnt] = (f[cnt] + mypow(26, res)) % mod;
}
for (int i = k; i <= n; i++) ans = (ans + mypow(-1, i - k) * C(i, k) % mod * f[i] % mod + mod) % mod;

2. P4859 已经没有什么好害怕的了

给出两个数组 $a_n$，$b_n$，其中 $2n$ 个数互不相同，将 $a$ 和 $b$ 中的数两两配对，设 $a_i>b_i$ 的有 $x$ 个，$a_i<b_i$ 的有 $y$ 个，求 $x-y=k$ 的方案数。

$1\le k\le n\le 2000$。

易得 $y=n-x$，则 $x-n+x=k$，$x=\frac{n+k}{2}$。

同样，设 $f(i)$ 表示 $a>b$ 的组数钦定为某 $i$ 个的方案数， $g(i)$ 表示 $a>b$ 的组数恰好为某 $i$ 个方案数。

考虑求 $f(i)$，可以用 dp 求 $a>b$ 的方案数。

设 $d{p}_{i,j}$ 表示前 $i$ 个数选了 $j$ 组 $a>b$ 的方案数，则：

$$d{p}_{i,j}=d{p}_{i-1,j}+d{p}_{i-1,j-1}\times (r_i-j+1)$$

其中 $r_i$ 表示 $a_i>b$ 的个数。

由于是钦定，剩下的数能随便配对，有 $(n-i)!$ 种组合。

故

$$f(i)=d{p}_{n,i}(n-i)!$$

二项式反演即可。

if ((n + k) % 2) {
	cout << 0;
	return 0;
}
k = (n + k) / 2;
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int p = 1, q = 0; p <= n; p++) {
    while (q < n and b[q + 1] < a[p]) q++;
    r[p] = q;
}
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
    dp[i][0] = 1;
    for (int j = 1; j <= i; j++) 
        dp[i][j] = (dp[i - 1][j] + (r[i] - j + 1) * dp[i - 1][j - 1] % mod) % mod;
}
for (int i = 0; i <= n; i++)
    f[i] = dp[n][i] * fac[n - i] % mod;
for (int i = k; i <= n; i++)
    ans = (ans + (mypow(-1, i - k) + mod) % mod * C(i, k) % mod * f[i] % mod) % mod;

3. P10596 BZOJ2839 集合计数

设 $f(x)$ 表示钦定 $x$ 个元素为交集的答案，随便选 $x$ 个就是 $C_n^x$，剩下 $(n-x)$ 个数构成 $2^{n-x}$ 个集合，这其中中已经包含了一个空集，因此至少要选择一个集合。每个集合选或不选就是 $2^{2^{n-x}}$，再减掉啥也不选。

$$f(x)=C_n^x(2^{2^{n-x}}-1)$$

二项式反演，设 $g(x)$ 表示恰好 $x$ 个元素为交集。

$$g(x)=\sum _{i=x}^n(-1{)}^{i-x}{C}_i^{x}f(x)$$

如何计算 $2^{2^{n-x}}$？注意到当 $x=n$ 时，$2^{2^{n-x}}=2$，而

$$2^{2^{n-(x-1)}}=2^{2^{n-x}\times 2}=(2^{2^{n-x}}{)}^2$$

倒着算即可。

4. P10597 BZOJ4665 小 w 的喜糖

设 $f(x)$ 表示钦定 $x$ 个不变，但直接组合数算重很多，因为颜色有重复的。设 $dp(i,j)$ 表示考虑前 $i$ 种颜色，钦定了 $j$ 个人不变的方案数。

$$dp(i,j)=\sum dp(i-1,j-k)C_{cn{t}_i}^k÷(cn{t}_i-k)!$$

除去的原因是，没被钦定的人不能随便重排。

$f(i)=dp(n_{cnt},i)$，二项式反演。