ABC298E 题解

前言

题目传送门！

更好的阅读体验？

题解区的代码都好丑啊，嘲讽。

思路

对于这种概率题，正常人都能反应到这是 dp。

所以：\(dp_{t, i, j}\) 表示：当前是第 \(t\) 回合，Tak 在 \(i\) 位置，Aok 在 \(j\) 位置，概率。

如果这样设状态的话，转移方程就会非常一眼（刷表）：

其中 \(\texttt{sti} \in \{1, 2, \cdots, p\}\)，\(\texttt{stj} \in \{1, 2, \cdots q\}\)，表示两人的步数。

答案就是 \(\sum\limits_{t=1}^n\sum\limits_{j=b}^n dp_{t, n, j}\)，表示某一回合内 Tak 走到 \(n\) 了，那必然算入答案内。

初始化 \(dp_{0, a, b} = 1\)。更多细节参考代码，注意分数用逆元实现。

闲话

时间复杂度 \(O(n^2pq)\)。

题解区写得没我好看的原因是，他们的复杂度是 \(O(n^2(p+q))\) 吧，好像跑得比我快多了。

但是正常机子跑常数极小的 \(10^8\) 级别运算，还是能轻松胜任的（？）所以就过了。不信的话，你拿样例三跑一跑！

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 998244353;
int qpow(int x, int y = mod - 2)
{
	int ans = 1;
	while (y)
	{
		if (y & 1) ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return ans;
}
int dp[105][105][105]; //dp[t][i][j] : 第t回合，Tak在i位置，Aok在j位置，概率 
int main()
{
	int n, a, b, p, q, ans = 0;
	cin >> n >> a >> b >> p >> q;
	int inv = 1ll * qpow(p) * qpow(q) % mod;
	
	dp[0][a][b] = 1;
	for (int t = 1; t <= n; t++)
		for (int i = a; i < n; i++)
			for (int j = b; j < n; j++)
				for (int sti = 1; sti <= p; sti++)
					for (int stj = 1; stj <= q; stj++)
						dp[t][min(n, i + sti)][min(n, j + stj)] = (dp[t][min(n, i + sti)][min(n, j + stj)] + 1ll * inv * dp[t - 1][i][j] % mod) % mod;
	for (int t = 1; t <= n; t++)
			for (int j = b; j <= n; j++)
				ans = (ans + dp[t][n][j]) % mod;
	cout << ans;
	return 0;
}

希望能帮助到大家！