给定一个长度为 n 的序列 a[1..n]，定义函数 f(b[1..m]) 的值为在 [0,m-1] 内满足如下条件的 i 的数目：
b 中前 i 个数异或起来的值小于 b 中前 i +1个数异或起来的值。
对于 a[1..n] 的每个子序列 b[1..m]，求f(b[1..m])之和。
第一行一个正整数 n。
接下来一共有 n 行。第 i+1 行包含一个非负整数 a[i]。
1 ≤ n ≤ 105
0 ≤ a[i] < 231
输出答案对 998244353 取模后的值。
样例输入 2 1 2 样例输出 4 计算A^B，假设B的最高位是第j位，如果要使A变小，那么A的第j位必须是1，否则A一定会变大 用c[j][0/1]维护前i个数里第j位是0/1的子序列的个数 对于第i个数，如果最高位是j，则对答案的贡献为c[j][0]*2^(n-i)#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MX = 1e5 + 5; const LL mod = 998244353; /***** 计算A^B，假设B的最高位是第j位，如果要使A变小，那么A的第j位必须是1，否则A一定会变大 用c[j][0/1]维护前i个数里第j位是0/1的子序列的个数 对于第i个数，如果最高位是j，则对答案的贡献为c[j][0]*2^(n-i) *****/ LL a[MX],f[MX],c[32][2]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); f[0]=1; for(int i=1;i<=n;i++) f[i]=f[i-1]*2%mod; LL ans=0; for(int i=0;i<=31;i++) c[i][0]=1; for(int i=1;i<=n;i++){ for(int j=31;j>=0;j--){ if(a[i]>>j&1){ ans=(ans+c[j][0]*f[n-i])%mod; break; } } for(int j=31;j>=0;j--){ if(a[i]>>j&1){ int x=c[j][0],y=c[j][1]; c[j][0]=(x+y)%mod; c[j][1]=(x+y)%mod; } else{ c[j][0]=c[j][0]*2%mod; c[j][1]=c[j][1]*2%mod; } } } printf("%lld\n",ans); return 0; }
