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

cao2333 · 2026-10-19 11:14:08 · 题解

——是赛后补题咕。

本题解同步发表于 博客园。

题目传送门。

用老师 10RMB 巨资买下览遍千秋老师的讲课直播写出的做法。

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

:::info[题目简述]

给定一个长度为 n 的数组 A。

对于区间 l\sim r，可以执行以下操作：

• 令 S=0。
• 按照 A_l,A_{l+1},\ldots,A_r 的顺序，依次将 S 的值增加 A_i。

所有加法均按照普通的二进制加法进行，用 C(l,r) 表示 A 序列中区间 [l,r] 执行上述操作过程中发生的“进位”总数。

若一个长度为 m 的下表序列 \{p_1,p_2,\ldots,p_m\} 满足以下条件，则称其合法：

• 对任意 1\le i\le m，均满足 1\le p_i\le n。
• 对任意 1\le i< m，均满足 p_i<p_{i+1} 且 C(p_i,p_{i+1})=1。

两个数组不同，当且仅当两个数组长度不同，或至少一个位置的数字的不同。

求有多少个不同的合法数组，答案对 998,244,353 取模。

前置知识

首先我们要知晓二进制加法的性质：在二进制加法下，每产生一次进位，二进制就会减少一个 1。

:::info[证明]

1. 若一个二进制数位为 1 且加上了 1（共两个），这一位将会变成 0 并将 1 进位到下一位（共一个），总计减少了一个 1。
2. 若一个二进制数位是 0 且加上了 1（共一个），这一位将会变成 1 且没有产生贡献（共一个），总计不变。
3. 若一个二进制数位是 0 且加上了 0，显然不会进位也不会变化，总计不变。

对于进位使得原本不需要进位的数产生进位，可以视作额外进行若干次加法，等价于直接相加，上述结论依然成立。证毕。

因此我们记 \operatorname{cnt}(x) 表示 x 二进制下的 1 的个数，\operatorname{Addw}(x,y) 表示 x+y 所产生的进位数，有：

:::

初步

显然这是统计方案数，那么我们容易想到用 DP 处理转移。

定义 dp_i 表示以 i 结尾的数列方案数。

先考虑部分分做法，我们可以查找每一个数对 (l,r)，\mathcal{O}(n) 计算每两个数相加的进位数，检查答案，再将 dp_r\gets dp_r+dp_l。

时间复杂度 \mathcal{O}(n^3)。

预估应该可以拿下前两个测试点。

优化

考虑原题中 C(l,r) 如何用 O(1) 计算。

对于每个 C(l,r)，有：

将 \operatorname{Addw}(x) 展开，得到：

两两相消，得到

形式化的讲，即：

对于 \sum_{i=l}^{r}A_i，显然是经典前缀和。

对于 \sum_{i=l}^{r}\operatorname{cnt}(A_i)，同样可以用前缀和计算。

于是我们压掉了一维，现在时间复杂度 \mathcal{O}(n^2)。

正解

这个时间复杂度还是炸掉了呢。考虑把枚举区间优化掉。

对于 \operatorname{cnt}(x)，显然其值非负。因此必然的，区间变长，C(l,r) 不可能变小。

也可以感性理解：加的数越多，进位越多；加的数越少，进位越少。

形式化地，有：

• 锚定右端点 r，左端点 l 向右移，C(l,r) 越来越小。
• 锚定左端点 l，右端点 r 向右移，C(l,r) 越来越大。

那么当 r 锚定时，所有对应的 C(l,r) 随 l 递增单调不增。

于是，所有合法的左端点一定连成一片。

:::info[证明] 采用反证法，假设存在一个 l 和一个大于一的正整数 k，使得对于单一右节点 r，满足 C(l,r)=1,C(l-1,r)\ne 1 且 C(l-k)=1。

那么由于 C(l,r) 随 l 递增不增，因此 C(l-1)\ge 1，且由于 l-k<l-1，因此 C(l-1)\le 1。

综上，C(l,r)=1，与假设矛盾，因此不存在不连续的 l 使得 C(l,r)=1。证毕。

:::

维护 cl 表示当 r 锚定时，第一个满足 C(l,r)=1 的 l，cr 表示第一个满足 C(l,r)=0 的 r。

那么所有合法左端点构成滑动区间 [cl,cr)（或者说 [cl,cr-1]）。

状态转移方程变成

其中 1 是指单独一个数 r 组成的合法序列。

这个也可以再加上一个 dp 数组的前缀和 \mathcal{O}(1) 解决。

因此我们维护总共三个指针 r,cl,cr 分别表示枚举右端点、合法左端点左界、合法左端点右界，三个指针一定全部向右移动；再维护 pre, prec, predp 分别维护原数组前缀和、\operatorname{cnt}(x) 的前缀和、dp 数组的前缀和，每个右端点的方案数为：

可以 \mathcal{O}(n) 解决。

时间复杂度非常优秀，可以拿到满分。

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long //Ai>=10^12.
#define cnt(x) (__builtin_popcountll(x)) //cnt 函数在这里呢咕
#define endl '\n'
const int N=5e5+7;
const int mod=998244353;

//快读快写
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c-'0'),c=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0)x*=-1,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

int n,T;
//dp 统计方案数
int a[N],dp[N];
//pre 统计原数组前缀和，prec 统计 cnt 前缀和，predp 统计 dp 前缀和
int pre[N],prec[N],predp[N];

//即题面中的 C(l,r) 函数，为了区分和寓意吉利（bush。
inline int AC(int l, int r){
    return prec[r]-prec[l-1]-cnt(pre[r]-pre[l-1]); 
  //见上。
}

signed main(){
    T=read();
    while(T--){
        memset(pre,0,sizeof(pre));
        memset(prec,0,sizeof(prec));
        memset(predp,0,sizeof(predp));
    //多测清空。
        n=read();
        for(int i=1; i<=n; i++){
            a[i]=read();
            pre[i]=pre[i-1]+a[i];
            prec[i]=prec[i-1]+cnt(a[i]);
        }
    //cl 表示合法左界，cr 表示合法右界，r 表示右端点，ans 用于统计答案。
        int cl=1,cr=1,r=1, ans=0;
        while(r<=n){
            while(cl<r && AC(cl,r)>1) cl++;//处理合法界限，见上。
            while(cr<r && AC(cr,r)>0) cr++;
            dp[r]=(1+predp[cr-1]-predp[cl-1]+mod)%mod;//记得加上一个模数防止出现负数。
            predp[r]=(predp[r-1]+dp[r]+mod)%mod;
            r++;
        }
        for(int i=1; i<=n; i++) ans=(ans+dp[i]+mod)%mod;//记得取模
        write(ans);
        putchar('\n');
    }
    return 0;
}

// Code by cao2333, [email protected]

后记

感谢览遍千秋老师的讲解。这道题其实还有一个小细节：二进制下加法进位个数与加法顺序无关，且多数加和进位同样可以用公式计算，可以根据 C(l,r) 的推导式 得到。以及这道题还有 \mathcal{O}(n\log n) 做法，出题人拼尽全力无法卡掉。

注意事项：

1. 取模时一定要加上一个模数防止出现负数。
2. 不要 给涉及 C(l,r) 的计算的任何数据取模（包括 A,pre,prec）。
4. 观察左界与右界的区别，检查初始值，检查有没有 dp_r+1。