题意

给定长度为 $n$ 的非负整数数组 $a$，将其分割成若干连续非空段。设第 $i$ 段所有元素的按位或值为 $f_i$，要求：

求不同的分割方案数，对 $998244353$ 取模。

算法

设 $dp[i]$ 表示以 $i$ 结尾的合法分割方案数，$dp[0]=1$。
$prefix[i] = \sum_{j=0}^i dp[j] \pmod{MOD}$。

对于固定的右端点 $i$，随着左端点 $l$ 从 $i$ 向左移动，$OR(l,i)$ 最多变化 $30$ 次（因为二进制位只会从 $0$ 变 $1$ 一次）。
因此可以维护一个 $segments$ 列表，每个元素为 $(or_value, left_boundary)$，表示：

• 对于所有 $l \in [left\_boundary, next\_left-1]$，$OR(l,i) = or\_value$，
• 且 $or_value$ 从左到右严格递增。

转移方法：
对于 $segments$ 中的第 $j$ 段 $(v, L)$（其中 $L$ 是该段最小的 $l$），设 $R$ 为下一段的 $L-1$（最后一段 $R=i$）。
则 $j = l-1$ 的取值范围是 $[L-1, R-1]$。
对于这些 $j$，以 $j$ 结尾的上一段的 OR 值一定 $\le v$（因为 $j+1=l\ge L$ 且 OR 值随 $l$ 减小而增大），因此条件自动满足。
所以该段对 $dp[i]$ 的贡献为 $\displaystyle \sum_{j=L-1}^{R-1} dp[j] = prefix[R-1] - prefix[L-2]$。

将 $segments$ 从后向前遍历（即 OR 值从小到大），累加即可得到 $dp[i]$。

复杂度

• 每个 $i$ 的 $segments$ 长度 $O(\log \max a)$，
• 总时间复杂度 $O(n \log \max a)$，
• 空间复杂度 $O(n)$。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    vector<int> prefix(n + 1, 0);
    prefix[0] = 1;

    vector<pair<int, int>> segments; // (or_value, left_boundary)
    segments.reserve(30);

    for (int i = 1; i <= n; i++) {
        vector<pair<int, int>> new_segments;
        new_segments.emplace_back(a[i], i);
        for (auto [val, left] : segments) {
            int new_val = val | a[i];
            if (new_segments.back().first == new_val) {
                new_segments.back().second = left;
            } else {
                new_segments.emplace_back(new_val, left);
            }
        }
        segments = move(new_segments);

        int total = 0;
        for (int j = (int)segments.size() - 1; j >= 0; j--) {
            int left = (j == 0 ? 1 : segments[j - 1].second + 1);
            int right = segments[j].second;
            if (left > right) continue;
            int sum = (prefix[right - 1] - (left - 2 >= 0 ? prefix[left - 2] : 0) + MOD) % MOD;
            total = (total + sum) % MOD;
        }
        dp[i] = total;
        prefix[i] = (prefix[i - 1] + dp[i]) % MOD;
    }

    cout << dp[n] << "\n";

    return 0;
}

样例解释

样例1
输入：

3
1 2 3

输出：4
所有 $2^{2}=4$ 种分割均合法。

样例2
输入：

5
1000 1000 1000 1000 1000

输出：16
所有 $2^{4}=16$ 种分割均合法。

样例3
输入：

3
3 4 6

输出：3
合法分割：[3][4][6]，[3][4,6]，[3,4,6]。