基本的计数技巧

基本的定理 / 恒等式¶

二项式定理¶

\[ (x+y)^n=\sum_{i=0}^{n}\binom{n}{i}x^iy^{n-i} \]

对于指数不为非负整数的情况，有牛顿二项式定理：

\[ (x+y)^{\alpha}=\sum_{k=0}^{\infty}\frac{\alpha^{\underline{k}}}{k!}x^ky^{\alpha-k} \]

插值¶

定理：\(n\) 个点值可以唯一确定一个 \(n-1\) 次的多项式。

拉格朗日插值¶

给出一个 \(n-1\) 次多项式 \(F(x)\) 在 \(n\) 个点的点值 \((a_i,b_i\))，试还原 \(F(x)\)。

拉格朗日插值给了我们一种可以还原这个多项式的构造。

考虑一个多项式 \(G_i\)，它满足 \(G_i(a_i)=b_i\)，并且对于所有 \(j\neq i,G_i(a_j)=0\)。

那么就有 \(F(x)=\sum_{i=1}^{n} G_i\)。

我们来试着构造这个 \(G_i\)，首先所有 \(j\neq i\) 的 \(a_j\) 都是它的零点，那么就应该是：

\[ \prod_{j\neq i}(x-a_j) \]

然后它在 \(a_i\) 处的点值还应为 \(b_i\)，那么我们先除掉 \(\prod_{j\neq i}(a_i-a_j)\)，再乘上 \(b_i\)，也就是说：

\[ F(x)=\sum_{i=1}^{n}\frac{b_i\prod_{j\neq i}(x-a_j)}{\prod_{j\neq i}(a_i-a_j)} \]

到这里，我们已经可以在 \(\mathcal O(n^2)\) 的时间内求出某一点的值了。考虑进一步求出这个多项式的系数。

我们先求出多项式 \(G(x)=\prod_{i}(x-a_i)\)，显然这可以在 \(\mathcal O(n^2)\) 的时间内完成。

然后利用类似于回撤背包的 Trick，对于每个 \(j\)，我们钦定 \((x-a_j)\) 是最后一个乘的（有交换律），令 \(P_i(x)=\prod_{j\neq i}(x-a_j)\)，那么有

\[ \begin{aligned} G(x)&=(x-a_i)P_i(x)\\ G(x)&=xP_i(x)-a_iP_i(x)\\ [x^k]G(x)&=[x^{k-1}]P_i(x)-a_i[x^k]P_i(x) \end{aligned} \]

其中显然 \([x^0]G(x)=-a_i[x^0]P_i(x)\)。对于每个 \(k\)，假使我们已经算出了 \(<k\) 项的 \(P_i(x)\) 的系数，那么

\[ [x^k]P_i(x)=\frac{[x^k]G(x)-[x^{k-1}]P_i(x)}{-a_i} \]

\(\mathcal O(n)\) 递推即可算出整个多项式的系数。

连续点值插值¶

假如 \((a_i,b_i)\) 中的 \(a_i\) 是一个 \(1\sim n\) 的排列，并且我们只需要询问某一个点 \(k\) 处 \(F(k)\) 的值，我们可以做到 \(\mathcal O(n)\) 的复杂度。

首先是

\[ \prod_{j\neq i}(a_i-a_j) \]

对于 \(a_j<a_i\) 的部分，贡献显然是 \((a_i-1)!\)，对于 \(a_j>a_i\) 的部分，则是

\[ \prod_{k=1}^{n-a_i}(-k)=(-1)^{n-a_i}(n-a_i)! \]

显然在预处理阶乘后可以 \(\mathcal O(1)\) 计算。

而对于

\[ \prod_{j\neq i}(k-a_j) \]

我们维护一个序列 \(p_i=(k-a_i)\)，那么显然这就是

\[ \prod_{j<i}p_j\prod_{j>i}p_j \]

维护前，后缀积即可。

不难发现这个方法可以被推广到 \(a_i\) 是一个 \(l\sim r\) 的排列的情况。

例：CF622F. The Sum of the k-th Powers

经典结论是 \(1\sim n\) 的 \(k\) 次幂之和是一个 \(k+1\) 次多项式，那么我们插 \(k+2\) 个值就可以了。

而 \(\operatorname{id}^k\) 是一个完全积性函数，可以直接线性筛。

代码：Submission #296314171 - Codeforces

反演¶

二项式反演¶

形式 1：

设 \(f(i)\) 表示所有钦定 \(i\) 个元素方案中，这 \(i\) 个元素必选，其他元素任意选择的方案数之和，\(g(i)\) 表示恰好选出 \(i\) 个元素的方案数，那么有

\[ f(n)=\sum_{i=n}^{m}\binom{i}{n}g(i)\Longleftrightarrow g(n)=\sum_{i=n}^{m}(-1)^{i-n}\binom{i}{n}f(i) \]

其中 \(m\) 是全集大小

形式 2：

设 \(f(i)\) 表示所有钦定 \(i\) 个元素的方案中，在这 \(i\) 个元素中任意选出一个子集的方案数之和，\(g(i)\) 表示恰好选出 \(i\) 个元素的方案数，那么有

\[ f(n)=\sum_{i=0}^{n}\binom{n}{i}g(i)\Longleftrightarrow g(n)=\sum_{i=0}^{n}(-1)^{n-i}f(i) \]

证明见二项式反演及其应用 - GXZlegend。

Burnside 引理与 Pólya 定理¶

群作用 / 等价类¶

我们假设有一个群 \((G,*)\) 和一个集合 \(X\)，同时又有一个映射 \(G\times X\rightarrow X\)（将 \(G\) 与 \(X\) 的笛卡尔积映射到 \(X\)）。记 \((g,x)\) 在此映射下的像为 \(g\cdot x\)，那么若映射满足

\((g*h)\cdot x=g\cdot (h\cdot x)\) 对所有 \(g,h\in G,x\in X\) 成立。
\(e\cdot x=x\)，其中 \(e\) 是 \(G\) 的单位元。

那么此映射则被称为一个 \(G\) 在 \(X\) 上的（左）群作用。

我们称 \(x,y\) 满足一种关系 \(x\sim y\)，当且仅当 \(\exists g\in G,g\cdot x=y\)。

显然由群的性质可以导出 \(x\sim y\) 的对称，自反，传递性。所以 \(x\sim y\) 是一种等价关系。

我们要求的问题就是在这样的等价关系下，等价类集合 \(X/G\) 的大小。