[AtCoder Beginner Contest 263]E - Sugoroku 3（期望DP）

题目传送门：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;
}