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

hehaoyanghy · 2026-10-19 10:40:07 · 题解

此篇题解主要是讲述跳 0 做法。

具体做法

首先因为我们只统计了非零的数，所以只需要固定一个左端点后从左向右枚举至多 \log{V} + 2 次就可以找出来。接着我们考虑如何计数。

首先我们先不考虑零，我们用 c_i 来表示以 i 结尾的合法序列个数。确定一个左端点 l，在枚举右端点 r 的时候每遇到一个合法的 r，我们的答案便加上一个 c_l，然后给 c_r 加上一个 c_l 就可以了。

接着我们考虑零，此时我们弄一个新序列 a，用来储存非零的数，再弄一个序列 p，用来记录序列 a 在原序列的下标。我们考虑如何处理零，对于一个左端点 l 和一个合法的右端点 r，此处的 l 和 r 均指 a 中的下标，它会使 c_{r+1} 加上 a_r 与 a_{r+1} 之间 0 的个数乘上 c_l，对于最终的答案，它会加上 (p_{r+1}-p_{r}) \times c_l 聪明的你相信一眼就可以看出为什么。

最后别忘记在一开始的时候在 c_i 加上它本身和它与 c_{i-1} 之间 0 的个数。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[500009],p[500009],c[500009],k,T;
int jw(int x,int y) {
    return __builtin_popcountll(x)+__builtin_popcountll(y)-__builtin_popcountll(x+y);
}
const int mod=998244353;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) {
        cin>>n;
        int y=1;
        for(int i=1; i<=n; i++) {
            int x;
            cin>>x;
            if(!x) y++;
            else a[++k]=x,p[k]=i,c[k]=y,y=1;
        }
        p[k+1]=n+1;
        for(int i=1; i<=k; i++) {
            int s=a[i],f=0;
            for(int j=i+1; j<=k; j++) {
                f+=jw(s,a[j]),s+=a[j];
                if(f==1) {
                    n=(n+(p[j+1]-p[j])*c[i]%mod)%mod;
                    c[j]=(c[j]+c[i])%mod,c[j+1]=(c[j+1]+(p[j+1]-p[j]-1)*c[i]%mod)%mod;
                }
                if(f>1) break;
            }
        }
        cout<<n<<'\n';
        for(int i=1; i<=k+1; i++) a[i]=c[i]=p[i]=0;
        k=0;
    }
    return 0;
}