[Help needed] AtCoder: F - Make 10 Again
Difference between en1 and en2, changed 46 character(s)
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,  

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English NerfThis 2024-04-18 20:01:10 46 Tiny change: 'preciated!\n\n\n\n\nThe editorial makes sense to me, ' -> 'preciated!'
en1 English NerfThis 2024-04-18 20:00:40 1775 Initial revision (published)