CS Academy #14 - Subarrays Xor Sum
問題
問題概要
長さの数列が与えられる。長さが以上以下の部分列に対して、xorを取った値の和をで割った余りを答えよ。
アイデア
ビットごとに独立に考えていく。今、ビットを固定する(とする)と、もとの数列は01の数列として見なすことができるようになる((a[i]>>b)&1
)。
こうなると、このビット列の中の部分列の中で、xorの値が1になる個数を数えるという問題に答えれば良いということになる。
さて、一般的な数列の部分和と同じように数列の部分に対してxorをとったものも同様に計算できる。からの部分和が欲しければ、prefix sum()を用意しておいてそのとに注目すれば良い。
次に、この部分列の長さに対する制約(以上以下)をどのように対処するかを考える。 個数を数えるにあたって、部分列の区間の右を固定して考える。すると、この部分列の制約から区間の左のindexはからということになる。つまり、の値に注目して、区間]のpreに対して0と1の値が何個ずつあるかを保持しながら、を増やしていくことで、この更新の処理を尺取的にできるので1つのビットに対してで計算ができ、十分に間に合う。
実装(C++)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second const ll mod = 1e9+7; int main() { int n,A,B; cin >>n >>A >>B; vector<int> a(n); rep(i,n) cin >>a[i]; ll ans = 0; rep(b,30) { vector<int> x(n); rep(i,n) x[i] = (a[i]>>b&1); vector<int> pre(n+1); rep(i,n) pre[i+1] = pre[i]^x[i]; int l=-B, r=-A; ll ct[2]={}; rep(i,n) { if(-1<=r && r<n) ++ct[pre[r+1]]; ++r; (ans += ct[!pre[i+1]]*(1<<b))%=mod;; if(-1<=l && l<n) --ct[pre[l+1]]; ++l; } } cout << ans << endl; return 0; }