P7468 愤怒的小N 题解
首先发现答案等于
\[\sum_{i=0}^{n-1}[cnt(i)\&1]\cdot f(i)\\ \]其中 \(cnt(x)\) 为 \(x\) 在二进制表示下 \(1\) 的个数。
考虑从高到低枚举第一个 \(n\) 是 \(1\) 而 \(i\) 是 \(0\) 的位置，那么更高位都相等。
假设这个位置是从低到高第 \(m\) 位。
那么对答案的贡献是 \(0\) 到 \(2^{m-1}-1\) 这些数中 \(a/b\) 的 \(f\) 函数值之和，具体取 \(a/b\) 取决于更高位 \(n\) 中 \(1\) 的个数。
考虑设计一个 \(dp\) 来求这个东西。
\(dp(i,j,0/1)\) 表示考虑了 \(0\) 到 \(2^{i}-1\)，所有的 \(a/b\) 的 \(x^j\) 的贡献之和。
设完这个状态后面再计算答案的时候相当于要计算这种 \((x+t)^j\) 的东西，暴力用二项式定理展开即可。
转移
\[dp(i,j,0)=dp(i-1,j,0)+\sum_{k=0}^j dp(i-1,k,1)\cdot\binom j k\cdot (2^{i-1})^{k-j}\\ dp(i,j,1)=dp(i-1,j,1)+\sum_{k=0}^j dp(i-1,k,0)\cdot\binom j k\cdot (2^{i-1})^{k-j} \]在 \(i>j\) 的时候 \(dp(i,j,0)=dp(i,j,1)=\sum_{x=0}^{2^i-1} \frac {x^j}2\)。
证明考虑归纳，当 \(i-1>j\) 的时候显然正确，当 \(i-1=j\) 的时候发现 \(k<j\) 的部分都满足。
两个式子中前面那项和后面那项的 \(k=j\) 加起来是完全一样的。
所以得证。
因此 \(dp\) 在 \(i>j\) 的时候特别好求，因为后面那个是关于 \(2^i-1\) 的 \(j+1\) 次多项式，可以拉格朗日插值。
所以延续最开始的思路，枚举从高到低第一个 \(n\) 是 \(1\) 而 \(i\) 是 \(0\) 的位置，钦定更高位都相等。
如果这个位置 \(i>k\)，那么可以插值，否则暴力求。
插值一次的复杂度是 \(O(k^2)\)，但是用下标连续的技巧可以做到 \(O(k)\)。
这样得到了一个复杂度为 \(O(k\log n+k^3)\) 的做法，\(\log n\) 最大是 \(5e5\)，可能比较卡常，不知道能不能过。
但是我们可以做到更优！！
复杂度瓶颈在于要做 \(\log n\) 次插值，太多了！！能不能只做常数次插值。
由于我们只能对 \(i>j\) 用插值，所以只能做 \(i>k\) 的部分。
把 \(n\) 拆分成 \(2^k\cdot a+b\) 的形式，那么前一部分可以一起通过一次插值搞定！！
对于剩下那个 \(b\)，就是前面都和 \(n\) 相等，最低的 \(k\) 位要小于 \(n\)，所以不能凑出满的 \(2^k\)，暴力做即可，二项式展开的复杂度也是 \(k^3\)。
总时间复杂度为 \(O(\log n+k^3)\)，空间复杂度：\(O(\log n+k^2)\)。
标签：P7468,log,插值,题解,复杂度,cdot,愤怒,sum,dp From： https://www.cnblogs.com/hellojim/p/17124549.html