题解 P7468 【[NOI Online 2021 提高组] 愤怒的小N】

· · 题解

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

性质 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} **定理 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)$ 的时间复杂度内解决了本题。