XORSPRT - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Ayush Singh
Tester : Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

XOR, Observations, Dynamic Programming

PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N. Find the number of ways to split it into one or more non-empty contiguous subsequences B_1, B_2, \ldots, B_k such that the following condition is satisfied: for each i (1 \le i \le k), the XOR of all elements in B_i is divisible by 2^{i-1}.

Since this number can be enormous, compute it modulo 1,000,000,007 (10^9 + 7).

EXPLANATION:

Suppose that we split an array A into non-empty contiguous subsequences B_1, B_2, \ldots, B_k such that all the conditions are satisfied. Let’s try to see what are the possible ending indices for the i^{th} sequence.

Claim: An i^{th} sequence can end at index j, only and only if the XOR of the prefix array A[1,j] is equal to the XOR of the whole array in the smallest i bits.

Proof:

Suppose we are trying to build the sequence B_1, then it is quite easy to observe that all the sequences that will be created after B_1 should be divisible by 2 which leads us to further observation that all such sequences will have their last bit unset. Now according to the property of XOR:

0 \oplus X = X

Since all the sequences after B_1 have their last bit unset, which means that the xor of the last bit is completely dependent on the sequence B_1. Hence we can say that:

XOR(A) = XOR(B1) \hspace{0.5cm} in \hspace{0.1cm} last \hspace{0.1cm} bit

Hence B_1 will end at such indices where XOR of the whole array is equal to the XOR of the prefix array on the last bit.

Let’s try to build the i_{th} sequence in a similar fashion, then all the sequences that will be created after B_i will be divisible by 2^i, which means that all such sequences will have their last i bits unset.

Therefore, the XOR of the last i bits will depend on the XOR of the sequences B_1,B_2,\dots,B_i.

That means the i^{th} sequence will end at index j only and only if the XOR of the prefix array A[1,j] is equal to the XOR of the whole array in the smallest i bits.

Now, suppose we had already created j sequences and we are at index i, then we have two choices:

  • Include i^{th} index at the j^{th} sequence, or
  • Start the new sequence which ends at index i

This gives us hint towards Dynamic Programming. Let us define our DP:

DP(i, j) gives us the number of ways among the first i elements in the first j sequences. And the transition will be as:

  • Include (i+1)^{th} index at the j^{th} sequence

\hspace{1cm} DP(i+1,j) = DP(i,j)

  • Start the new sequence which ends at index (i+1)

\hspace{1cm} This transition will only be done when. XOR of the first i elements matches with the XOR of an array in the smallest j+1 bits

DP(i+1,j+1) += DP(i,j)

Since there is no bound in the value of K hence K can be up to N which is quite huge. Observe that after the most significant bit of the XOR(A), the bits will always be matching, and hence the condition when we can do our second transition is just that the XOR of some prefix is equal to the XOR of the whole array. Hence we just need to be deal with log(max(A_i)) state.

TIME COMPLEXITY:

O(N*log(max(A_i))) per test case

SOLUTIONS:

Author
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc=new Scanner(System.in);
	    int t=sc.nextInt();
	    long z=0;
	    while(--t>=0){
	        int n=sc.nextInt();
	        long arr[]=new long[n];
	        long dp[][]=new long[105][n+5];
	        long pre[]=new long[n+5];
	        for(int i=0;i<n;i++){
	        arr[i]=sc.nextLong();
	        dp[1][i]=1;
	        }
	        long m=1000000007;
	        long c=1;
	        long ans=1,x=0;
	        for(int i=n-1;i>=0;i--){
	            x=x^arr[i];
	            if(x==0){
	                pre[i]=c;
	                c=(c*2)%m;
	            }
	        }
	        for(int i=2;i<=Math.min(60,n);i++){
	            HashMap<Long,Integer> map=new HashMap<>();
	            long xor=0;
	            map.put(0l,i-1);
	            for(int j=i;j<=n;j++){
	                xor=xor^(((1l<<(long)(i-1))-1l)&arr[j-1]);
	                if(map.containsKey(xor)){
	                    int l=map.get(xor);
	                    dp[i][j]=(dp[i][l]+dp[i-1][l])%m;
	                    if(i==60)
	                    ans=(ans+dp[i][j]%m*pre[j]%m)%m;
	                }
	                map.put(xor,j);
	            }
	            ans=(ans+dp[i][n])%m;
	        }
	        System.out.println(ans);
	    }
	}
}
Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<int m>
struct mod {
    long long x;
    mod() : x(0) {}
    mod(long long xx) : x(xx) {
        if(abs(x) >= m) x %= m;
        if(x < 0) x += m;
    }
    mod operator+(const mod &a) const {
        mod n;
        n.x = x + a.x;
        if(n.x >= m) n.x -= m;
        return n;
    }
    mod operator-(const mod &a) const {
        mod n;
        n.x = x - a.x;
        if(n.x < 0) n.x += m;
        return n;
    }
    mod operator*(const mod &a) const {
        return x * a.x;
    }
    mod operator+=(const mod &a) {
        x += a.x;
        if(x >= m) x -= m;
        return *this;
    }
    mod operator-=(const mod &a) {
        x -= a.x;
        if(x < 0) x += m;
        return *this;
    }
    mod operator*=(const mod &a) {
        x = (x * a.x) % m;
        return *this;
    }
    mod pow(long long b) const {
        mod ans = 1;
        mod a = *this;
        while(b > 0) {
            if(b & 1) ans *= a;
            a *= a;
            b /= 2;
        }
        return ans;
    }
    mod inv() const {
        return pow(m - 2);
    }
    mod operator/(const mod &a) const {
        return (*this) * a.inv();
    }
    mod operator/=(const mod &a) {
        return (*this) *= a.inv();
    }
    bool operator==(const mod &o) const {
        return x == o.x;
    }
    bool operator!=(const mod &o) const {
        return x != o.x;
    }
    long long operator()() const {
        return x;
    }
};

template<int m>
istream &operator>>(istream &is, mod<m> &n) {
    long long x;
    is >> x;
    n = x;
    return is;
}

template<int m>
ostream &operator<<(ostream &os, const mod<m> &n) {
    return os << n();
}

const int M = 1e9 + 7;
using base = mod<M>;

// problem reduces to:
// number of subsequences [c[0], ..., c[k-1]] such that c[i] >= i
// O(n^2) dp seems possible

// all c[i] are either < 60 or INF
// dp[i][val] = num sequences among first i elements, ending with val (number < 60 or INF)
// dp[i][val] += dp[i - 1][val]
// if a[i] >= val, dp[i][val] += dp[i - 1][val - 1]

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    rep(i, 1, n + 1) cin >> a[i];
    for(int i = n - 1; i >= 1; i--) a[i] ^= a[i + 1];
    rep(i, 1, n + 1) {
        a[i] &= -a[i];
        if(a[i] == 0) {
            a[i] = 60;
        }else {
            int l = 0;
            while((1LL << l) < a[i]) l++;
            a[i] = l;
        }
    }
    vector<base> dp0(61, 0), dp1(61, 0);
    dp0[0] = 1;
    rep(i, 2, n + 1) {
        fill(all(dp1), 0);
        rep(val, 0, 61) {
            dp1[val] = dp0[val];
            if(a[i] >= val && val > 0) {
                dp1[val] += dp0[val - 1] + (val == 60 ? dp0[val] : 0);
            }
        }
        dp0.swap(dp1);
    }
    cout << accumulate(all(dp0), base(0)) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
2 Likes