题解：P17729 [SCP-J 2026] 进位 / carry

xrz_like_genshin · 2026-10-19 07:33:56 · 题解

P17729 题解

喵！

虽说这道题能用双指针做，可我就偏偏用二分做。

思路

先设 \text{P}(x) 表示 x 中二进制位中 1 的个数。

我们发现两个数 a,b 相加的过程中，每次进位都会使最后的和的二进制位中 1 的个数少一，也就是若进了 x 次位，则 \text{P}(a+b)=\text{P}(a)+\text{P}(b)-x。推而广之，那么我们就可以得出：

移位一下，得：

所以当我们的 C(l,r)=1 时，\left(\sum_{p=l}^{r}\text{P}(a_p)\right)-\text{P}(\sum_{i=l}^{r}a_i)=1。因为固定 r 时的区间的范围越大，即 l 越小，进位数一定不会减少，范围越小，即 l 越大，进位数一定不会增多。根据这个我们发现，对于一个 r，其符合条件的 l 一定是一个区间，况且这个区间的判断条件我们是知道的，并且区间的判断条件还符合单调性，这不就是二分吗。所以我们可以通过二分二分出第一个满足条件的和最后一个满足条件的，它们之间的数一定都满足条件，设 r 满足条件的 l 区间为 [L_r,R_r]。

题目让我们求 p 的方案数，可我们发现当我们已经求出 [L_r,R_r] 时，也就是对于 p_i，我们知道 p_{i-1} 能填啥时，dp 可能是比较好做的。具体的，因为 p 序列的长度不固定，所以我们设 dp_i 表示目前的 p 在最后一个位置填了 i 时 p 的方案数，注意这个 p 的长度我们后面还可以加的。根据上述所说，可得：

要加一是因为 i 还可以当第一个。这个柿子明显可以通过记录 dp 数组的前缀和来优化到线性。具体的，我们设 dps_i=\sum_{j=1}^{i}dp_j，则转移式为：

可以方便的求解。

时间复杂度 \text{O}(\sum n\log n)，需要注意一下常数。空间复杂度 \text{O}(n)。

上代码

#include <bits/stdc++.h>
#define int long long
#define pc __builtin_popcountll

using namespace std;

const int N = 5e5 + 5, Mod = 998244353;

int t, n, a[N], sum[N], s[N], L[N], R[N], dp[N], dps[N]; // sum 二进制位中一的个数的前缀和，s 原序列的前缀和 dps dp 数组的前缀和

void Solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        sum[i] = sum[i - 1] + pc(a[i]);
        s[i] = s[i - 1] + a[i];
    }
    for(int i = 1; i <= n; ++i){
        int l = 1, r = i;
        L[i] = n + 1;
        R[i] = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            int x = sum[i] - sum[mid - 1], y = pc(s[i] - s[mid - 1]);
            if(x == y){
                r = mid - 1;
                R[i] = mid - 1;
            }else{
                l = mid + 1;
            }
        } // 第一个 C(x,i)=0 的下标减一即为 R_i
        r = R[i], l = 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            int x = sum[i] - sum[mid - 1], y = pc(s[i] - s[mid - 1]);
            if(x == y + 1){
                r = mid - 1;
                L[i] = mid;
            }else{
                l = mid + 1;
            }
        } // 第一个 C(X,i)=1 的下标即为 L_i
    }
    for(int i = 1; i <= n; ++i){
        if(L[i] > R[i]){
            dp[i] = 1; // i 只能当开头
        }else{
            dp[i] = (1 + dps[R[i]] - dps[L[i] - 1] + Mod) % Mod;
        }
        dps[i] = (dps[i - 1] + dp[i]) % Mod;
    }
    cout << dps[n] << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while(t--){
        Solve();
    }
    return 0;
}

管理审核辛苦了！