problem link - https://www.codechef.com/COG2020/problems/COG2007

I am not able to simplify the expression in the problem. can anyone help?

1 Like

\sum_0^n\binom{n}{i}=2^n

and

(a+b)^n = \sum_0^n \binom{n}{i}a^ib^{n-i}

so when m=1

\sum_0^n\sum_0^{n-i}\binom{n}{i}\binom{n-i}{j}

=\sum_0^n \binom{n}{i} \times \sum_0^{n-i}\binom{n-i}{j}

since \binom{n}{i} is independent of j.

=\sum_0^n \binom{n}{i} \times 2^{n-i}

=(1+2)^n = 3^n

now when m=2

f(n,2)=\sum_i^n \binom{n}{i}f(n-i,1)

=\sum_i^n \binom{n}{i}3^{n-i}

=(3+1)^n = 4^n

by recursion, f(n,m)=(m+2)^n

\prod_{1}^{n} f(i,m)

=\prod_{1}^{n} (m+2)^i

=(m+2)^{\sum_0^n i}

=(m+2)^\frac{n*(n+1)}{2}

7 Likes

Thanks a lot!

nice thanks a alot