自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:59:26，当前版本为作者最后更新于2024-06-15 13:04:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

在任意位置上时，都有 $n$ 条棱可以选择走，对应了改变 $n$ 维坐标中任意一个的状态。

所以稍微转化一下问题：有 $n$ 个硬币，初始全是反面。每次选一个硬币翻面，$m$ 次后要让恰好前 $l$ 个正面朝上，问方案数。

那么前 $l$ 个硬币要翻奇数次，剩下的翻偶数次，答案也就是：

$$m![x^m]\left(\frac{\text e^x -\text e^{-x}}{2} \right)^{l}\left(\frac{\text e^x +\text e^{-x}}{2} \right)^{n-l} $$

我们可以设

$$G(x)=(x+1)^{n-l}(x-1)^l$$

显然 $G(x)$ 是微分有限的，具有整式递推式。具体而言：

$$(x^2-1)G'(x)=((2l-n)+nx)G(x)$$ $$(i-1)g_{i-1}-(i+1)g_{i+1}=(2l-n)g_i+ng_{i-1}$$

那么答案就是

$$2^{-n}m! [x^m] \text e^{-nx} G(\text e^{2x})=2^{-n}\sum_{i=0}^n g_i(2i-n)^m $$

线性筛出自然数幂即可计算，时间复杂度 $\Theta(n + n \log_n m)$。