题解 P3760 【[TJOI2017]异或和】

Nemlit

2019-09-24 14:36:09

Solution

对于这种异或类的题目,我们可以考虑从异或运算性质下手 我们记$sum[i] = \sum_{j = 1} ^ {i}a[j]$ 不难发现,如果我们对每一位分开考虑,若我们在求第x为的答案,记所有区间的连续的和有K个该位为1,那么跟据异或的运算法则,这一位对答案有贡献当且仅当K为奇数,且对答案的贡献为$K\ \%\ 2 * 2 ^ x$ 说得更具体点,我们要求的式子变成了: $$\sum_{k = 0} ^ {2 ^ k <= sum[n]}\ *\ ((\sum_{i = 1}^{n}\sum_{j = 1}^i(sum[i] - sum[j - 1]) >> k\ \&\ 1)\ \%\ 2)\ *\ 2 ^ k$$ 我们单独看里面的柿子: $$\sum_{i = 1}^{n}\sum_{j = 1}^i(sum[i] - sum[j - 1]) >> k\ \&\ 1$$ 其实问题已经转化为:给定$sum[i]$,求有多少个$j(j\in[0,\ i - 1])$,满足$sum[i] - sum[j]$的第K位为1 这个问题看上去很好处理,貌似是只要求出有多少个$sum[i]$与$sum[j]$的第K位不同即可,我们只需要记录$sum[i] >> k$的一个前缀和即可。 但是这道题目十分弟弟,因为异或的减法是可以进位的,所以我们并不能直接向刚刚那么算。 为了方便,我们定义$sum[i]_k$表示$sum[i]$的第K位,$sum[i]_{1\ -\ k}$表示sum的1~k位 ~~(原谅我'~'打不出来)~~ 的和 我们先进行分类讨论: 一、如果$sum[i]_k = 1$,那么能对答案产生贡献只有两种情况: $1.sum[j]_k = 0\ \&\&\ sum[j]_{1\ - \ k - 1} <= sum[i]_{1 - k - 1}$ $2.sum[j]_k = 1\ \&\&\ sum[j]_{1\ -\ k - 1} > sum[i]_{1\ -\ k - 1}$ 二、如果$sum[i]_k = 0$,那么能对答案产生贡献也只有两种情况: $1.sum[j]_k = 1\ \&\&\ sum[j]_{1\ - \ k - 1} <= sum[i]_{1 - k - 1}$ $2.sum[j]_k = 0\ \&\&\ sum[j]_{1\ -\ k - 1} > sum[i]_{1\ -\ k - 1}$ 那么现在问题来了,我们怎么判断进位呢? 注意到$\sum a[i]$不会太大 我们可以把$sum[i]_{1\ -\ k - 1}$扔到两颗权值树状数组内,一棵存0的,另一颗存1的 注意:树状数组的下标可能为0,所以我们要把所有下标+1 # $Code:$ ``` #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; #define il inline #define re register #define int long long il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define mem(k, p) memset(k, p, sizeof(k)) #define lb(x) (x)&(-(x)) #define maxn 1000005 int n, m, a[maxn], sum[maxn], ma, Ans, ans; struct Tree { int t[maxn]; il void add(int u, int v, int x) { while(u <= x) t[u] += v, u += lb(u); } il void Add(int u, int v, int x) { add(u + 1, v, x + 1); } il int query(int u) { int ans = 0; while(u) ans += t[u], u -= lb(u); return ans; } il int query(int l, int r) { return query(r + 1) - query(l); } }A, B;//A表示0的树状数组,B表示1的 signed main() { n = read(); rep(i, 1, n) a[i] = read(), sum[i] = sum[i - 1] + a[i], ma = max(ma, sum[i]); for(re int k = 0; (1 << k) <= ma; ++ k) { memset(A.t, 0, sizeof(A.t)), memset(B.t, 0, sizeof(B.t)), Ans = 0; int pax = (1 << k) - 1;//我们只考虑1~k位 rep(i, 0, n) { int temp = sum[i] & pax;//求出sum[i]_{1-k} //cout << k << ' ' << temp << endl; if((sum[i] >> k) & 1) { Ans += A.query(0, temp) + B.query(temp + 1, pax), B.Add(temp, 1, pax); } else { Ans += B.query(0, temp) + A.query(temp + 1, pax), A.Add(temp, 1, pax); } } //cout << Ans << ' ' << ans << endl; ans += (Ans % 2) * (1 << k); } printf("%lld", ans); return 0; } ```