PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Dynamic Programming, Binomial Coefficients
EXPLANATION:
More than writing code, this problem requires you to sit down and work out equations on a sheet. So get yourself a piece of paper and try working out these equations yourself as you go through the editorial.
We will see two different approaches with different complexities for this problem:
SETTER’S SOLUTION:
Will be updated soon.
APPROACH
Complexity: O(MND2)
Let us define dp[m][n] = f(m,n,X)
(For ease, we will write f(m,n,X) as f(m,n) thoughout this editorial. This will not make any difference as X is constant for any particular case.)
f(m,n) = Σ P(k1x)P(k2x)…P(kmx)
where Σ ki = n= Σk P(kx) Σ P(k1x)P(k2x)…P(km-1x) for k = n to 0
= Σk P(kx) Σ f(m-1,n-k)
= P(nx).f(m-1,0) + P((n-1)x).f(m-1,1) + … +
P(0x).f(m-1,n)= P(nx).dp[m-1][0] + P((n-1)x).dp[m-1][
1] + … +
P(0x).dp[m-1][n]
By expanding the P(cx) functions we get:
= (C0(nx)0 + C1(nx)1 + C2(nx)2 +…+ CD(nx)D) . dp[m-1][0]
+(C0((n-1).x)0 + C1((n-1).x)1 + C2((n-1).x)2 +…+ CD((n-1).x)D) . dp[m-1][1].
.
+(C0(0x)0 + C1(0x)1 + C2(0x)2 +…+ CD(0x)D) . dp[m-1][n]
Note that 0^0 is considered as 1 here.
Now, let us define another variable.
Let
sum[m][n][k] = dp[m-1][
0] * n^k +
dp[m-1][1] * (n-1)^k + … +
dp[m-1][n] * 0^k
Also, let C[k] = Ck . xk
Thus, the above equation can be rearranged and we get:
f(m,n) = dp[m][n] = sum[m][n][
0] *
C[0] + sum[m][n][1] * C[1] +
… + sum[m][n][D] * C[D]
And sum[m][n][k] can be calculated as:
if k=0, then sum[m][n][
0] =
sum[m][n-1][0] + dp[m-1][n]if k=1,
then sum[m][n][1] = sum[m][n-1][1] +
sum[m][n-1][0]if k=2, then
sum[m][n][2] = sum[m][n-1][2] +
2*sum[m][n-1][1] + sum[m][n-1][0]
because
sum[m][n][
2] - sum[m][n-1][2]= dp[m-1][
0] * (n2 - (n-1)2) + dp[m-1][1] * ((n-1)2 - (n-2)2) +
… + dp[m-1][n-1] * (12 - 02)= dp[m-1][
0] * (2n + 1) + dp[m-1][1] * (2(n-1) + 1) + … + dp[m-1][n-1] * (2*0 + 1)= 2*sum[m][n-1][
1] + sum[m][n-1][0]
And for generalized k (>= 1), we have
sum[m][n][k] = Comb(k,k) *
sum[m][n-1][k] + Comb(k,k-1) *
sum[m][n-1][k-1] + Comb(k,k-2) *
sum[m][n-1][k-2] + … + Comb(k,0) *
sum[m][n-1][0]
where Comb(a,b) = a!/(b! * (a-b)!)
Comb(a,b) can be calculated easily as Comb(a-1,b) + Comb(a-1,b-1) and use the precomputed values without having to compute it repeatedly.
Thus, for every (m,n) pair, we are doing approximately D2 operations(k operations to calculate each sum[m][n][k] and there are D such values of k).
Hence the order of the solution will be O(MND2). But a naive implementation will not pass the time limit. The problem asks you to find the answer modulo 10^9 + 7. ***The ’' operator is a very costly operator***. So we must use it wisely. Too many operations will give you a TLE. There are several methods to reduce the number of such operations.
A simple if condition can reduce it to a very large extent. For example,
if(ans >= MOD)
ans%=mod;
This will perform the ‘%’ operation only when required. A better optimization for this problem is as follows:
for(k=0;k<n;k++)
sum = (sum + a[k]*b[k])%MOD;
We can use the fact that a[k] and b[k] are already calculated using %MOD i.e. both of them are less than MOD.
So we define LIM as 2^63 - 1 – MOD ^ 2. Thus, LIM + a[k]*b[k] will always fit in long long of C/C++.
Therefore we can replace
for(k=0;k<n;k++)
sum = (sum + a[k]*b[k])%MOD;
with
for(k=0;k<n;k++){
sum += a[k]*b[k];
if(sum > LIM)
sum %= MOD;
}
if(sum >= MOD) sum %= MOD;
This optimized code has at most ceil(n/8) % operations.
TESTER’S SOLUTION:
Can be found here.
APPROACH:
Complexity O(NMD)
Let’s begin exactly like the way we did for the previous solution.
f(m,n) = Σ P(k1x)P(k2x)…P(kmx)
where Σ ki = n= Σk P(kx) Σ P(k1x)P(k2x)…P(km-1x) for k = n
to 0= Σk P(kx) Σ f(m-1,n-k)
= Σk P((n-k)x) Σ f(m-1,k)
Now let’s try and calculate P((n-k)x)
From the definition of P(x) , we get:
P((n-k)x) = ?j
Cj(n-k)jxj for j = 0 to D= ?j Cj ?i Comb(i,j)
n(j-i) (-1)i
ki xj= ?i ki (-1)i ?j Cj
Comb(i, j) n(j-i)
xj
Let a[n][i] = (-1)i ?j Cj Comb(i, j) n(j-i) xj
Hence, f(m,n) = ?k?i a[n][i] . ki . f(m-1,k)
= ?i a[n][i] ?k ki . f(m-1,k)
Clearly, total number of operations to calculate f(m,n) are N.D.M. Hence the complexity of the solution is O(NMD).
This solution can be optimized in the same way as the above solution by reducing the number of % operations.
ALTERNATE TESTER’S SOLUTION:
Can be found here.
APPROACH:
We saw that
f(m,n) = ? P(k1x)P(k2x)…P(kmx)
where ? ki = n
Let A[j] = P(x*j). Hence the above equation can be rewritten as:
f(m,n) = ? f(m-1, k) * A[n-k] for
0<=k<=n
So, f(m) = f(m-1) * A where A * B is the convolution of sequences A and B:
C = A * B if C[n] = Sum[A[k] * B[n-k],
0<=k<=n]
We need to find f[M][N]. We have
f(M) = f([M-1) * A = (f(F[M-2) * A) * A =
… = (((f[0] * A) * A) …) * A,
where f[0] = {1, 0, …, 0}.
Since convolution has both associative and commutative properties, we can simply write:
f(M) = AN * f(0) where AN = A * A * … * A is the convolution power.
The attached code contains quite descriptive explanation of this solution in comments.
