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!