这个题看到第一眼不是暴力数位 dp 创过去吗?
换以前,我虽然忘了数位 dp ,但是可能接着这个机会重新学一遍数位 dp 。
但是最近工作任务和学校任务都很重,根本不想重新学一遍数位 DP 。
反而让我发现了一个更通用更好更简单的做法。
洛谷链接:https://www.luogu.com.cn/problem/P14074
核心问题:问题容易被转化成计算 \(x \in [0, N]\) 中,所有满足 \(popcount(x)\) 是奇数的数字之和。
为了不引起人类语言上的歧义,形式化表示即要求计算:
其中 [p]
若 \(p\) 为真返回 \(1\) ,若 \(p\) 为假返回 \(0\) 。
关于 \(0 \sim N\) 内所有数在二进制下的加法贡献问题,常见的最无脑最简单方法是把指数折半。
根据经验,如果有 \(L(a^{x + y}) = L(a^{x}) \times L(a^{y})\) ,那么我们可以把 \(O(a^{x + y})\) 级问题转化为 \(O(max(a^{x}, a^{y}))\) 级问题。
以上是一些经验主义的东西。
接下来介绍实际的解法。
考虑带余整除法 \(v = 2^{k} \cdot x + r \ (0 \leq r < 2^{k})\) 。其中 \(2^k \leq N\) 且 \(k\) 为常数。
每个组(每个块)余数取满 \(0 \sim 2^{k} - 1\) ,则 \(0 \sim N\) 可以分成 \(\lceil N / 2^{k} \rceil\) 个块。
根据 \(x = 0, 1, 2, \cdots, \lceil N / 2^{k} \rceil - 1\) 对每个块编号,分布如下:
\(x = 0, 1, 2, \sim \lceil N / 2^{k} \rceil - 2\) 的块一定都完整。
\(x = \lceil N / 2^{k} \rceil - 1\) 块可能不完整,即 \(r\) 不能取满 \(0, 1, \cdots, 2^{k} - 1\) 。
-
考虑某个完整的块,即 \(0 \leq x < \lceil N / 2^{k} \rceil - 1\) 。
由于 \(r\) 不超过 \(k\) 位,则 \(popcount(v = 2^{k} \cdot x + r) = popcount(v = (x << k) + r) = popcount(x) + popcount(r)\) 。
一个块对应唯一 \(x\) ,则 \(popcount(x)\) 已知。这个块的贡献是:
\[\sum_{ \substack{ r = 0, \\ popcount(x) + popcount(r) \equiv 1 (\bmod 2) } }^{2^{k} - 1} x \cdot 2^{k} + r \]考虑 \(k\) 个位置,选择一些位置为 \(1\) ,否则为 \(0\) ,容易证明(并且早就知道):
\[\begin{aligned} \binom{k}{0} + \binom{k}{2} + \binom{k}{4} + \cdots \binom{k}{2 \lfloor k / 2 \rfloor} + \binom{k}{1} + \binom{k}{3} + \binom{k}{5} + \cdots \binom{k}{2 \lceil k / 2 \rceil - 1} = \sum_{i = 0}^{k} \binom{k}{i} = 2^{k} \\ \\ \binom{k}{0} + \binom{k}{2} + \binom{k}{4} + \cdots \binom{k}{2 \lfloor k / 2 \rfloor} = \binom{k}{1} + \binom{k}{3} + \binom{k}{5} + \cdots \binom{k}{2 \lceil k / 2 \rceil - 1} = 2^{k - 1} \\ \end{aligned} \]于是这个块的贡献是:
\[\begin{aligned} &x \cdot 2^{k} \cdot 2^{k - 1} + \sum_{ \substack{ r = 0, \\ popcount(x) + popcount(r) \equiv 1 (\bmod 2) } }^{2^{k} - 1} r \\ &= x \cdot 2^{k} \cdot 2^{k - 1} + \begin{cases} \sum_{ \substack{ r = 0, \\ popcount(r) \equiv 0 (\bmod 2) } }^{2^{k} - 1} r,\ popcount(x) \equiv 1 (\bmod 2); \\ \sum_{ \substack{ r = 0, \\ popcount(r) \equiv 1 (\bmod 2) } }^{2^{k} - 1} r,\ popcount(x) \equiv 0 (\bmod 2). \\ \end{cases} \end{aligned} \]这里我们已经可以 \(O(2^{k})\) 预处理
\[\begin{aligned} S_{even} = \sum_{ \substack{ r = 0, \\ popcount(r) \equiv 0 (\bmod 2) } }^{2^{k} - 1} r \\ S_{odd} = \sum_{ \substack{ r = 0, \\ popcount(r) \equiv 1 (\bmod 2) } }^{2^{k} - 1} r \\ \end{aligned} \]总共有 \(\lceil N / 2^{k} \rceil - 1\) 个块。
-
考虑最后一个块,即 \(x = \lceil N / 2^{k} \rceil - 1\) 。
可以暴力遍历 \(r \in [x \cdot 2^{k} + 0, N]\) ,若 \(popcount(x)\) 和 \(popcount(r)\) 的奇偶性不同,则对答案贡献 \(x \cdot 2^{k} + r\) 。
综上,时间复杂度 \(O(max(N / 2^{k}, 2^{k}))\) 。如果把 \(k\) 取成 \(N\) 的二进制表示的一半,由 \(2^{a} \cdot 2^{b} = 2^{a + b}\) ,时间复杂度为 \(O(\sqrt{N})\) 。
Code
#include<iostream>
#include<cassert>const int32_t K = 16;
const int64_t BLOCK = int64_t(1) << K;int64_t S_even, S_odd;int64_t S(int64_t N) {if (N == 0) return 0;int64_t M = (N + BLOCK - 1) / BLOCK;int64_t rem = N % BLOCK;int64_t ret = 0;assert(M >= 1);for (size_t x = 0; x < M - 1; x++) {ret += int64_t(x) * (1 << K) * (1 << K - 1) + (__builtin_popcount(x) == 0 ? S_odd : S_even);}int32_t x = M - 1;for (size_t r = 0; r <= rem; r++) if ((__builtin_popcount(r) + __builtin_popcount(x) ) % 2 == 1) {ret += x * BLOCK + r;}return ret;
}int main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);int64_t D, U;std::cin >> D >> U;for (size_t i = 0; i < BLOCK; i++) {if (__builtin_popcount(i) % 2 == 0) S_even += i;if (__builtin_popcount(i) % 2 == 1) S_odd += i;}std::cout << S(U) - S(D - 1) << "\n";return 0;
}
当 \(k \geq 2\) ,可以证明(有时间再说,有简单但是很长的构造,也有很短但是用生成函数构造)
那么代码可以优化成:
Code
#include<iostream>
#include<cassert>const int32_t K = 16;
const int64_t BLOCK = int64_t(1) << K;int64_t S(int64_t N) {if (N == 0) return 0;int64_t M = (N + BLOCK - 1) / BLOCK;int64_t rem = N % BLOCK;int64_t ret = 0;assert(M >= 1);for (size_t x = 0; x < M - 1; x++) {ret += int64_t(x) * (1 << K) * (1 << K - 1) + int64_t(1) * (1 << K - 2) * ((1 << K) - 1);}int32_t x = M - 1;for (size_t r = 0; r <= rem; r++) if ((__builtin_popcount(r) + __builtin_popcount(x) ) % 2 == 1) {ret += x * BLOCK + r;}return ret;
}int main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);int64_t D, U;std::cin >> D >> U;std::cout << S(U) - S(D - 1) << "\n";return 0;
}
最后我突然发现好像能从 \(O(\sqrt{N})\) 优化到 \(O(1)\) …… 后面再说。