H题 | Blackboard

本题解适合刚入门算法的同学，会比较注重细节（啰嗦），已经有算法基础的同学可以直接看官方题解和各位大佬的题解。

解题思路：

首先对于任意两个非负整数 $a$ 和 $b$ ，如果它们二进制形式的某位不同时为 $1$ ，则对于这一位来说， $+$ 和 $|$ 操作是等价的。

0+0 == 0|0 == 0

0+1 == 0|1 == 1

1+0 == 1|0 == 1

否则， $a | b$ 的结果一定小于 $a+b$ ，因为相对于 $加运算$ 来说， $按位或$ 舍弃了所有的进位，导致结果偏小。

1 | 1 == 01

1+1 == 10

因此我们得出结论：对于连续求和操作 $a_1+a_2+\cdots+a_n$ ，将任意位置的 $+$ 替换为 $|$ 只会导致结果要么变小，要么不变（不可能导致结果变大）。

为了保证替换前后的公式结果不变，必须满足每个子式 $a|b$ 的结果都等于 $a+b$ ，否则将会导致结果不可逆地变小。

题目规定 $|$ 运算符的优先级大于 $+$ ，所以对于任意一种可能的替换方案（不一定合法），我们都可以把 $+$ 看作分隔符，将数列分割成若干个区间，区间内的数做连续 $|$ 运算。例如：0 | 1 | 3 + 5 | 7 + 9 可分割成 {0|1|3} + {5|7} + {9} 。

对于一个连续 $|$ 运算，当参与运算的任意两个数都满足所有位都不同时为 $1$ 时，该连续 $|$ 运算与连续求和操作等价。也就是说，如果某个数的某一个二进制位为 $1$ ，那么其他所有的数对应二进制位都必须为 $0$ 。

1000 =======非=> 1001
0100 =======法=> 1100
0010 <=合======= 0010
0001 <=法======= 0000

综上，对于任意一种合法的替换方案，形式一定为若干个合法的连续 $|$ 运算相加。

对于题目给定的连续求和操作 $a_1+a_2+\cdots+a_n$ ，这里取一个下标 $i(1 \leq i \leq n)$ ，假设我们已经求出了子区间 $[1,i]$ 的所有合法方案数 $ans_i$ ，我们只需要把 $i$ 向后推广到 $n$ ，就可以得到本题答案 $ans_n$ （ $ans_n$ 表示区间 $[1,n]$ 的所有合法方案数，即本题所求）。

这是一种 $dp$ 的思想（动态规划），我们用 $dp[i]$ 表示 $ans_i$ ，而现在要做的是求解 $dp[i+1]$ （即转移方程）。

我们在区间 $[1,i]$ 后面追加一个 $a_{i+1}$ ，这个追加的数导致总方案数发生了变化，可以分成三类讨论：

$a_i$ 和 $a_{i+1}$ 存在某些位同时为 $1$ 。这时 $a_i$ 必须单独划分到一个连续 $|$ 运算区间，也就是说 $a_i$ 和 $a_{i+1}$ 中间的运算符只能是 $+$ ，两者绝不能做 $|$ 运算。因此 $dp[i+1]=dp[i]$ （ $a_{i+1}$ 的加入不会产生新的方案数）。
$a_i$ 和 $a_{i+1}$ 的所有位都不同时为 $1$ ，但是存在一个最大的下标 $L(1 \leq L \lt i)$ ，满足 $a_L$ 和 $a_{i+1}$ 存在某些位同时为 $1$ 。因此在区间 $[L+1,i+1]$ 内的任意两个数， $+$ 和 $|$ 操作是等价的，所以 $a_{i+1}$ 可以并入 $[L+1,i+1]$ 所属的连续 $|$ 运算区间。此时新区间的总合法方案数为： $dp[i+1] = \sum_{j=L}^{i} dp[j]$ 。

看到这一坨公式别害怕，我给你理一理。在区间 $[1,a_{i+1}]$ 内的数字，两两之间都有一个运算符，且对于任意一种合法的替换方案，我们从右往左，找到第一个 $+$ 运算符。我们可以确定：这个运算符右边只能出现一个连续的 $|$ 运算区间，左边则是若干个连续的 $|$ 运算区间相加的形式。形如：(...)+(x|x|...|x|x) 。此时由于这个 $+$ 右侧的运算符都是确定的，不确定的运算符只存在于这个 $+$ 的左侧。换句话说，正因为存在左侧这些不确定的运算符，才导致存在不止一种替换方案。而 $dp[k]$ 表示区间 $[1,k]$ 的所有合法方案数，只要你大于 $k$ 的部分是一个 $+$ 加上若干个 $|$ ，那么你右侧就不存在不确定符号，也就是只有 $1$ 种方案。因此，这样的区间的合法方案数是左边方案数乘右边方案数，即 $dp[k] \times 1=dp[k]$ 。由于第 $i+1$ 个数和第 $L$ 个数不能存在于同一个连续 $|$ 运算区间内，因此两个数字中间至少存在 $1$ 个 $+$ 。也正因如此，我们枚举 $[L,i]$ 的所有数字，依次令该数字右侧的符号作为整个多项式最右侧的 $+$ ，即可覆盖区间 $[1,i+1]$ 内的所有方案，不重复、不遗漏。因此上述递推公式，本质是枚举所有可能的最右侧 $+$ 的位置并求和所有对应方案数。
$a_i$ 和 $a_{i+1}$ 的所有位都不同时为 $1$ ，且不存在下标 $L(1 \leq L \lt i)$ ，满足 $a_L$ 和 $a_{i+1}$ 存在某些位同时为 $1$ 。此时只有两种可能：要么 $a_{i+1}=0$ ，此时 $L$ 取上一次递推的 $L$ 值即可；要么 $a_{i+1}$ 和前面所有出现的数都可以进行 $|$ 运算，取 $L=1$ 即可。

聪明的你又发现了：第 $1$ 种情况是第 $2$ 种情况的子情况，相当于 $L=i$ ，遂将 $1、2$ 条合并。

聪明的你又又发现了：可以开一个长度为 $31$ 的 $lst[]$ 数组，记录每个二进制位最后一次 $1$ 是在哪个位置的数字上出现的，可以 $O(31)$ 求解 $L$ ，不赖。

聪明的你又又又发现了：在从 $1$ 开始往 $n$ 递推时， $L$ 是单调不减的，因此第 $3$ 条中甚至不需要考虑如何取上一个值，因为当 $a_{i+1}=0$ 时， $L$ 自然不会被更新，本身就是上一个值了。

然鹅，聪明的你并没有就此罢休，叕叕叕发现了： $dp[i+1] = \sum_{j=L}^{i} dp[j]$ 这个递推方程，右侧不就是连续值求和嘛，于是你想到了用前缀和来 $O(1)$ 化区间求和的复杂度。优雅，实在太优雅了。

示例代码：

代码中的递推方程是递推的是 $dp[i]$ 而不是 $dp[i+1]$ ，导致一个小问题：

存输入数据的时候以 $1$ 为第一个元素的下标，但是 $dp$ 数组会往边界左侧访问一位，前缀和数组 $sum$ 又会往 $dp$ 数组的边界左侧访问一位，导致 $sum$ 数组可能越界。我的解法是三目运算符手动判边界。当然，你也可以把sum数组开成 unordered_map<int,int> 的形状（或者你想要的任何形状），瞬间解决所有数组越界问题~欸欸，我可没说建议你这么干哦 :)

const int mod = 998244353;
void solve() {
	int n, L = 0, lst[31] = {0};
	cin >> n;
	vector<int> dp(n + 1), sum(n + 1);
	dp[0] = sum[0] = 1; // init

	for (int i = 1, num; i <= n; ++i) {
		cin >> num;
		int pos = 0;
		while (num) {  // move L & update lst[]
			if (num & 1) L = max(L, lst[pos]), lst[pos] = i;
			num >>= 1, ++pos;
		}

		dp[i] = (sum[i - 1] - (L ? sum[L - 1] : 0) + mod) % mod;  // update dp[]
		sum[i] = (sum[i - 1] + dp[i]) % mod;  // update sum[]
	}
	cout << dp[n] << '\n';
}

蒟蒻一枚，质量不高，请各位大佬多指教~

题解 | #Blackboard#

H题 | Blackboard

解题思路：

示例代码：