题目传送门:E - Sugoroku 3 (atcoder.jp)
题目大意 / Problem
有N个点(位置),其中从1到N - 1个点上各有一个骰子,在第i个点上可以投掷第i个骰子,假设在x位置上投到y,下一步就走到y上。保证下一个位置不会大于N。
问从位置1到位置N的步数期望,对998244353。
思路 / Thought
之前有写过期望的题《[LightOJ]Race to 1 Again(期望DP)》,但是和这道题还是有点区别的。
我们用dp[i]表示从i到N所需的期望步数。
显然应该从后往前进行dp,那么转移方程怎么写呢?
朴素的想法就是dp[i] = sum(dp[j]) / (a[i] + 1) + 1,j从i到i + a[i],意思是有1.0 / (a[i] + 1)的概率通过走1 + dp[j]步到终点N。
但是这里毕竟不能从dp[i]转移到dp[i]嘛,所以对dp[i]进行一个移项就好了。
最后的方程是dp[i] = (sum(dp[j]) + a[i] + 1) / a[i],j从i + 1到i + a[i]。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 9, p = 998244353; int a[maxn], N, dp[maxn], suffix[maxn]; int qmi(int a,int b) { int res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p, b >>= 1; } return res; } int inv(int x){return qmi(x, p - 2);} void solve() { cin >> N; for(int i = 1;i < N; ++ i)cin >> a[i]; for(int i = N - 1;i >= 1; -- i) { dp[i] = (suffix[i + 1] - suffix[i + a[i] + 1] + p + a[i] + 1) * inv(a[i]) % p; suffix[i] = (suffix[i + 1] + dp[i]) % p; } cout << dp[1] << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int _ = 1; while(_ --)solve(); return 0; }
Comments NOTHING