[题解]QOJ #8520. Xor Partitions

QOJ #8520. Xor Partitions

给定非负整数序列 \(A_1,A_2,\dots,A_n\)，求所有非空划分的权值之和。一个划分的权值定义为每一段的异或和之积。

\(n\le 3\times 10^5,a\in[0,10^{18}]\)。

Sample in：

4
7 3 1 2

Sample out:

170

Solution

考虑朴素的 DP，设 \(f[i]\) 为前 \(i\) 个元素的答案，\(s_i\) 为异或前缀和数组，则有转移：

\[f[i]=\sum\limits_{j=0}^{i-1} f[j]\times (s_i\oplus s_j) \]

异或题的经典套路是考虑按位转移，上式可以写成：

\[f[i]=\sum\limits_{c=0}^{60}2^c\times \sum\limits_{j=0}^{i-1}f[j]\times\big[s_i的第c位\ne s_j的第c位\big] \]

于是我们可以预处理 \(d[c][i][0/1]\) 表示 \(s_1,\dots,s_i\) 中第 \(c\) 位为 \(0/1\) 对应的 \(f\) 值之和。然后上式可以写成：

\[f[i]=\sum\limits_{c=0}^{60} 2^c\times d[c][i-1][s_i的第c位\oplus 1] \]

时间复杂度 \(O(n\log V)\)。

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,P=1e9+7;
int n,a[N],f[N],d[60][2];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i],a[i]^=a[i-1];f[0]=1;for(int i=0;i<60;i++) d[i][0]=1;for(int i=1;i<=n;i++){int b=1;for(int j=0;j<60;j++) (f[i]+=b*d[j][(~a[i]>>j)&1])%=P,(b<<=1)%=P;for(int j=0;j<60;j++) (d[j][(a[i]>>j)&1]+=f[i])%=P;}cout<<f[n]<<"\n";return 0;
}