首页 > 其他分享 >二项式反演和容斥原理学习笔记

二项式反演和容斥原理学习笔记

时间：2025-01-06 13:55:59浏览次数：1  
标签：limits sum 容斥 反演 ans binom 二项式 dp

容斥原理

先从容斥原理开始。

容斥原理的结论如下：

$$
|\bigcup\limits_{i = 1}^{n}S_{i}|
= \sum\limits_{m = 1}{n}(-1)\sum\limits_{a_{i} < a_{i - 1}}|\bigcap_{i = 1}^{m}S_{a_{i}}|
$$

证明的思路是考虑一个元素在每一个 $\bigcap\limits_{i = 1}^{m}S_{a_{i}}$ 里出现的次数，然后通过一番暴算，我们能够发现每个元素都只出现了 $1$ 次，这样，每个元素合起来就变成了总的并集。

详见 OI-wiki

二项式反演

反演的定义

现在我们有两个数组：$g$ 和 $f$。而 $f$ 和 $g$ 之间有对应关系：

$$
f_{n} = \sum\limits_{i = 0}^{n}a_{i} \times g_{i}
$$

然而题目里不可能这么简单，一般是已知 $f$ 让我们推 $g$。这种情况解个方程就可以。但是如果只有解方程的话，还不足以搞出反演这种东西出来，而上面的柿子在某些情况下会化出许多种优美的形式，所以才搞出了反演这种东西。

二项式反演的公式

我们可以从容斥原理推到二项式反演的公式。

有全集 $U = S_{1} \cup S_{2} \cup S_{3} \cup \cdots \cup S_{n}$，且任意 $i$ 个集合的交集和并集大小相同。设 $f_{i}$ 表示任意 $i$ 个集合的并集的大小，$g_{i}$ 表示任意 $i$ 个集合的补集的大小。特别的，$g_{0} = f_{0} = |U|$。根据补集的交集和原集的并集的容斥关系可以得出：

$$
\begin{aligned}
|\bigcap\limits_{i = 1}^{n}S_{i}|
& = |U| - |\bigcup\limits_{i = 1}^{n}\overline{S_{i}}| \
& = |U| - (|\overline{S_{1}}| + |\overline{S_{2}}| + \cdots + (-1)^{n - 1}|\overline{S_{1}} \cap \overline{S_{2}} \cap \cdots \cap \overline{S_{n}}|) \
& = |U| - |\overline{S_{1}}| - |\overline{S_{2}}| - \cdots + (-1)^{n}|\overline{S_{1}} \cap \overline{S_{2}} \cap \cdots \cap \overline{S_{n}}| \
& = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}g_{i}
\end{aligned}
\
\begin{aligned}
|\bigcap\limits_{i = 1}^{n}\overline{S_{i}}|
& = |U| - |\bigcup\limits_{i = 1}^{n}S_{i}| \
& = |U| - (|S_{1}| + |S_{2}| + \cdots + (-1)^{n - 1}|S_{1} \cap S_{2} \cap \cdots \cap S_{n}|) \
& = |U| - |S_{1}| - |S_{2}| - \cdots + (-1)^{n}|S_{1} \cap S_{2} \cap \cdots \cap S_{n}|) \
& = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}f_{i}
\end{aligned}
$$

然而，我们惊奇的发现：$|\bigcap\limits_{i = 1}^{n}S_{i}| = f_{n},|\bigcap\limits_{i = 1}^{n}\overline{S_{i}}| = g_{n}$，于是我们便得到了二项式反演的第一个公式：

$$
f_{n} = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}g_{i}
\Longleftrightarrow
g_{n} = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}f_{i}
$$

如何用数学方法证明这个公式是正确的呢？直接代入就行。
将 $f_{n} = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}g_{i}$ 代入：

$$
\begin{aligned}
g_{n} & = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}\sum\limits_{j = 0}{i}(-1)\binom{i}{j}g_{j} \
& = \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}{i}(-1)\binom{n}{i}\binom{i}{j}g_{j} \
& = \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}{i}(-1)\binom{n}{j}\binom{n - j}{n - i}g_{j} \
& = \sum\limits_{j = 0}^{n}\binom{n}{j}g_{j}\sum\limits_{i = 0}^{n - j}(-1)^{i}\binom{n - j}{i} \
& = \sum\limits_{j = 0}^{n}\binom{n}{j}g_{j}[j = n] \
& = g_{n}
\end{aligned}
$$

显然成立。当然，这个柿子里还有一些不那么显然的东西

  1. $\displaystyle\binom{n}{i}\binom{i}{j} = \binom{n}{j}\binom{n - j}{n - i}$
    这个可以用数学方法证明，也可组合意义的方法证明，这里主要说明组合意义的证法。
    求 $|U| = n,|A| = i,b = |j|,B \subseteq A \subseteq U$ 的方案数。这里有两种方法：
    法一：先在 $U$ 里取 $i$ 个元素构成集合 $A$，方案数为 $\binom{n}{i}$，然后在 $i$ 个元素里再取 $j$ 个元素构成集合 $B$，方案数为 $\binom{i}{j}$，合起来就是 $\binom{n}{i}\binom{i}{j}$
    法二：先在 $U$ 里取 $j$ 个元素构成集合 $B$，方案数为 $\binom{n}{j}$，再在剩下的 $n - j$ 个元素里取 $i - j$ 个元素，方案数为 $\binom{n - j}{i - j}$，又有 $\binom{n - j}{i - j} = \binom{n - j}{n - i}$，所以方案数就是 $\binom{n}{j}\binom{n - j}{n - i}$。
    得证。
  2. $\displaystyle\sum\limits_{i = 0}^{n - j}(-1)^{i}\binom{n - j}{i} = [j = n]$
    设 $k = n - j$，令 $k = 0$，原式的值为 $1$，令 $k > 0$，原式为 $\sum\limits_{i = 0}{k}\binom{k}{i}(-1)$，我们来添一个项：$\sum\limits_{i = 0}{k}\binom{k}{i}(-1) 1^{i}$，发现，这玩意不就是二项式定理的的右边那坨吗？那么原式就是 $(-1 + 1)^{k} = 0^{k} = 0$。得证。

现在再看那个式子就比较好懂了。注意再第二点那里，因为数学老师告诉我们 $0^{0}$ 没有意义，所以在证明的时候为了严谨需要分类讨论。在做题的时候，为了方便可以钦定 $0^{0} = 1$。

小结

二项式反演的 $4$ 种形式：

形式一

$$
f_{n} = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}g_{i}
\Longleftrightarrow
g_{n} = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}f_{i}
$$

形式二（形式一的变形，比较常用）：

$$
f_{n} = \sum\limits_{i = 0}^{n}\binom{n}{i}g_{i}
\Longleftrightarrow
g_{n} = \sum\limits_{i = 0}{n}(-1)\binom{n}{i}f_{i}
$$

形式三：

$$
f_{n} = \sum\limits_{i = n}{m}(-1)\binom{i}{n}g_{i}
\Longleftrightarrow
g_{n} = \sum\limits_{i = n}{m}(-1)\binom{i}{n}f_{i}
$$

形式四（形式三的变形，非常常用）：

$$
f_{n} = \sum\limits_{i = n}^{m}\binom{i}{n}g_{i}
\Longleftrightarrow
g_{n} = \sum\limits_{i = n}{m}(-1)\binom{i}{n}f_{i}
$$

为什么形式四非常常用呢？因为题里多半都是求恰好满足一些条件的方案数。而我们好求的一般都是钦定满足一些条件的方案数。比如：有 $m$ 个条件，$g_{i}$ 表示恰好满足 $i$ 个条件的方案数，$f_{i}$ 表示钦定满足 $i$ 个条件，剩下的随便的方案数。从 $f_{i}$ 的表述里就可以看出，$f_{i}$ 比 $g_{i}$ 好求很多，我们就可以用 $f$ 推得 $g$。

推导思路和证明思路来自 __allenge 的博客。

例题 for 暴力容斥

P1450 [HAOI2008] 硬币购物

我们先考虑没有限制的情况：$dp_{i}$ 表示没有限制的情况下买价格为 $i$ 的物品的方案数，容易发现这就是一个完全背包，可以在 $\mathcal{O}(val)$ 的复杂度下预处理，其中 $val$ 表示最大价格。然后接下来考虑限制的情况。发现正着考虑不超过限制的情况不太好做，正难则反。
我们考虑超过限制的情况。超过限制就是第 $i$ 个硬币强制选 $d_{i} + 1$ 个，剩下的依然随便选，那么情况数就是 $dp_{s - (d_{i} + 1) \times c_{i}}$，答案就要减去 $\sum\limits_{i = 1}^{4}dp_{s - (d_{i} + 1) \times c_{i}}$。这是单个硬币超出限制的情况，如果有多个硬币，就得请出我们的容斥原理了。但是，容斥原理的公式要求任意两个集合的交集和并集大小相等，这很明显不相等啊，我们又发现：只有 $4$ 种硬币，那我们直接枚举不就行了吗？无非就是带一个 $16$ 的常数嘛。

核心代码：

int ans = dp[s];//dp是预处理好的完全背包
for (int k = 1; k < (1 << 4); k++)
{
    int tmp = s;
    for (int i = 0; i < 4; i++)
        if (k & (1 << i))
            tmp -= (d[i] + 1) * c[i];
    if (tmp >= 0)
        ans += (__builtin_popcount(k) & -1 : 1) * dp[tmp];//容斥
}

P6521 [CEOI2010 day2] pin

发现考虑不同的方案数有点难，正难则反。
我们设 $cnt_i$ 为钦定有 $i$ 位相同的方案数。这个可以用哈希求解。我们设哈希函数：

int hsh(char ch){return isdigit(ch) ? ch - '0' : ch - 'a' + 10;}
int hsh(char ch1,char ch2){return hsh(ch1) * 36 + hsh(ch2);}
int hsh(char ch1,char ch2,char ch3)
{return hsh(ch1) * 36 * 36 + hsh(ch2) * 36 + hsh(ch3);}

分别用于求解一个字符，两个字符，三个字符的哈希值。很明显，这个哈希函数生成的哈希值不会超过 $6 \times 10 ^ 4$。那么我们记录 $tmp_{i}$ 表示有多少个字符序列的哈希值是 $i$，然后要求解方案数呢，就相当于求解在 $tmp_{i}$ 个元素里随便取两个不同元素的方案数，很明显是 $\frac{tmp_{i} \times (tmp_{i} - 1)}{2}$。最后，我们求得了钦定有 $i$ 个元素相同的方案数，因为最多有 $4$ 个元素相同，所以我们直接暴力容斥就行。

code:

for (int x = 1; x <= 4; x++)//一个字符相同的
{
    memset(tmp,0,sizeof tmp);
    for (int i = 1; i <= n; i++)
        tmp[hsh(s[i][x])] ++;
    for (int i = 0; i <= 6e4; i++)
        cnt[1] += (tmp[i] * (tmp[i] - 1)) >> 1;
}
for (int x = 1; x <= 4; x++)//两个字符相同
{
    for (int y = x + 1; y <= 4; y++)
    {
        memset(tmp,0,sizeof tmp);
        for (int i = 1; i <= n; i++)
            tmp[hsh(s[i][x],s[i][y])] ++;
        for (int i = 0; i <= 6e4; i++)
            cnt[2] += (tmp[i] * (tmp[i] - 1)) >> 1;
    }
}
for (int x = 1; x <= 4; x++)//三个字符相同
{
    for (int y = x + 1; y <= 4; y++)
    {
        for (int z = y + 1; z <= 4; z++)
        {
            memset(tmp,0,sizeof tmp);
            for (int i = 1; i <= n; i++)
                tmp[hsh(s[i][x],s[i][y],s[i][z])] ++;
            for (int i = 0; i <= 6e4; i++)
                cnt[3] += (tmp[i] * (tmp[i] - 1)) >> 1;
        }
    }
}
//以下是暴力容斥
ans[3] = cnt[3];
ans[2] = cnt[2] - 3 * ans[3];
ans[1] = cnt[1] - ans[2] * 2 - ans[3] * 3;
ans[0] = ((n * (n - 1)) >> 1) - ans[1] - ans[2] - ans[3];
printf("%lld",ans[4 - d]);//由于求解的是相同的，所以不同的就是4 - d个

例题 for 二项式反演

P10986 [蓝桥杯 2023 国 Python A] 2023

设 $f_{m}$ 表示钦定有 $m$ 个 2023 的方案数。用插板法，在这些 2023 的缝里插入那些乱七八糟的数。在 $m$ 个 2023 中插入 $n - 4m$ 个数的方案是

$$
f_{m} = \binom{(n - 4m) + (m + 1) - 1}{(n - 4m) - 1}
$$

设 $g_{m}$ 表示恰好有 $m$ 个 2023 的方案数，那么有：

$$
f_{m} = \sum\limits_{i = m}^{n}\binom{i}{m}g_{i}
$$

根据二项式反演公式，我们得到：

$$
g_{m} = \sum\limits_{i = m}{n}(-1)\binom{i}{m}f_{i}
$$

那么我们就求得了 $g_{m}$，就是答案。时间复杂度 $\mathcal{O}(n)$

BZOJ2839 集合计数

设 $f_{k}$ 表示钦定有 $k$ 个相同元素的情况，那么，剩下的 $n - k$ 个元素能够组成 $2^{n - k}$ 个集合，而，这 $2^{n - k}$ 个集合又能够再组成 $2{2{n - k}}$ 个集合。那么显然有

$$
f_{k} = \binom{n}{k}2{2{n - k}}
$$

设 $g_{k}$ 表示恰好有 $k$ 个相同元素的情况，那么有：

$$
f_{k} = \sum\limits_{i = k}^{n}\binom{i}{k}g_{i}
$$

反演一下得到：

$$
g_{k} = \sum\limits_{i = k}{n}(-1)\binom{i}{k}f_{i}
$$

我们就得到了 $g_{k}$。时间复杂度 $\mathcal{O}(n)$。

P5505 [JSOI2011] 分特产

首先设 $f_{i}$ 表示钦定有 $i$ 个同学没有拿到特产的方案数，那么有：

$$
f_{i} = \binom{n}{i} \times \prod\limits_{j}^{m}\binom{a_{j} + n - i - 1}{n - i - 1}
$$

后面那坨表示将 $a_{j}$ 个物品分成 $n - i$ 个可空集的方案数，而前面的是因为我们并没有钦定哪几个人没有，所以要乘一个在 $n$ 个人里面选 $i$ 个的方案数。

接下来我们开始反演。设 $g_{i}$ 表示正好有 $i$ 个人没有，那么有反演公式：

$$
g_{i} = \sum\limits_{j = i}{n}(-1)\binom{j}{i}f_{j}
$$

而我们要让每一个人都拿到，答案就是 $g_{0}$。这样，我们就做完了。时间复杂度 $\mathcal{O}(n)$

BZOJ4665 小 w 的喜糖

依然是正难则反 + 二项式反演 演都不带演

设 $f_{i}$ 表示钦定有 $i$ 个位置相同，$g_{i}$ 表示正好 $i$ 个位置相同。那么有反演：

$$
f_{i} = \sum\limits_{j = n}^{m}\binom{j}{n}g_{j}
\Longleftrightarrow
g_{i} = \sum\limits_{j = n}{m}(-1)\binom{j}{n}f_{j}
$$

我们的答案就是 $g_{0}$

现在的问题就在于怎么求 $f_{i}$。发现初始数组的顺序对于答案来说没有影响，那么我们就记录每种颜色的数量并去重，然后开始 dp。设 $dp_{i,j}$ 表示循环到第 $i$ 个颜色，钦定有 $j$ 个元素相同的方案数。那么有

$$
dp_{i,j} = \sum\limits_{k = 0}^{\min(cnt_{i},tmp)}dp_{i - 1,j - k} \times \binom{cnt_{i}}{k} \times \binom{tmp - j}{cnt_{i} - k}
$$

初学时属实没想到这玩意还能带 dp

很明显，$f_{i} = dp_{m,i}$，其中 $m$ 表示颜色总数。然后我们就得出了答案，时间复杂度为 $\mathcal{O}(n^2)$。

code:

sort(a + 1,a + n + 1);
int m = unique(a + 1,a + n + 1) - a - 1,tmp = 0;
dp[0][0] = 1;
for (int i = 1; i <= m; i++)
{
    tmp += cnt[a[i]];
    for (int j = 0; j <= tmp; j++)
        for (int k = 0; k <= min(j,cnt[a[i]]); k++)
            dp[i][j] = (dp[i][j] + dp[i - 1][j - k] * c(tmp - j,cnt[a[i]] - k) % mod * c(cnt[a[i]],k) % mod) % mod;
}
int ans = 0;
for (int i = 0; i <= n; i++)
    ans = ((ans + (i & 1 ? -1 : 1) * dp[m][i]) % mod + mod) % mod;

好题推荐

P4448 [AHOI2018 初中组] 球球的排列
P3158 [CQOI2011] 放棋子
P3160 [CQOI2012] 局部极小值

标签：limits,sum,容斥,反演,ans,binom,二项式,dp
From： https://www.cnblogs.com/eous/p/18655146

相关文章

  • [Tricks-00007]AGC070C 什么才是真正的容斥
    呜呜。这题太难受了，还不知道以怎样的方式写能把其中的巧妙思维方式解释清楚。先把做法的表象讲讲吧：考虑翻折容斥。我以为这个做不了，实际是可以的啊！把\(+1,-1,0\)分别记作A,B,X。则要求相当于，固定A,B,X分别的个数（记为\(a,b,x\)），但要求不能出现连续的AA或者BB且前缀和非......
  • 【组合数学】二项式相关与容斥
    二项式定理\[(a+b)^n=\displaystyle\sum^{n}_{i=0}{\binom{n}{i}a^ib^{n-i}}\]证明：数学方法。\[(a+b)^n=a\times(a+b)^{n-1}=a\timesb\times(a+b)^{n-2}=\dots\]假设我们选了\(k\)个\(a\)，我们就需要选\(n-k\)个\(b\)，根据乘法原理，可......
  • [学习笔记] 二项式定理与反演
    一假设\(f(x)\)代表恰好满足\(x\)个性质的方案数。钦定代表至少\(x\)个。假设\(g(x)\)代表至多满足\(x\)个性质的方案数。显然有\[g(n)=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{matrix}\right)f(i)\]并且有\[f(n)=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{ma......
  • P3175 [HAOI2015] 按位或（min-max 容斥）
    题意有一个初始为\(0\)的变量\(x\)，每次操作会以\(p_i\)的概率选择位于\([0,2^n)\)中的某个整数\(i\)，并将\(x\)或上\(i\)。问期望几次操作后\(x=2^n-1\)。\(n\le20,\sump_i=1\)引入：min-max容斥以两个式子入手：\[\max(S)=\sum_{T\subseteqS}(-1)^{|T|+1}\min(T......
  • 莫比乌斯反演学习笔记
    前置知识一、整除分块即按照\(\lfloor\frac{n}{i}\rfloor\)的值域进行分块，块数$\leq\lfloor2\sqrtn\rfloor$。分$i\leq\lfloor\sqrtn\rfloor$，$i>\lfloor\sqrtn\rfloor$讨论。\(i\)所在块的右端点为$\lfloor\frac{n}{\lfloor\frac{n}{i}\rfl......
  • 二项式泰勒展开
    好的，我们来详细解释一下k₂在(xₙ,yₙ)点的泰勒展开过程。背景知识：在多元微积分中，泰勒展开可以将一个多元函数在某一点附近用多项式来近似。对于二元函数f(x,y)，在(x₀,y₀)附近的二阶泰勒展开公式为：f(x,y)≈f(x₀,y₀)+(∂f/∂x)(x₀,y₀)(x-x₀)+(∂f/∂......
  • 容斥原理+组合计数note
    看课笔记：https://www.bilibili.com/video/BV1G3411h7f5/?spm_id_from=333.337.search-card.all.click&vd_source=47c0221101e188411183012cce9b216c讲的真的很好，但是我是不会去看普林斯顿数学指南的（）枚举原理+加法原理+乘法原理枚举基本定理：找到对应的一一映射加法原理：集合加法......
  • 容斥技巧（长期更新）
    普通容斥反射容斥用于格路计数问题，可以在转移与格路计数类似的DP中见到，然后直接用数学方法优化。首先容易得到\((x_0,y_0)\)关于\(y=x+b\)对称得到\((y_0-b,x_0+b)\)。以及\((0,0)\)走到\((n,m)\)的方案数为\(\binom{n+m}n\)。先来考虑一下Catalan数的格路计数的推导方式解......
  • 反演笔记
    反演反演若已知\(f(n)=\sumg(k)\)，用\(f\)表示\(g\)的过程就叫“反演”。二项式反演参考一下邓老师的PPT。经典题：\(n\)个元素错排的方案数。要求线性。考虑枚举有\(k\)个人非错排，可以得到这\(k\)个人一共有\(\dbinom{n}{k}\)种选法，剩下的人有\((n-k)\)......
  • 【算法】欧拉函数、快速幂、容斥原理
    欧拉函数内容：表示1-n中与n互质的个数原理：一个数可以被质因子表示，而除了质因子及其倍数，剩下的个数都是与n互质推导（容斥原理）：​ 1-N总共有N个数，首先将质因子\(p_1,p_2...p_n\)中的倍数减去，因为质因子的倍数与n是不互质的，因此首先减去质因子倍数的个数：\[N=N-\frac{N}{p_1}-\f......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99