分类： 未分类

Educational Codeforces Round 133 F – Bags with Balls

题目中存在高次项的和。则我们分别计算有 $p=1,2,\cdots,n$ 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子，每个有 $\lceil \frac{m}{2} \rceil$ 种选择；偶数的则有 $\lfloor \frac{m}{2} \rfloor$ 种。因此答案为：
$$
\sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}
$$

由于 $n\leq 10^9$，这式子看起来非常棘手。但我们注意到，有 $k\leq 2000$，这提示我们或许应该转变对答案的贡献方式：从高次幂入手，找到 $\mathrm{O}(\operatorname{poly} k)$ 而非 $\mathrm{O}(n)$ 的算法。 （更多…）

二项式反演

有函数 $f,g$，则 $\forall n \in \mathbb{N},$
$$\begin{aligned}
f(n)=\sum\limits_{x=0}^{n}\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^{n-x}\dbinom{n}{x}f(x) && (1)\\
f(n)=\sum_{x=0}^{n}(-1)^x\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^x\dbinom{n}{x}f(x) && (2)\\
f(n)=\sum_{x=n}^{+\infty}\dbinom{x}{n}g(x) &\iff g(n)=\sum_{x=n}^{+\infty}(-1)^{x-n}\dbinom{x}{n}f(x) && (3)
\end{aligned}$$

（6月22日追记：式 $(1),(3)$ 在OI中是最常用的。尤其是 $(3)$，阐述了在计数类问题中钦定 $x$ 个元素满足某种属性（$f(x)$），其他元素任意，与恰好有 $x$ 个元素满足某种属性（$g(x)$）之间的对应关系。）

证明

（更多…）