D - Number of Multisets Editorial by evima
In this problem, we want to find the following: - The number of ways to decompose \(K\) into \(N\) numbers, each of which is \(1\) or \(\frac{1}{2}\) or \(\frac{1}{4}\) or\(\dots\)
Let us divide these decompositions into two categories: decompositions using \(1\) at least once and decompositions not using \(1\).
Decompositions using \(1\):
The number of such decompositions is equal to the following:
- The number of ways to decompose \(K-1\) into \(N-1\) numbers, each of which is \(1\) or \(\frac{1}{2}\) or \(\frac{1}{4}\) or\(\dots\)
Decompositions not using \(1\):
The number of such decompositions is equal to the following:
- The number of ways to decompose \(K\) into \(N\) numbers, each of which is \(\frac{1}{2}\) or \(\frac{1}{4}\) or\(\dots\)
By multiplying all values by \(2\), we can see that this is equal to the following:
- The number of ways to decompose \(2K\) into \(N-1\) numbers, each of which is \(\frac{1}{2}\) or \(\frac{1}{4}\) or\(\dots\)
Thus, we have dp[N][K] = dp[N-1][K-1] + dp[N][2K]
, where dp[N][K]
is the answer to the problem.
Note that, from the definition of the problem, we have dp[N][K] = 0
for \(N < K\), and we can solve the problem in \(O(N^2)\) time.
posted:
last update: