Hi,
I am trying to solve this problem from AtCoder: F — Make 10 Again, using the following approach. (I have read the editorial and it makes sense to me, but it is a different dp approach).
the answer == the number of valid dice roll states / the total number of dice roll states
For a valid state, it means there is some way to get a sum of a target sum.
Let dp[i][j] be the number of valid states from A[1, i] with sum j
My main logic is as follows. Clearly this is wrong. But I am not sure why it is incorrect.
Is it because the assumption of valid ways / total ways is incorrect? (since A[i] can be different values) or if this is right, my dp state transition is incorrect.
long[][] dp = new long[n + 1][11];
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
dp[i][0] = 1;
for(int j = 1; j <= 10; j++) {
//a[i] does not contribute to the sum j, so a[i]'s actual roll does not matter
dp[i][j] = dp[i - 1][j] * a[i] % mod;
//a[i] contributes to the sum j, a[i]'s actual roll must be <= j
for(int v = 1; v <= min(a[i], j); v++) {
dp[i][j] = addWithMod(dp[i][j], dp[i - 1][j - v], mod);
}
}
}
long total = 1;
for(int i = 1; i <= n; i++) {
total = multiplyWithMod(total, a[i], mod);
}
long ans = dp[n][10] * modInv(total, mod) % mod;
out.println(ans);
Any help is appreciated!