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

orz

场上推了一半不会了qwq，还是太菜啦/dk

由于云浅太菜了，所以写的可能会通俗一点qwq（

Description

有一个可爱的数列 $\{A_n\}$，满足：

$A_0=0$
$A_{n}=1-A_{n-2^{m}}$，其中 $m$ 是使得 $2^{m}\le n$ 的最大的正整数。

再给你一个可爱的 $k-1$ 次多项式 $f(x)=\sum_{i=0}^{k-1}a_ix^{i}$。

给定 $n$，求 $\sum_{i=0}^{n-1}A_i\cdot f(i)$。

Solution

第一步肯定要处理 $\{A_n\}$ ，毕竟这个数列太神奇了，不搞一下都没法做>_<

首先看一下数列 $\{A_n\}$ 到底是什么东西。

仔细观察这个递推式：$A_{n}=1-A_{n-2^{m}}$。

我们发现，如果把 $n$ 的二进制表达写出来，那么减去这个 $2^m$ ，就相当于把 $n$ 最高位上的那个 $1$ 去掉！

毕竟，$2^{m}$ 在二进制下总是一个 $1$ 后面跟一长串 $0$，而且这还是使得 $2^{m}\le n$ 的最大的正整数嘛，那就只能是最高位和 $n$ 一样都是 $1$，然后后面全是 $0$ qwq。

于是 $A_{n-2^{m}}$ 到 $A_n$ 就相当于在前头加了个 $1$，那就相当于把 $A_n$ 的二进制表达中奇偶性翻转。

再结合 $A_0=0$，就有：

$A_n=\text{Popcount}(n)\bmod2$

其中 $\text{Popcount}(n)$ 表示 $n$ 的二进制表达中的 $1$ 个数。方便起见，下面统一简记为 $\text{P}(n)$。

但是这个 $\bmod 2$ 让我们很难受啊>_<

用一个常见的技巧，把 $\bmod 2$ 搞掉：

$A_n=\text{P}(n)\bmod2=\dfrac{1-(-1)^{\text{P}(n)}}{2}$

于是那我们就成功搞掉了 $A_n$，把它变得更可爱啦（๑ `▽´๑)

回到要求出来的这个式子。

把我们之前推出来的 $A_n$ 带进去化简一通：

$\begin{aligned} \sum_{i=0}^{n-1}A_i\cdot f(i)&=\sum_{i=0}^{n-1}\left(\dfrac{1-(-1)^{\text{P}(i)}}{2}\cdot f(i)\right)\\ &=\dfrac{1}{2}\left(\sum_{i=0}^{n-1}\left(f(i)-(-1)^{\text{P}(i)}\cdot f(i)\right)\right)\\ &=\dfrac{1}{2}\left(\sum_{i=0}^{n-1}f(i)-\sum_{i=0}^{n-1}(-1)^{\text{P}(i)}\cdot f(i)\right) \end{aligned}$

诶，前面就是一个 $f(x)$ 的前缀和嘛！

那就可以直接拉格朗日插值，$O(k^2)$ 求出前缀和的表达式，然后带进去算出这部分qwq。

现在主要看后面这部分：

$\sum_{i=0}^{n-1}(-1)^{\text{P}(i)}\cdot f(i)$

貌似这种形式没法继续推。把 $f(i)$ 展开试试：

$\sum_{i=0}^{n-1}(-1)^{\text{P}(i)} \sum_{r=0}^{k-1}a_{r}i^{r}$

交换一下求和顺序（其实就是提取公因式）：

$\sum_{r=0}^{k-1}a_r\sum_{i=0}^{n-1}(-1)^{\text{P}(i)}i^{r}$

诶，前面的这个系数 $a_r$ 是很好算的嘛qwq！

那我们现在要求的就是：

$\sum_{i=0}^{n-1}(-1)^{\text{P}(i)}i^{r}$

然后，我当时就推到这里，推不下去啦>_<

现在我们写出 $n$ 的二进制表示，是一长串 $1$ 和 $0$。

然后我们从后往前，一个一个地把 $n$ 二进制表示中的 $1$ 去掉，去掉之后的数和去掉之前的数构成了一个区间。

这样就把 $[0,n)$ 划分成了很多个区间，并且每个区间的长度都是 $2$ 的正整数次幂。

比如随便写一个 $n=114=(1110010)_2$，那么就把 $[0,n)$ 划分成了：

• $[(1110000)_2,(1110010)_2)$，即 $[112,114)$
• $[(1100000)_2,(1110000)_2)$，即 $[96,112)$
• $[(1000000)_2,(1100000)_2)$，即 $[64,96)$
• $[0,(1000000)_2)$，即 $[0,64)$

当然你也可以拿 $514=(1000000010)_2$ 验证一下qwq。

（其实就是 $114=2^6+2^5+2^4+2$，$514=2^9+2$ 嘛qwq）

那么我们考虑一段长度为 $2^t$ 的区间 $[u,u+2^t)$ 中的和：

$\sum_{i=u}^{u+2^t-1}(-1)^{\text{P}(i)}i^{r}$

把求和换成从 $0$ 开始：

$\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i+u)}(i+u)^{r}$

显而易见的一点是，要么 $u=0$，要么 $u$ 的最低位上的 $1$ 要比 $2^t$ 的最高位上的 $1$ 靠前，即 $\text{lowbit}(u)>\text{highbit}(2^t)$。

毕竟，我们每一次区间的转换其实就相当于在 $u$ 的后面的一堆 $0$ 上选一位变成 $1$ 嘛qwq。

比如前面的例子 $n=114=(1110010)_2$，这里的 $u$ 和 $t$ 就依次是：

$\begin{aligned}u&&0000000 &&1000000&&1100000&&1110000&&1110010\\2^t&&1000000&&100000&&10000&&10&&/\end{aligned}$

既然 $u$ 的最低位上的 $1$ 都比 $2^t$ 的最高位上的 $1$ 靠前，那它肯定比 $i$ 的最高位上的 $1$ 靠前。也就是说，$u+i$ 的二进制表示中，不会发生进位！

那么 $u+i$ 的二进制表示中的 $1$ 的个数就是 $u$ 和 $i$ 各自的二进制表示中 $1$ 的个数之和，即：$\text{P}(u+i)=\text{P}(u)+\text{P}(i)$。

那么就可以提出来一个 $(-1)^{\text{P}(u)}$，把式子变成：

$(-1)^{\text{P}(u)}\cdot\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i)}(i+u)^{r}$

再用二项式定理展开 $(i+u)^r$，得到：

$(-1)^{\text{P}(u)}\cdot\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i)}\sum_{j=0}^{r}C_{r}^ju^{r-j}i^{j}$

再交换求和顺序：

$(-1)^{\text{P}(u)}\cdot\sum_{j=0}^{r}C_r^ju^{r-j}\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i)}i^j$

仔细观察这个式子的后半部分qwq！

$\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i)}i^j$

嘛......这个东西，好像在前面见过？

如果我们记

$\text{Sum}(u,t,r)=\sum_{i=u}^{u+2^t-1}(-1)^{\text{P}(i)}i^{r}=\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i+u)}(i+u)^{r}$

诶，刚才那个式子的后半部分

$\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i)}i^j$

不就是 $\text{Sum}(0,t,j)$ 嘛qwq！

也就是说，如果我们知道了对于所有 $0\le j\le r$ 的 $\text{Sum}(0,t,j)$ 的值，那么就可以在 $O(r)$ 的时间内算出 $\text{Sum}(u,t,r)$。

至于 $\text{Sum}(0,t,j)$ 的值，那直接变形一下：

$\begin{aligned} \text{Sum}(0,t,j)&=\sum_{i=0}^{2^t-1}(-1)^{\text{P}(i)}i^j\\ &=\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}i^j+\sum_{i=2^{t-1}}^{2^t-1}(-1)^{\text{P}(i)}i^j\\ &=\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}i^j+\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i+2^{t-1})}(i+2^{t-1})^j\\ &=\text{Sum}(0,t-1,j)+\text{Sum}(2^{t-1},t-1,j)\\ \end{aligned}$

那么我们发现，类似于动态规划，可以用 $\text{Sum}(0,t-1,j)$ 和 $\text{Sum}(2^{t-1},t-1,j)$ 来推出 $\text{Sum}(0,t,j)$。

直接硬算的话，由于总共有 $O(k+\log_2n)$ 个不同的 $x$，而两重的递推又是 $O(k^2)$ 的，所以总复杂度为 $O(k^3+k^2\log_2n)$，可以获得 $60pts$。

回到刚才的那个式子，另一方面，它也可以变成：

$\begin{aligned} &\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}i^j+\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i+2^{t-1})}(i+2^{t-1})^j\\ =&\text{Sum}(0,t-1,j)+(-1)^{\text{P}(2^{t-1})}\cdot \sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}(i+2^{t-1})^j\\ =&\text{Sum}(0,t-1,j)-\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}(i+2^{t-1})^j\\ \end{aligned}$

推到这里之后发现有一个和之前形式几乎一模一样的：

$\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}(i+2^{t-1})^j$

类似之前的操作，用二项式定理展开并交换求和顺序，就得到：

$\begin{aligned} \sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}(i+2^{t-1})^j&=\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}\sum_{s=0}^{j}C_{j}^s\left(2^{t-1}\right)^{j-s}i^{s}\\ &=\sum_{s=0}^{j}C_j^s\left(2^{t-1}\right)^{j-s}\sum_{i=0}^{2^{t-1}-1}(-1)^{\text{P}(i)}i^s\\ &=\sum_{s=0}^jC_j^s\left(2^{t-1}\right)^{j-s}\text{Sum}(0,t-1,s) \end{aligned}$

于是就得到另一个递推式：

$\text{Sum}(0,t,j)=\text{Sum}(0,t-1,j)-\sum_{s=0}^jC_j^s\left(2^{t-1}\right)^{j-s}\text{Sum}(0,t-1,s)$

利用这个递推式，可以发现一个结论：若 $2^{t}>2^j$ 即 $t>j$ 时，总有：

$\text{Sum}(0,t,j)=0$

$t=0$ 时显然成立。

若 $t=x$ 时，对于 $j<t$，均有 $\text{Sum}(0,x,j)=0$。

则当 $t=x+1$ 时，对于任意的 $j<x+1$ 即 $j\le x$：

若 $j<x$，则由归纳：

$\text{Sum}(0,x,j)=0$

$\sum_{s=0}^jC_j^s\left(2^{x}\right)^{j-s}\text{Sum}(0,x,s)=0$

那么

$\text{Sum}(0,x+1,j)=\text{Sum}(0,x,j)-\sum_{s=0}^jC_j^s\left(2^{x}\right)^{j-s}\text{Sum}(0,x,s)=0$

若 $j=x$，则：

$\begin{aligned} \text{Sum}(0,x+1,j)&=\text{Sum}(0,x,j)-\sum_{s=0}^jC_j^s\left(2^{x}\right)^{j-s}\text{Sum}(0,x,s)\\ &=\text{Sum}(0,x,j)-\text{Sum}(0,x,j)=0 \end{aligned}$

于是命题对 $t=x+1$ 仍然成立。

因此，若 $t>j$，则 $\text{Sum}(0,t,j)=0$。

类似地，我们也可以证明：对于 $\text{Sum}(x,t,j)$，若 $x>2^j$，则同样也有 $\text{Sum}(x,t,j)=0$。

由上面两个结论，可以发现：实际上真正「有用」的 $x$ 只有 $O(k)$ 个。毕竟，如果 $x$ 太大了，那这个小可爱就是 $0$ 嘛QAQ。

那我们就可以在 $O(k^3)$ 的时间内计算后面的东西，再加上前面的东西，总复杂度 $O(\log_2n+k^3)$。足以通过本题。