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

· · 题解

P17729 [SCP-J 2026] 进位 [题解]

题目大意

使用 C(l,r) 表示 a 数组区间 l\sim r 二进制下求和过程中发生的进位总数。

要求构造一个序列 p，其中的每一个数都是原数组的下标，且对于任意 1\le i< m，均满足 p_i<p_{i+1} 且 C(p_i,p_{i+1})=1。

Solution

快速计算进位

我们使用 cnt(x) 表示 x 在二进制下 1 的个数。

不难发现，如果 cnt(x)+cnt(y)=cnt(x+y)，那一定没有发生进位，同理，如果 cnt(x)+cnt(y)>cnt(x+y) 那么一定发生进位，且进位次数就是 cnt(x)+cnt(y)-cnt(x+y)。

可以这样理解：在二进制下计算时，如果当前位都为 1，那一定相加变为 0，同时向前进 1。这样，原本两个 1 变为了一个，多次进位也同理。

此时，区间 l\sim r 的进位次数就是：

cnt(a_l)+cnt(a_{l+1})-cnt(a_l+a_{l+1})+cnt(a_l+a_{l+1})+cnt(a_{l+2})-(a_l+a_{l+1}+a_{l+2}+...)

发现中间一减一加消掉了，原式化简为：

cnt(a_l)+cnt(a_{l+1})+...+cnt(a_{r})-cnt(a_l+a_{l+1}+...+a_r)

这显然可以使用两个前缀和数组维护，即可做到 O(1) 查询进位次数。

扫描区间统计答案

首先，假定我们有区间 [l,r]，若 l 向右移，C(l,r) 一定不增加，同理，若 l 向左移，C(l,r) 一定不降。

又因为题目要求进位次数为 1 的区间，所以符合条件的左端点 l 一定连续，且可能到达的最靠左的位置一定是第一个使得区间和为 1 的位置，最靠右的位置就是最后一个使得区间和为 1 的位置。

定义 dp[i] 表示以 i 为结尾的区间有多少满足进位数为 1。

于是合法左端点成为一个区间 [l,r-1]。

状态转移式即为：

dp_R = 1+\sum_{i=l}^{r-1} dp_i

同样我们可以使用一个 dp 的前缀和数组快速查询。

最终算法流程

开三个指针 l，r，R，分别表示合法左端点最靠左的位置，合法左端点最靠右的位置，右端点。

同时维护三个前缀和数组：

对于每个固定右端点，计算答案：

dp_R = sdp_{r-1}-sdp_{l-1}+1

注意不要忘记取模，处理负数情况。

Code

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define cnt(x) __builtin_popcountll(x)
#define int long long
const int MOD = 998244353;
const int N = 6e6+5;
int t;
int n;
int a[N];
int s1[N],s2[N];
int sdp[N],dp[N];
int C(int l,int r){
    return s2[r]-s2[l-1]-(cnt(s1[r]-s1[l-1]));
}
signed main(){
    cin>>t;
    while(t--){
        scanf("%lld",&n);
        memset(dp,0,sizeof dp);
        memset(sdp,0,sizeof sdp);
        s1[0] = 0;
        s2[0] = 0;
        for(int i = 1;i<=n;i++) scanf("%lld",&a[i]),s1[i] = s1[i-1]+a[i];
        for(int i = 1;i<=n;i++) s2[i] = s2[i-1]+cnt(a[i]);
        int l = 1,r = 1,R = 1,ans = 0;
        while(R<=n){
            while(l<R&&C(l,R)>1) l++;
            while(r<R&&C(r,R)>0) r++;
            dp[R] = (1+sdp[r-1]-sdp[l-1]+MOD)%MOD;//+MOD处理负数
            sdp[R] = (sdp[R-1]+dp[R]+MOD)%MOD;//+MOD处理负数
            R++;
        }
        for(int i = 1;i<=n;i++) ans = (ans+dp[i])%MOD;
        cout<<ans<<'\n';
    }
    return 0;
}

:::: ::::warning[警告]

  1. 注意不要忘记取模。
  2. 记得加上模数处理负数情况。
  3. 不要用 cin，不然你会 T 飞。