子数组+w+

1. 由于仅存在加法，即满足交换律和结合律，故可考虑累加单个元素的总贡献
2. 对当前元素g[i]，包含该元素的子数组数为(i + 1) * (n - i + 1)，则该元素的总贡献为(i + 1) * (n - i) * g[i]，枚举所有元素累加即可
   • i起始为1

void solve(){int n;cin >> n;ll res = 0;for(int i = 1; i <= n; i++){int x;cin >> x;res += 1ll * i * (n - i + 1) * x;}cout << res << '\n';
}

子数组^w^

类似考虑单个元素总贡献，当元素g[i]的出现次数(i + 1) * (n - i)为奇数时总贡献为g[i]，否则为0，计算异或和即可

void solve(){int n;cin >> n;ll res = 0;for(int i = 1; i <= n; i++){int x;cin >> x;x = (((n - i + 1) * i) & 1) * x;res ^= x;}cout << res << '\n';
}

子数组^w+

1. 考虑异或前缀和sx[i]，对任意子数组的异或和可表示为sx[r] ^ sx[l - 1]
2. 考虑二进制拆位，即枚举累加每个二进制位的贡献
3. 对当前位k，相当于在前缀和数组中选取两个元素，使sx[r] ^ sx[l - 1]中该位为1，即sx[r]和sx[l - 1]必须恰好一个1一个0，此时贡献为1 << k
4. 枚举统计前缀和数组中当前位下为1的元素个数cnt，则为0的个数为(n + 1 - cnt)，故存在贡献的子数组的总贡献为cnt * (n + 1 - cnt) * (1 << k)

void solve(){int n;cin >> n;ve<int> sx(n + 1);for(int i = 1; i <= n; i++){cin >> sx[i];sx[i] ^= sx[i - 1];}ll res = 0;for(int k = 0; k < 22; k++){int cnt = 0;for(int i = 0; i <= n; i++) cnt += sx[i] >> k & 1;res += 1ll * cnt * (n + 1 - cnt) * (1 << k);}cout << res << '\n';
}

子数组+w^

1. 考虑前缀和$s[i]$，对任意子数组和可表示为$s[r]-s[l-1]$

2. 考虑二进制拆位，即枚举累加每个二进制位的贡献

3. 对当前$k$位，需要获取所有子数组和该位为1的数量，若为奇数则贡献为$2^k$，否则为0

4. 问题转换为求指定位下所有子数组和该位为1的数量

5. 只考虑低位到$k$位，令所有$s[i]$对$2^{k+1}$取模，从而将$s[r]-s[l-1]$的结果及其$s[r]$和$s[l-1]$压缩到一定连续范围内

6. 当$k=2$时，$s[r]-s[l-1]$产生$k$位为1的结果范围为[100, 111]，考虑减法操作中高位的影响，如1000 - 1 = 111的结果满足条件，故当$s[r]\ge 2^{k+1}$时，在$k+1$位补1，此时结果范围为$[100,111]\cup [1100,1111]$，则$s[l-1]$的范围为

   $[s[r]-111,s[r]-100]\cup [s[r]-1111,s[r]-1100]$

7. 枚举所有$s[r]$，对当前$s[r]$获取$[1,r-1]$中在区间内的$s[l-1]$的个数进行累加，最后得到当前位下所有子数组和该位为1的数量

8. 由于$[1,r-1]$是动态区间，故使用树状数组维护即可

const int N = 2e7 + 10;ve<int> tr(N);int lowbit(int x){return x & -x;
}void add(int idx, int val){idx++;for(int i = idx; i < N; i += lowbit(i)) tr[i] += val;
}int sum(int x){x++;int ans = 0;while(x > 0){ans += tr[x];x -= lowbit(x);}return ans;
}void solve(){int n;cin >> n;ve<int> s(n + 1);for(int i = 1; i <= n; i++){cin >> s[i];s[i] += s[i - 1];}int res = 0;for(int k = 0; (1 << k) <= s[n]; k++){add(0, 1);int cnt = 0;for(int i = 1; i <= n; i++){int ts = s[i] & ((1 << (k + 1)) - 1);if(s[i] >= 1 << (k + 1)) ts |= 1 << (k + 1);int r = ts - (1 << k), l = ts - (1 << (k + 1)) + 1;cnt += sum(r) - sum(l - 1);l -= 1 << (k + 1), r -= 1 << (k + 1);cnt += sum(r) - sum(l - 1);add(s[i] & ((1 << (k + 1)) - 1), 1);}if(cnt & 1) res |= 1 << k;fill(all(tr), 0);}cout << res << '\n';
}

子序列+w+

1. 由于仅存在加法，即满足交换律和结合律，故可考虑累加单个元素的总贡献
2. 对于元素g[i]，包含该元素的子序列总数为$2^{n-1}$，即总贡献为$2^{n-1}\ast g[i]$
3. 所有元素总贡献为$2^{n-1}\ast sum$

void solve(){int n;cin >> n;ll res = 0;for(int i = 0; i < n; i++){int x;cin >> x;res += x;}for(int i = 0; i < n - 1; i++) res = 2 * res % mod;cout << res << '\n';
}

子序列^w^

1. 类似可考虑累加异或单个元素的总贡献
2. 当且仅当n = 1存在贡献g[0]，否则$2^{n-1}$为偶数，总贡献为0

void solve(){int n;cin >> n;ve<int> g(n);for(int i = 0; i < n; i++) cin >> g[i];if(n == 1) cout << g[0] << '\n';else cout << 0 << '\n';
}

子序列^w+

1. 考虑二进制拆位，即枚举累加每个二进制位的贡献
2. 对于当前位k，若所有元素都为0，则总贡献为0
3. 若存在元素为1，设数量为c，可用数学归纳法证明从c个数中选偶数个数和奇数个数的方案数都为$2^{c-1}$，再算上0可得异或和为0和为1的子序列数都为$2^{n-1}$
4. 则此时该位总贡献为$2^{n-1}\ast 2^k$

void solve(){int n;cin >> n;ve<int> g(n);for(int i = 0; i < n; i++) cin >> g[i];ll res = 0;for(int k = 0; k < 30; k++){bool ok = false;for(int i = 0; i < n; i++){if(g[i] >> k & 1){ok = true;break;}}if(ok) res += 1 << k;}for(int i = 0; i < n - 1; i++) res = 2 * res % mod;cout << res << '\n';
}

子序列+w^

1. 考虑枚举累加每个子序列和的可能值的贡献
2. 对当前序列数和sum，得到该和的方案数为奇数时贡献为sum，否则为0
3. 考虑使用01背包推导序列数和的方案数的奇偶性

void solve(){int n;cin >> n;int m = 1 << 16;ve<int> dp(m + 1);dp[0] = 1;for(int i = 0; i < n; i++){int v;cin >> v;for(int j = m; j >= v; j--){dp[j] = dp[j] ^ dp[j - v];}}int res = 0;for(int i = 0; i <= m; i++){if(dp[i]){res ^= i;}}cout << res << '\n';
}