Hi, ↵
↵
I am trying to solve this problem from AtCoder: [F — Make 10 Again](https://atcoder.jp/contests/abc310/tasks/abc310_f), 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!↵
↵
↵
↵
↵
The editorial makes sense to me,
↵
I am trying to solve this problem from AtCoder: [F — Make 10 Again](https://atcoder.jp/contests/abc310/tasks/abc310_f), 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!
↵
↵
↵
↵
The editorial makes sense to me,
