裏紙

ほぼ競プロ、たまに日記

CS Academy #14 - Subarrays Xor Sum

問題

CS Academy

問題概要

長さNの数列aが与えられる。長さがA以上B以下の部分列に対して、xorを取った値の和を10^9+7で割った余りを答えよ。

  •  1 \le A \le B \le N \le 10^5
  •  0 \le a_i \le 10^9

イデア

ビットごとに独立に考えていく。今、ビットを固定する(bとする)と、もとの数列aは01の数列として見なすことができるようになる((a[i]>>b)&1)。

こうなると、このビット列の中の部分列の中で、xorの値が1になる個数を数えるという問題に答えれば良いということになる。

さて、一般的な数列の部分和と同じように数列の部分に対してxorをとったものも同様に計算できる。iからjの部分和が欲しければ、prefix sum(pre)を用意しておいてそのpre_jpre_{i-1}に注目すれば良い。

次に、この部分列の長さに対する制約(A以上B以下)をどのように対処するかを考える。 個数を数えるにあたって、部分列の区間の右jを固定して考える。すると、この部分列の制約から区間の左のindexはj-B+1からj-A+1ということになる。つまり、pre_jの値に注目して、区間 [j-B, j-A]のpreに対して0と1の値が何個ずつあるかを保持しながら、jを増やしていくことで、この更新の処理を尺取的にできるので1つのビットに対してO(N)で計算ができ、十分に間に合う。

実装(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;
}