# Problem Link:

# Difficulty:

Easy

# Pre-requisites:

Binary Indexed Tree, Ad-hoc

# Problem:

You are given a sequence of **N** positive integers in the range 0 to 2^{M}-1, say **A[0], A[1], …, A[N-1]**. In how many ways can you partition this sequence into disjoint **contiguous** subsequences, such that the sum of numbers in each contiguous subsequence modulo 2^{M} in each partition is in the range 0 to 2^{M-1}-1.

# Explanation:

The first thing to note is that the sum of any contiguous subsequence of the sequence A, can be got very easily if we maintain a prefix sum array. Let B[i] = A[0] + A[1] + … A[i]. Now, the sum of numbers from A[i] to A[j], is just B[j] - B[i-1], (with the convention that B[-1] = 0). Similarly, the values of the sums modulo 2^{M} will be (B[j] - B[i-1]) modulo 2^{M}.

We now ask, given the sequence of integers A[0], A[1], …, A[N-1], how many ways are there to partition it? In particular, we ask, what will the last partition be? Note that A[j], A[j+1], …, A[N-1] is a valid partition iff (B[N-1] - B[j-1]) % 2^{M} < 2^{M-1}. Given that that is a valid partition, we ask how many ways are there to partition A[0], A[1], …, A[j-1].

That brings us to the following dynamic program: let f(i) = number of ways of partitioning A[0], A[1], …, A[i] in the required manner. Now, again we ask what is a valid last partition. Any prefix sum in the range B[i]-2^{M-1}+1 to B[i] (modulo 2^{M}, with prefix sums wrapping around) is valid. Once we have such a valid last partition, f(i) = sum of answers of previous partitions.

Thus, let us associate f(i) with B[i]. If we ask at each point of time, let dp[j] = number of ways of partitioning the currently seen array such that the prefix sum to this point is j, then, we just need to make the update dp[B[i]] += sum (j from B[i] - 2^{M-1} + 1 to B[i]) dp[j]. Thus, this is a sum over a contiguous portion of a “dp-array”, and can be efficiently implemented using a Binary Indexed Tree (BIT).

Thus, the overall algorithm’s pseudocode is as follows:

```
Keep a BIT, over an initial array of size 2^M, whose 0'th entry is 1, others are 0.
for i from 0 to N-1
pref[i] = pref[i-1] + A[i]
if(pref[i] >= 2^(M-1)) //don't wrap around
res = BIT.query(pref[i]-2^(M-1)+1, pref[i])
else //wrap around
res = BIT.query(0, pref[i]) + BIT.query(pref[i]+2^(M-1)+1, 2^M-1)
BIT.update(pref[i], res)
output answer = res // result at final position = pref[N-1].
```

## Related Problem:

Problem “Generic Cow Protests” USACO Feb 11 Gold Contest

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here