# 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* = A[0] + A[1] + … A*. Now, the sum of numbers from A* 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* in the required manner. Now, again we ask what is a valid last partition. Any prefix sum in the range B*-2^{M-1}+1 to B* (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*. 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*] += sum (j from B* - 2^{M-1} + 1 to B*) 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* = pref[i-1] + A*

if(pref* >= 2^(M-1)) //don’t wrap around

res = BIT.query(pref*-2^(M-1)+1, pref*)

else //wrap around

res = BIT.query(0, pref*) + BIT.query(pref*+2^(M-1)+1, 2^M-1)

BIT.update(pref*, 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