描述
题解
最开始我有一个误区,就是以为子序列必须连续,后来发现不连续也是可以的(尽管就算知道这一点,我也做不出来)……
然后呢,根据题目中的条件我们可以知道,我们必须求出来对于每一个元素他前边有多少个合法的子序列再异或他后结果变大,这时,我们应该考虑,如何才能保证他变大呢?
这个部分虽然不好想,但是很容易理解的是,当这个元素的最高二进制位对应前边序列的异或值的二进制位为 0 时,那么异或起来肯定是会变大的,举个例子,假如说前边的序列的二进制值为
说到这里,剩下的应该就没有什么难点了,我们需要维护一个
说到这里,忽然感觉和单调栈的几道题十分相似,比如说 51Nod 上的那几道,《数组的宽度》之类的题,都是将子连续序列的价值之和转化为了每个元素的贡献之和了,当然这个题是子序列不是子连续序列,所以呢,不能用单调栈而是用
代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const int MAX_DIG = 31;
const int MOD = 998244353;
int n, ans = 0;
int a[MAXN];
int power[MAXN];
int c[MAX_DIG + 3][2];
void init()
{
power[0] = 1;
for (int i = 1; i <= n; i++)
{
power[i] = (ll)power[i - 1] * 2 % MOD;
}
}
int main()
{
scanf("%d", &n);
init();
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i <= MAX_DIG; i++)
{
c[i][0] = 1;
}
for (int i = 1, j; i <= n; i++)
{
for (j = MAX_DIG; j >= 0; j--)
{
if (a[i] & (1 << j))
{
break;
}
}
ans += (ll)c[j][0] * power[n - i] % MOD;
ans %= MOD;
for (j = 0; j <= MAX_DIG; j++)
{
int t0 = c[j][0];
int t1 = c[j][1];
if (a[i] & (1 << j))
{
c[j][0] = (t0 + t1) % MOD; // 选 a[i] 的有 t1 种 不选 a[i] 的有 t0 种
c[j][1] = (t0 + t1) % MOD; // 选 a[i] 的有 t0 种 不选 a[i] 的有 t1 种
}
else
{
c[j][0] = t0 * 2 % MOD; // 选或不选 a[i] 都是 t0 种
c[j][1] = t1 * 2 % MOD; // 选或不选 a[i] 都是 t1 种
}
}
}
printf("%d\n", ans);
return 0;
}