关于F题的疑问
如果dp[x][y]表示的是恰好出现 x 个 2,y 个 3 的期望步数,那么为什么答案不用考虑dp[x + 1][y],dp[x + 2][y]......dp[x + ∞][y] 以及 dp[x][y + 1],dp[x][y + 2]......dp[x][y + ∞] ?答案要求的是第一次出现至少 x 个 2,y 个 3 的期望步数,这两者等价吗?
这些也可以从 dp[x + 1][y - 1],dp[x + 2][y - 1]......dp[x + ∞][y - 1] 以及 dp[x - 1][y + 1],dp[x - 1][y + 2]......dp[x - 1][y + ∞] 对应转移过来呀,也满足题目说的第一次出现就停止呀。
ll inv2 = qsm(2, mod - 2); for(int i = 1 ; i <= 70 ; i ++) dp[i][0] = dp[0][i] = 3 * i; for(int i = 1 ; i <= 70 ; i ++) for(int j = 1 ; j <= 70 ; j ++) { dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 3) % mod * inv2 % mod; } cout << dp[x][y] << endl;