自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 22:30:08，当前版本为作者最后更新于2021-03-27 16:17:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先分析题目中关于奖励关卡的叙述，容易发现：

性质 0 第 $i$ 关是奖励关卡当且仅当 $i$ 的二进制表示包含奇数个 $1$。

可以通过对 $i$ 在二进制下的位数进行归纳证明，此处略去。也就是说，我们要计算的值为

$$\sum_{0\leq i < n,i\in C_1}f(i)$$

其中 $C_1$ 是全体二进制表示中有奇数个 $1$ 的自然数的集合。由于有限制 $i < n$，为了去掉这个限制，考虑枚举 $i$ 和 $n$ 在二进制位上首次不一样的地方——这样，更低位的选择便是自由的。不妨设 $n$ 在二进制下有 $s$ 位，且 $n=(n_sn_{s-1}\cdots n_1)_2$（其中 $n_s$ 是最高位）。令 $T_i$ 表示将 $n$ 的后 $i$ 位变成 $0$ 所得的数（即 $T_i=(n_s\cdots n_{i+1}00\cdots 0)_2$。那么答案便是

$$\sum_{1\leq i\leq s,n_i=1}\sum_{0\leq j<2^{i-1},T_i+j\in C_1}f(T_i+j) $$

显见这里的 $T_i$ 对每个 $i$ 是固定且容易计算的，且 $T_i+j$ 有奇数个 $1$ 当且仅当 $T_i$ 和 $j$ 在在二进制中有相同奇偶性个数的 $1$。问题的关键在于对多项式的求和。按二项式定理展开：

$$f(T+j)=\sum_{p=0}^{k-1}a_p\binom{k-1}{p}T^pj^{k-1-p} $$

$T=T_i$ 是确定的，我们要做的是快速的求出符合条件的 $j$ 的 $0\sim (k-1)$ 次幂和。观察到这里是对所有 $i-1$ 位二进制数中的恰好一半求次幂和，联想到一个广为人知的结论：

定理 1 设 $k$ 是正整数，那么

$$\sum_{0\leq i < 2^k,i\in C_1}i^p=\sum_{0\leq i < 2^k,i\in C_0}i^p $$

对所有的非负整数 $0\leq p < k$ 成立，其中 $C_0,C_1$ 分别是二进制下 $1$ 个数为偶数、奇数的自然数集合。

（知道这个定理的读者可以跳过证明）

为了证明这个定理，我们先证明如下结论：

引理 2 设 $x_1,...,x_k;y_1,...,y_k$ 是实数，$p$ 是自然数，若对任意自然数 $f\leq p$ 都有

$$\sum_{i=1}^kx_i^f=\sum_{i=1}^ky_i^f$$

那么对任意的实数 $z$，有

$$\sum_{i=1}^k(z+x_i)^f=\sum_{i=1}^k(z+y_i)^f$$

证明 左右对减，观察到 $z^i$ 项的系数为 $\binom{p}{p-i}(\sum_{j=1}^kx_j^{p-i}-y_j^{p-i})$，由已知条件显然该式为 $0$。故左式等于右式。

定理 1 的证明 考虑归纳法。$k=1$ 时显然。$k>1$ 时，对于任意 $p < k-1$，由归纳假设知

$$\sum_{0\leq i < 2^{k-1},i\in C_1}i^p=\sum_{0\leq i < 2^{k-1},i\in C_0}i^p $$

那么由引理可得

$$\sum_{0\leq i < 2^{k-1},i\in C_1}(2^k+i)^p=\sum_{0\leq i < 2^{k-1},i\in C_0}(2^k+i)^p $$

对任意 $x\in [2^{k-1},2^k)$，$x$ 的二进制中 $1$ 的个数奇偶性恰和 $x-2^{k-1}$ 的奇偶性相反。因而我们得知

$$\sum_{0\leq i < 2^k,i\in C_1}i^p=\sum_{0\leq i < 2^{k-1},i\in C_1}i^p+\sum_{0\leq i < 2^{k-1},i\in C_0}(2^k+i)^p $$

对另一侧也有相同的结论。再由上面的式子就得知：对于 $p < k-1$，上式是成立的。我们关键来讨论 $p=k-1$ 的情况。这里我们特别留心 $i^{k-1}$ 次项的系数（因为除了这一项外前面的次幂和都是相等的）。展开得

$$\sum_{0\leq i < 2^k,i\in C_1}i^{k-1}=\sum_{0\leq i < 2^{k-1},i\in C_1}i^{k-1}+\sum_{0\leq i < 2^{k-1},i\in C_0}(2^k+i)^{k-1} $$$$=\sum_{0\leq i < 2^{k-1},i\in C_1}i^{k-1}+\sum_{0\leq i < 2^{k-1},i\in C_0}(i^{k-1}+\sum_{j=0}^{k-2}\binom{k-1}{j}i^j2^{k(k-1-j)} $$$$=\sum_{i=0}^{2^{k-1}}i^{k-1}+\sum_{0\leq i < 2^{k-1},i\in C_0}\sum_{j=0}^{k-2}\binom{k-1}{j}i^j2^{k(k-1-j)} $$

后面那一堆东西是什么并不重要——由于 $i$ 的次幂不超过 $k-2$ 次，因此归纳假设已经保证了左右是相等的。而前面的 $k-1$ 次项神奇地合并了！定理证毕。

---

回到原题。由上面的定理进一步可以知道：当 $k > p$ 时，

$$\sum_{0\leq i < 2^{k},i\in C_1}i^p=\sum_{0\leq i < 2^{k},i\in C_0}i^p=\dfrac{1}{2}\sum_{i=0}^{2^k-1}i^p $$$$\sum_{0\leq i < 2^{k},i\in C_1}(T+i)^p=\sum_{0\leq i < 2^{k},i\in C_0}(T+i)^p=\dfrac{1}{2}\sum_{i=0}^{2^k-1}(T+i)^p $$

那么当 $k-1 < i-1$ 时，要求的

$$\sum_{0\leq j<2^{i-1},T_i+j\in C_1}f(T_i+j)=\dfrac{1}{2}\sum_{0\leq j<2^{i-1}}f(T_i+j) $$

令 $S(x)=\sum_{i=0}^{x}f(i)$。显见这是关于 $x$ 的不超过 $k$ 次的多项式且当 $k$ 小于模数时在模意义下有等价性。我们可以用拉格朗日插值的方法，在求出 $S(0),...,S(k)$ 后推出各项系数。这样在预处理系数后便可以 $O(k)$ 代入上式进行计算了！算上枚举 $i$ 的复杂度，这一部分的总时间复杂度为 $O(sk)$。

我们还剩下 $k\geq i$ 的情况没有处理。由于这样的 $i$ 只有 $k$ 个，我们考虑暴力处理出 $G_z(i,p)=\sum_{0\leq j < 2^i,j\in C_z}j^p$。运用二项式定理可以在 $O(k^3)$ 的时间复杂度内完成转移。之后暴力代入计算即可。这一部分总时间复杂度为 $O(k^3)$。综上，我们在 $O(sk+k^3)$ 的时间复杂度内解决了本题。