招聘工作的网站有哪些,网页制作与网站建设完全学习手册,外贸seo软件,怎样免费建企业网站学到的几个知识点#xff1a;
1.拆位
对于整体上的异或操作可以转化为31个二进制位上的操作#xff0c;每一位再上 。
将一次操作拆为31次来方便操作。
2.
s[i]表示异或前缀和#xff0c;l~r间的异或和为s[r] ^ s[l - 1] ----
拆完位后这个公式还能再推出一个性…
学到的几个知识点
1.拆位
对于整体上的异或操作可以转化为31个二进制位上的操作每一位再×上 。
将一次操作拆为31次来方便操作。
2.
s[i]表示异或前缀和l~r间的异或和为s[r] ^ s[l - 1] ----
拆完位后这个公式还能再推出一个性质
只有s[r] ! s[l - 1]时这段区间的异或和才为1来以右端点为1还是0来讨论一下
对于每一位1只有左端点的左边一位为0时才有值才可以计算进去
对于每一位0只有左端点的左边一位为1时才有值才可以计算进去 对于一位上的1设当前为r,左边的为0的点为l,那要承的数就是(r - l),
如果这样的l有k个就是k * r - ()
这样就算出来了对于每一个数的每一位的贡献 时间复杂度 O(31 * n)
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;
typedef long double ld;const int N 300010, mod 998244353;int n;
int a[N];
ll f[40][2], cnt[40][2];int main()
{IOScin n;for(int i 1; i n; i ){cin a[i];a[i] ^ a[i - 1];//cout a[i] ;}//cout endl;ll ans 0;for(int i 0; i n; i ){for(int j 0; j 30; j ){if(a[i] j 1){ans (1ll j) % mod * (((cnt[j][0] * i - f[j][0]) % mod mod) % mod);ans % mod;f[j][1] (f[j][1] i) % mod;cnt[j][1] ;}else{ans (1ll j) % mod * (((cnt[j][1] * i - f[j][1]) % mod mod) % mod);ans % mod;f[j][0] (f[j][0] i) % mod;cnt[j][0] ;}}}cout ans;return 0;
}
