P17729 [SCP-J 2026] 进位 题解

· · 题解

P17729 [SCP-J 2026] 进位 题解

看到这道题我们发现这道题是一道策略类问题。

思路

Step 1: 大体框架

这道题显然就是一道分段问题，也就是序列 DP 的模板。

那我们不妨设 dp_i 为前 i 个满足条件的方案数的总和。

转移方程也很显然：

dp_i=\sum_{j=0}^{i-1}dp_j[C(j,i)=1]

显然，这个复杂度为 O(n^2) 显然超时的。我们实际上只要解决两个问题：

  1. 如何求快速求 C(a,b)；
  2. 如何优化掉 DP 的 j 循环。

Step 2: 快速求 C(a,b)

首先，题目在末尾特地写了 __builtin_popcount 的用法，显然就是让你用。（还有更显然的吗）

接下来，我们要用一个结论：二进制加法的进位数等于加法前后数中 1 的数量之差。

::::info[证明] 采用一一对应法，即证：每一次进位都会减少一个 1。

分类讨论：

  1. 1 + 1：此时会变为 10，减少了 1 个 1；
  2. 1 + 0：并没有进位，1 的数量不变；
  3. 0 + 0：并没有进位，1 的数量不变。
这里很多人可能会问，如果进位了之后因为这次进位有进位了呢？那实际上就是下一次计算涵盖的了。可以自己品味一下。

为了方便，后文将 __builtin_popcount 简称为函数 PC。

那么，对于任意两个数 x+y 产生的进位数为：PC(x) + PC(y) - PC(x + y)。

然后，我们注意这个 C(x,y) 的计算式子，实际上等于（s_i 为 a_i 的前缀和）：

C(x,y)=\sum_{i=x}^{y}{PC (a_i) + PC(s_{i-1})-PC(s_i)}

此时，我们发现 PC(s_i), PC(s_{i-1}) 可以交叉相减化简掉，于是：

C(x,y)=\sum_{i=x}^{y}{PC(a_i)} - PC(\sum_{i=x}^{y}a_i)

这些都可以用前缀和预处理，并以 O(1) 的复杂度调用。

Step 3: 优化

对于很多二进制有关的题目而言，按照位数进行处理是一个非常好的优化方法。因为不难发现实际上位数的常数很小，只有 100 不到（骗你的，实际上在 int 范围只有 32）。

因此，这里我的方法和其他大佬不是非常一样：

我们知道，这个数最多有 41 位。那么，问题来了，一个只有 41 位的数最多有多少个 1 呢？（这还用想吗）

当然是最多 41 个了啊。

我们既然要求的是 C(x,y)=1 的数字，那么带入可以得到：

\sum_{i=x}^{y}{PC(a_i)} - PC(\sum_{i=x}^{y}a_i)=1

变形一下：

\sum_{i=x}^{y}{PC(a_i)} = PC(\sum_{i=x}^{y}a_i) + 1

注意到：

PC(\sum_{i=x}^{y}a_i) \leqslant 41

那么，很显然：

\sum_{i=x}^{y}{PC(a_i)}\leqslant 42

然而，每一个 a_i 都对这个答案一定有贡献（a_i = 0 的情况将在后续进行讨论)，也就是说，有条件满足 C(x,y) = 1 的数最多有 42 个，而且，由于这个是单调递增的，也就是说，这 42 个一定是连续的。

也就是说，实际上，我们无论如何，只需要将 DP 的 j 循环的次数改成 42 就可以了，即：

dp_i=\sum_{j=i}^{\max(i-42,0)}dp_j[C(j,i)=1]

细节

当然，由于 0 这个数对答案的贡献为 0，对答案的贡献 dp_i = dp_{i-1}，因此，我们在对于非 0 数位 a_i 计算 dp_i 的时候，我们实际上在枚举 dp_i 的过程中可以跳过这个为 0 的 a_i。因此我们只需要记录一下每个位置的上一个非 0 位置的下标就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 10, MOD = 998244353;
ll a [N], bit [N], pre [N], ans [N];
int main () {
    int T; scanf ("%d", &T);
    while (T --) {
        int n; scanf ("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf ("%lld", a + i);
        int lst = 0;
        for (int i = 1; i <= n; i++) {
            bit [i] = __builtin_popcountll (a [i]);
            pre [i] = lst;
            if (a [i] != 0)
                lst = i;
        }
        ans [0] = 0;
        for (int i = 1; i <= n; i++) {
            ll sum = 0, sum_bit = 0, f = 0;
            for (int p = i; p != 0; p = pre [p]) {
                sum += a [p]; sum_bit += bit [p];
                if (sum_bit > 42) break;
                if (sum_bit - __builtin_popcountll(sum) == 1) {
                    f += (ans [p] - ans [pre [p]]) % MOD;
                    if (f >= MOD) f -= MOD;
                }
            }
            ans [i] = (ans [i - 1] + (f + 1) % MOD + MOD) % MOD;
        }
        cout << ans [n] << '\n';
    }
    return 0;
}