So i have been solving a PnC question and now am stumbled upon a problem.
Statement: Suppose we have an array of (n+m) size. Each element of array can be filled with any number from 0 to K. Now a partition is created in the array so that array is divided in two parts of n and m sizes respectively. We need to find the number of such "distinct" arrays such that maximum of all the elements in both parts respectively are same.
Input : $n, m, k$
constraints : $n\leq10^6; m\leq10^6; k\leq10^9$
Output :(number of distinct such arrays)%(10^9+7)
Time limit : 2 sec
Eg : n=2 m=2 k=1
so distinct arrays arrays are :
{ 0 0 | 0 0 }, { 0 1 | 0 1}, {0 1 | 1 0}, {0 1 | 1 1}, {1 0 | 0 1}, {1 0 | 1 0}, {1 0 | 1 1}, {1 1 | 0 1}, { 1 1 | 1 0},
{1 1 | 1 1}
so answer : 10 as there are 10 distinct arrays in which maximum of first n elements = maximum of later m elements.
I have been able to solve this problem pnc wise but i am facing problem in computation as my solution will surpass time limit.
My solution :
$\sum_{X=0}^K [ (1+X)^n - X^n ]*[ (1+X)^m - X^m ]$
Explanation : let the maximum element in both parts be X.
Now for first part ( i.e., first n elements )
Let there be only 1 X : ways-> ${n \choose 1}*( X^{n-1} )$ : selecting 1 element as X and other (n-1) elements could be anything from 0 to X-1
Let there be only 2 X : ways-> ${n \choose 2}*( X^{n-2} )$ : selecting 2 elements as X and other (n-2) elements could be anything from 0 to X-1 . . .
Similiarly upto n X
so number of ways for first part to have X as maximum element
= ${n \choose 1}*( X ^{n-1} ) + {n \choose 2}*( X^{n-2} ) + ... + {n \choose n}*( X^0)$
= $(1+X)^n - X^n$
now second part should also have maximum element as X and similiarly its number of ways
= $(1+X)^m - X^m$
So number of distinct arrays with the two parts having same maximum element as X
= $[ (1+X)^n - X^n ]*[ (1+X)^m - X^m ]$
now since maximum element can be from 0 to K
so answer : $\sum_{X=0}^K [ (1+X)^n - X^n ]*[ (1+X)^m - X^m ]$
Now this could be solved in O(K*(LogN+LogM)) -> Logarithmic term for binary exponentiation.
But K is of order 10^9 so time limit surpasses.
Is there any other way to solve this problem so that the solution passes the time limit.
Thanks in advance for help ;)
You have a sum over a polynomial of degree $m+n$. It's not a particularly deep result that the sum is a polynomial of degree $m+n+1$. Therefore you can calculate the first $m+n+2$ values and extrapolate. I think that Newton's polynomials give a sufficiently efficient algorithm.
The more analytical approach would be to try to find an equivalent to Faulhaber's formula for sums $\sum_x x^a(1+x)^b$