第 N+1 次头疼

头晕头痛，耳鸣眼花，什么题都做不出了。

P7468 愤怒的小 N

题意

给 $k-1$ 次多项式 $f(x)$，求 $\sum_{i=1}^n[\mathrm{popcount}(i)\bmod 2]f(i)$，对 $10^9+7$ 取模。$\log_2 n \leq 5\times 10^5$，$k \leq 500$。

题解

$\log_2 n$ 实在是太大了，而这个 $\mathrm{popcount}(i)\bmod 2$ 也就是只统计二进制下有奇数个 $1$ 的数比较烦。如果我们把它变成 $\dfrac {1}{2}-\dfrac 12(-1)^{\mathrm{popcount}(i)}$ 的形式分别计算，那么前半部分与 $i$ 无关，后半部分的形式就变得很好。具体而言：

$\begin{aligned} &\sum_{i=1}^n[\mathrm{popcount}(i)\bmod 2]f(i)\\ =&\dfrac 12\sum_{i=1}^nf(i)-\dfrac 12\sum_{i=1}^n(-1)^{\mathrm{popcount}(i)}f(i) \end{aligned}$

前面一部分拉格朗日插值，容易处理。后半段我们可以枚举 $i$ 与 $n$ 二进制位的 LCP，那么后面的二进制位就不受限制，前面在 $(-1)^{\mathrm{popcount}(i)}$ 的贡献无非就是一个容易计算的 $1$ 或 $-1$。记 $m_x=2^x\left\lfloor\dfrac{n}{2^x}\right\rfloor$，也就是 $n$ 去掉最低 $x$ 位之后的结果，则答案为：

$\begin{aligned} &\sum_{x=1}^{\log_2 n}[n \operatorname{and} 2^x \neq 0](-1)^{\mathrm{popcount}(m_x)}\sum_{i=0}^{2^{x}-1}(-1)^{\mathrm{popcount}(i)}f(m_x+i)\\ =&\sum_{x=1}^{\log_2 n}[n \operatorname{and} 2^x \neq 0](-1)^{\mathrm{popcount}(m_x)}\sum_{i=0}^{2^{x}-1}\sum_{j=0}^{k-1} a_j(m_x+i)^j(-1)^{\mathrm{popcount}(i)}\\ =&\sum_{j=0}^{k-1} a_j\sum_{t=0}^{j}\dbinom{j}{t}\sum_{x=1}^{\log_2 n}[n \operatorname{and} 2^x \neq 0](-1)^{\mathrm{popcount}(m_x)}m_x^{j-t}\sum_{i=0}^{2^{x}-1}(-1)^{\mathrm{popcount}(i)}i^{t} \end{aligned}$

令 $g(x,t)=\sum\limits_{i=0}^{2^{x}-1}(-1)^{\mathrm{popcount}(i)}i^{t}$，类似上面的拆位我们把第 $x$ 位拆出来：

$\begin{aligned} g(x,t)&=g(x-1,t)+\sum\limits_{i=2^{x-1}}^{2^{x}-1}(-1)^{\mathrm{popcount}(i)}i^{t}\\ &=g(x-1,t)-\sum\limits_{i=0}^{2^{x-1}-1}(-1)^{\mathrm{popcount}(i)}\sum_{j=0}^{t}\dbinom tj2^{x(t-j)}i^j\\ &=g(x-1,t)-\sum_{j=0}^{t}\dbinom tj2^{x(t-j)}g(x-1,j) \end{aligned}$

此时我们已经可以 $O(k^2 \log n)$ 递推求解，但这还不够。一个简单但不易观察到的性质是 $x>t$ 时 $g(x,t)=0$，可以归纳法证明。此时 $g$ 的递推变为了 $O(k^3)$，原式的求和中 $x$ 也只用枚举到 $t$：

$\sum_{j=0}^{k-1} a_j\sum_{t=0}^{j}\dbinom{j}{t}\sum_{x=1}^{t}[n \operatorname{and} 2^x \neq 0](-1)^{\mathrm{popcount}(m_x)}m_x^{j-t}g(x,t)$

这样就 $O(k^3)$ 做完了。

P3447 [POI2006]KRY-Crystals

题意

给出序列 $a_{1\sim n}$，求满足以下条件的序列 $b$ 的个数：

• $\forall i$，$0 \leq b_i \leq a_i$；
• $b_1\oplus b_2\oplus \ldots\oplus b_n=0$。

$n \leq 50$，$a_i<2^{32}-1$，保证答案小于 $2^{64}$。

题解

如果前面 $n-1$ 个数已经填好，那么第 $n$ 个数只有一种选择，但它的上限会限制合法性。如果 $a_n = +\infty$，则方案数就是 $\prod_{i=1}^{n-1}(a_i+1)$。

这启示我们从高位到低位考虑，不妨设所有 $a_i$ 中最高的位为 $w$，$a_i$ 包含最高位的 $i$ 的集合为 $S$。如果存在一个包含最高位的 $a$，它的 $b$ 在 $w$ 这一位不顶上界（即取 $0$）的情况，如果其非空子集 $T$ 内的 $b_i$ 最高位填的是 $0$，也就是非最高位不受限，那么只需要从 $T$ 集合中任取一个放最后「补漏」，其它随便取即可，方案数就是：

$\sum_{T\subseteq S, T \neq \varnothing}[|S|-|T| \text{ is even}](2^w)^{|T|-1}\prod_{i \not\in T}(a_i\bmod 2^w+1)$

这个式子可以一遍 DP 简单地 $O(n)$ 算出，不赘述。剩下的情况只有 $S$ 内所有 $b$ 最高位都填 $1$，判断合法性后就是将所有数都去掉最高位之后的子问题了。故我们做 $O(\log m)$ 次 DP 即可求出答案，时间复杂度 $O(n \log m)$。

P7408 [JOI 2021 Final] ダンジョン 3

题意

$n+1$ 个加油站，第 $i$ 与 $i-1$ 个之间距离 $a_i$ 个单位长度，第 $i$ 个加油站加单位油量需要花费 $b_i$。

车只能向右走，走 $1$ 单位长度要用 $1$ 单位油量，用完不能走。加油不能超过油量上限。

$m$ 组询问，每次给出 $l,r,x$ 表示一辆车从 $l$ 走到 $r$ 并且油量上限为 $x$ 需要花费的最小代价。

$1 \leq n,m,a_i,b_i \leq 2\times 10^5$，$1 \leq x \leq 10^9$。

题解

令油量上限为 $u$，有一个贪心：找到当前位置后第一个价格比它小的位置 $x$，加油至能走到 $x$ 为止；若到 $x$ 的距离 $\ge u$，则加满 $u$ 然后往后走一步。

考虑如何维护这个贪心：固定右端点，从右往左扫描左端点，维护价格递减的单调栈（为方便表述，令栈中元素是位置），栈顶即要找的位置。令当前位置为 $i$，$i$ 加入单调栈后，策略的变化是用 $b_i$ 替换从 $i$ 到栈顶的前 $u$ 个单位的油，不足则全部替换。原因是，我找到原单调栈中与 $i$ 距离 $\ge u$ 的第一个位置，到达此位置时我一定没油，后面策略就不变了。

但询问的 $u$ 不等，就要讨论单调栈每一段的贡献。具体而言，假设我此时弹出 $x$，弹出后的栈顶为 $y$：

• $u\leq x-i$：无贡献。
• $x-i<u$：将 $\min(u+i,y)-x$ 单位油的价格由 $b_x$ 替换为 $b_i$，贡献 $(b_i-b_x)(\min(u+i,y)-x)$。

容易发现这是个关于 $u$ 的分段一次函数，线段树可以维护，这样就解决 Subtask 3 了。

对于区间 $[l,r]$ 的询问，我们找出 $[r-u,r]$ 中最小价格的位置 $k$，则 $k$ 处的决策一定是加满油到走到 $r$ 为止，这段路与「从 $k$ 走到最后」的决策完全一致，所以 $\operatorname{ans}(l,r)=\operatorname{ans}(l,+\infty)-\operatorname{ans}(k,+\infty)+b_k(r-k)$。

只需要将右端点固定为最右边就可以算出 $\operatorname{ans}(i,+\infty)$，时间复杂度 $O(n \log n)$。