ALFR R2-D 线性做法

· · 题解

在任意位置上时，都有 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)。