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

· · 题解

题意：

给定一个长度为 n 的序列 a，你要求出有多少个长度为 m 升序序列 p，使得对于任意 2\le i\le m，满足从 a_{p_{i-1}} 加到 a_{p_i} 有且只有一次进位，m 长度自定。

题目分析：

首先我们定义 popcount(x) 表示在二进制下 x 的二进制位为 1 的个数。我们不难将进位次数转化为一开始有 1 的位数和最终和的 1 的位数只差为 1，即为：

\sum_{i=l}^r{popcount(a_i)}-popcount(\sum_{i=l}^r{a_i})=1

由于 p 序列相邻两数都得满足这个条件，转移仅与相邻两数有关我们不难想到动态规划，我们设 dp_i 表示序列 p 的结尾为 i 的方案数。

我们不难想到转移就是从两点之间进位刚好为 1 的点转移。由于对于固定右端点长度越长的序列进位数必然单调不降，那么进位数刚好为 1 的左端点一定是一段连续的区间，且对于右端点的右移，左端点的区间也一定会不动或向右移。我们更据前面的转换用双指针找到这段能转移的区间。转移由于是加上一段连续的区间我们把动态规划状态改为前缀和即可，即为 dp_i 表示结尾为 1 到 i 的方案数之和。注意长度为 1 的序列 p 一定是合法的，那么对于每一次转移我们可以提前给 dp 加 1。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10,mod=998244353;
int t,n;
ll dp[N],a[N];
inline ll read(){
    ll w=0,f=1;
    char ch=getchar();
    while(ch<'0' || '9'<ch){
        if(ch=='-') f=-1;
        ch=getchar(); 
    }
    while('0'<=ch && ch<='9'){
        w=(w<<3)+(w<<1)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
signed main(){
    cin.tie(0);cout.tie(0);
    //ios::sync_with_stdio(false);
    t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n;i++) a[i]=read(),dp[i]=0;
        dp[0]=0;
        int l=1,r=1;
        ll popl=0,popr=0,suml=0,sumr=0;
        for(int i=1;i<=n;i++){
            ll x=a[i];
            int px=__builtin_popcountll(x);
            suml+=x;popl+=px;
            while(l<=i){
                int c=popl-__builtin_popcountll(suml);
                if(c<=1) break;
                ll y=a[l];
                suml-=y;popl-=__builtin_popcountll(y);
                l++;
            }
            sumr+=x;popr+=px;
            while(r<=i){
                ll y=a[r];
                ll nsum=sumr-y;
                ll npop=popr-__builtin_popcountll(y);
                ll nc=npop-__builtin_popcountll(nsum);
                if(nc>=1){
                    sumr=nsum;
                    popr=npop;
                    r++;
                }else break;
            }
            int R=0;
            int cr=popr-__builtin_popcountll(sumr);
            if(cr>=1) R=r;
            else R=0;
            ll ways=1;
            if(l<=R){
                ways+=(dp[R]-dp[l-1]);
                ways%=mod;
                if(ways<0) ways+=mod;
            }
            dp[i]=dp[i-1]+ways;
            if(dp[i]>=mod) dp[i]-=mod;
        }
        cout<<dp[n]<<'\n';
    }
    return 0;
}