2026牛客寒假算法基础集训营1 H. Blackboard

叠甲：博主是灰名低手，建议移步其他大佬的题解

H. Blackboard

本题中 | 运算优先级高于 + 运算，所以可以以 + 为断点，将序列分隔成若干个连续区间，每段区间内的数字做 | 和 + 运算结果相等。

要使任意两个数字做 | 和 + 运算结果相等，那它们在每一个二进制位上都不能有重复的1，即 a&b==0 。

划分方法可以通过dp求解。对于每一个位置 i​ ，向前找出所有使 [​j,i] 和等于或的的区间起点 ​j ，并做 dp[i]+=dp[j-1] 。可以注意到这里所有符合条件的 j 都是连续的，所以开一个数组 s 记录 dp 数组的前缀和。

在向前寻找 j 的过程中，使用变量 val 来记录当前区间的或。把 val 转成二进制来看的话会发现这里1的数量是单调递增且有上限的，只有遇到0才会不变。那么我们可以再开一个 pre 数组，通过标记最近非0数字的方式来把0跳过，有效的限制向前找 j 的次数。

博主的ac码略显抽象（）还是官方题解比较优雅，给跪了orz

#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl '\n'
#define PI3 array<long long, 3>
#define PI4 array<long long, 4>
#define lowbit(_) _ & (-_)
using namespace std;

const int N = 2e5 + 5;
const int mod = 998244353;

int n;
int arr[N];
int pre[N]; // 记录上一个非零位置
int dp[N];
int s[N]; // dp前缀和

void solve()
{
    cin >> n;
    int lst = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        pre[i] = lst;
        if (arr[i])
        {
            lst = i;
        }
        dp[i] = 0;
        s[i] = 0;
    }
    dp[0] = 1;
    dp[1] = 1;
    s[0] = 1;
    s[1] = 2;
    for (int i = 2; i <= n; i++)
    {
        int val = 0;
        int pos = i;
        while (pos > 0 && (val & arr[pos]) == 0)
        {
            val = (val | arr[pos]);
            pos = pre[pos];
        }
        /*这里的if判断纯粹是我的史山发力了，因为前缀和数组总会比dp数组多一位，但是dp数组本身下标就已经是从0开始，前缀和就会访问到s[-1]，只能特判一下了（逃跑）*/
        if (pos == i)
        {
            dp[i] = dp[i - 1];
        }
        else if (pos == 0)
        {
            dp[i] = s[i - 1];
        }
        else
        {
            dp[i] = (s[i - 1] - s[pos - 1] + mod) % mod;
        }
        s[i] = (s[i - 1] + dp[i]) % mod;
    }
    cout << dp[n] << endl;
}

signed main()
{
    ios;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}