## 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(MND ^{2})**

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(k

_{1}x)P(k_{2}x)…P(k_{m}x)

where Σ ki = n= Σ

_{k}P(kx) Σ P(k_{1}x)P(k_{2}x)…P(k_{m-1}x) 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:

= (C

_{0}(nx)^{0}+ C_{1}(nx)^{1}+ C_{2}(nx)^{2}+…+ C_{D}(nx)^{D}) . dp[m-1][0]

`+`

(C_{0}((n-1).x)^{0}+ C_{1}((n-1).x)^{1}+ C_{2}((n-1).x)^{2}+…+ C_{D}((n-1).x)^{D}) . dp[m-1][`1`

].

.

`+`

(C_{0}(0x)^{0}+ C_{1}(0x)^{1}+ C_{2}(0x)^{2}+…+ C_{D}(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] = C_{k} . x^{k}

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`

] * (n^{2}- (n-1)^{2}) + dp[m-1][`1`

] * ((n-1)^{2}- (n-2)^{2}) +

… + dp[m-1][n-1] * (1^{2}- 0^{2})= 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 **D ^{2}** 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(MND ^{2})**. But a naive implementation will not pass the time limit. The problem asks you to find the

**answer modulo 10^9 + 7**.

*. So we must use it wisely. Too many % operations will give you a*

**The ‘%’ operator is a very costly operator****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(k

_{1}x)P(k_{2}x)…P(k_{m}x)

where Σ k_{i}= n= Σ

_{k}P(kx) Σ P(k_{1}x)P(k_{2}x)…P(k_{m-1}x) 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}

C_{j}(n-k)^{j}x^{j}for j = 0 to D= ?

_{j}C_{j}?_{i}Comb(i,j)

n^{(j-i)}(-1)^{i}

k^{i}x^{j}= ?

_{i}k^{i}(-1)^{i}?j C_{j}

Comb(i, j) n^{(j-i)}

x^{j}

Let a[n][i] = (-1)^{i} ?_{j} C_{j} Comb(i, j) n^{(j-i)} x^{j}

Hence, f(m,n) = ?_{k}?_{i} a[n][i] . k^{i} . f(m-1,k)

= ?_{i} a[n][i] ?_{k} k^{i} . 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(k

_{1}x)P(k_{2}x)…P(k_{m}x)

where ? k_{i}= 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) = A^{N} * f(0) where A^{N} = A * A * … * A is the convolution power.