Problem Link:
Difficulty:
Medium
Pre-requisites:
Combinatorics
Problem:
You are given a line of bushes from 1 to N, each having C[i] berries. A query (L, R) scenario is as follows. K tourists visit contiguous ranges of bushes, collecting all their berries (which then regrow instantly). They then want to divide the total berries among themselves evenly (no two people should have their number of berries differing by more than 1). In how many ways can this division be done? Two divisions are considered different if there is a single berry that goes to different people in the two divisions, and all berries among all bushes are distinct. You may also have to update the C[] array in between execution.
Quick Explanation:
The solution to a query only depends on the total number of berries B, and the number of people K. Further, exactly (B % K) people will get floor(B/K) + 1 berries, and the remaining will get exactly floor(B/K). This is seen by arranging berries in a ceil(B/K) x K grid, and giving columns of berries to each person.
Now, dividing the berries among the people can be thought of as first choosing who all to give floor(B/K) berries, and then using formula for multinomial coefficient to divide B items into K sets where set i has size Xi. This gives K choose (B K) for the first term, and B! / product(Xi!) for the second term. Notice that Xi = floor(B/K) + 1 for (B K) such i, and is floor(B/K) for the remaining.
Final answer:
Given, L, R,
compute B = C[L] + C[L+1] + … + C[R], K = R - L + 1, x = floor(B/K), i = B % K.
f(B, K) = K!/(i!(K-i)!) * B! / ((x+1)!i * (x!K - i))
Also, we need to be able to compute sum of a range of array C[] as well as update elements of C[] quickly. This can be done using either a segment tree or a Fenwick tree etc. giving an overall complexity of O(logN) per query.
A few things to note:
Since the answer is large, we should take our answer modulo the number 3046201, which is prime. Further, the maximum value of any factorial we use is less than this, so we can precompute all factorials easily. We would also need to be able to find inverses and powers efficiently. These both can be done with logarithmic exponentiation in O(logP) time.
Explanation:
As mentioned in the Quick Explanation, the first thing to note is, in order to answer a query, we just need to know how many berries are there in total, and how many people we need to distribute these berries to. Once we know these: B = number of berries, K = number of people, let us call denote our answer as f(B, K).
The next natural thing to ask is, how many berries should go to each person?
Since we ensure that two people do not get a number of berries differing by more than one, we can say that everyone gets either “x” or “x+1” berries for some value “x”. Lets say “i” people get value “x+1”. Then, we have the constraint
“i * (x+1) + (K-i) * x = B”,
which gives us that
“K * x = B - i”.
Note that 0 <= i <= K (in fact, i = K can be considered as a degenerate case of i=0, and x=x+1, so we just take i < K). This gives us immediately that x = floor(B/K) and i = B % K.
Now, let us fix some set of people to get floor(B/K) (=“x”), and the others get floor(B/K)+1. For these people fixed, we count the number of ways. Then we sum over all such ways of dividing the sets.
Let us consider the general case of dividing a set of size N into subsets of size x1, x2, x3, …, xK, where sum(xi) = N. The first set can be chosen in Comb(N, x1) ways. The next set in Comb(N-x1, x2), … the i’th in Comb(N-x1-x2…-x(i-1), xi) ways. If you write Comb(n, r) as n!/(r!(n-r)!), and expand out the above, you will get a telescoped product that becomes N!/(x1! * x2! * x3! * … * xK!).
We know however, that exactly (B % K) of the above have value xi = x + 1, and that the remaining have value xi = x (recall, x = floor(B/K)). This means, our actual number of ways, after we have fixed our set of people who get (x+1) berries, the number of ways of dividing the berries is
B! / (((x+1)!)i * (x!K - i)), where i = B % K.
The number of ways of choosing a set of people to get (x+1) berries is Comb(K, i) = K!/(i! * (K - i)!)
Thus, given the values B and K, f(B, K) =
K!/(i! * (K - i)!) * B! / (((x+1)!)^i * (x!^(K - i)))
In the above formula, notice that we have a lot of Factorials, a few divisions, and a few powers. If we precompute values of factorials modulo P, as well as write a logarithmic exponentiation function, then division is also taken care of because a^-1 = a ^ (P-2) modulo P.
The final caveat is that we need to find sums of ranges and update individual elements efficiently. This however can be done in O(logN) time using either a segment tree or a Binary Indexed Tree.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here