PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This problem is to be solved using dynamic programming approach plus some combinatorics.
First, define dp[i][j] as the number of ways to cook exactly j different types of dish for i days. As the base case, it is obvious that dp[0][0] = 1, dp[0][x] = 0 for x > 0.
Suppose we know the value of dp[i][j] for some pair (i, j). Now, consider the (i+1)th day. There are two options for us:
- Cook a dish which has been cooked before. There are j types of such dishes. We can update dp[i+1][j]:
dp[i+1][j] += j * dp[i][j] - Cook a new type of dish. Note that we don’t care which type of dish it is; we only care that its type is different from all j types. We can update dp[i+1][j+1]:dp[i+1][j+1] += dp[i][j]
After that, we’ll take the actual types of dish into account. There are M available types of dish. There are P(M, j) ways to choose j types from M types (the order is important). So, the number of ways to cook exactly j different types of dish for i days is P(M, j) * dp[i][j] = (M! / (M-j)!) * dp[i][j] = M! * (M-j)!-1 * dp[i][j]. Of course, all calculations are performed modulo MOD = 1000000007.
We can precompute all values of k! for all 1 ≤ k ≤ M. The value of k!-1 (mod MOD) can be calculated using Euler’s Theorem: k!-1 = k!MOD-2 (mod MOD). Also, the DP values can be computed only once for all T test cases.
Since the original problem asks for the number of ways to cook at most K different types of dish in N days, the final answer is: sum {M! * (M-j)!-1 * dp[N][j]} for all 1 ≤ j ≤ min(M, K).
The complexity of this solution is O(N(M+K) + M log MOD + T(M+K)).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.