「Algorithm」关于容斥/多项式/生成函数

恶补大家小学就会的知识点

其实是一些乱七八糟的基础知识

容斥

$n$ 种限制，算方案数

\begin{aligned} ans &= \sum_{S} (-1)^{|S|}f_S\\ &= \sum_{i=0}^{n}(-1)^{i}\binom{n}{i}f_i \end{aligned}

$f_S$ 表示钦定满足 $S$ 集合限制，其他任意的方案数

$f_i$ 表示钦定满足 $i$ 种限制，其他任意的方案数

假设有一种方案满足 $k>0$ 种限制，那么它会被算这么多次：

\begin{aligned} &\binom{k}{0}-\binom{k}{1} + \binom{k}{2} - \binom{k}{3} -...+(-1)^{k}\binom{k}{k}\\ =&1-\Bigg(\binom{k-1}{0}+\binom{k-1}{1}\Bigg)+ \Bigg(\binom{k-1}{1}+\binom{k-1}{2}\Bigg)-...+\Bigg(\binom{k-1}{k-1}\Bigg)\\ =&1-\binom{k-1}{0}\\ =0 \end{aligned}

而只有当 $k=0$ 时，才会被算 $\binom{0}{0} = 1$ 次

所以这样算就对了

ans = \sum_{i=1}^{n}(-1)^{i+1}\binom{n}{i}f_i

$f_i$ 定义相同，证明方法同上

另外也可以通过维恩图理解

设 $g_k$ 表示答案

g_k = \sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f_i

$f_i$ 定义相同

证明方法只能（~~我只知道~~）通过二项式反演。

\begin{aligned} f_k &= \sum_{i=k}^{n}\binom{i}{k}g_i\\ \Rightarrow g_k&=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f_i \end{aligned}

上面的式子要乘个组合数是因为要枚举出在 $i$ 个限制中是哪 $k$ 个满足（ $f$ 在乱选的时候会算重）

ans = \sum_{i=k}^{n}g_i

其中 $g_i$ 表示恰好满足 $i$ 个限制的方案，于是转化到上一个问题

在得到一个看起来很像卷积的式子后，先把枚举的部分通过变量替换得到 $\displaystyle \sum_{j=0}^{i}$ 的形式

比如，本身式子长这样： $\displaystyle \sum_{j=i}^{n}f[j-i]g[j]$ ，就可以把 $j-i$ 替换成 $k$ ，变成 $\displaystyle \sum_{k=0}^{n-i}f[k]g[k+i]$

然后通过翻转来凑出卷积的形式

接着上面的式子，把 $g$ 数组翻转后得到 $\displaystyle \sum_{k=0}^{n-i}f[k]g[n-k-i]$ ，这样就能直接卷了，卷出来之后再翻转一下就得到要求的数组了

就是把一个数列转化成多项式的形式，转化成更简洁的式子。通过多项式运算，计算系数，来得到答案

用生成函数能快速得到每一项的答案

有时候因为不好直接考虑很多个物品的组合，也可以通过把若干个生成函数直接相乘取 $[x^n]$ ，以方便计算

感觉这东西往往与值域有关

f(x) = \sum_{n=0}^{\infty}\frac{f^{(n)}x_0}{n!}(x-x_0)^n

其中 $\frac{1}{n!}$ 是为了把 $x^n$ 一次一次求导后得到的系数 $n!$ 消去

在取 $[x^n]$ 的时候前面要乘一个 $\frac{1}{n!}$ ，因为指数型生成函数会带一个 $\frac{1}{i!}$