SRM663

The constraint on D is the key to solve this problem.

As different ways are given, Generating function would be a great tool to hold all the info all at once.

Suppose ways = {1, 3, 6, 2}, then $f(x) = 1 + 3x + 6x^2 + 2x^3$

By adding a coin whose value is 1, then new ways is $f(x) * (1+x)$

On the contrary, by removing a coin whose value is 1, the new ways is $f(x) {(1+x)}^{-1}$

By removing n coins, the new ways is $f(x) {(1+x)}^{-n}$

The coefficient of $x^k$ is $\binom{-n}{k}$ which has to be developed.

$\binom{n}{k} = (-1)^{k} \binom{k - n - 1}{k}$ $\implies$ $\binom{-n}{k} = (-1)^{k} \binom{k + n - 1}{k}$

The final answer would be

$\sum_{k=0}^D (-1)^{k} \times ways[D - k] \times \binom{k + numberRemoved[i] - 1}{k}$

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------

Hide Comments