题面描述
小红和小紫在一个一维坐标系上玩捉迷藏，坐标范围为[1,r]。初始时，小红位于x，小紫位于y。每次移动，小红可以选择向左或向右移动不超过a个距离，小紫可以选择向左或向右移动不超过b个距离。求经过t秒后，小红和小紫位于同一个位置的概率。答案需要对109+7取模。
思路
我们使用动态规划结合二维差分优化来解决这个问题。定义状态 dp[t][i][j] 表示经过 t 秒后，小红位于 i，小紫位于 j 的概率。通过二维差分数组记录每一步的移动概率更新，利用前缀和还原状态，最终累加所有 dp[t][i][i] 得到两人位于同一位置的概率。整个过程通过模运算和逆元计算确保结果的正确性，时间复杂度为O(t∗n2)，空间复杂度为O(n2)。
- 状态表示：我们可以用动态规划来解决这个问题。定义dp[t][i][j]表示经过t秒后，小红位于i，小紫位于j的概率。
P2659.第3题-捉迷藏
题目内容
小红和小紫在一个一维度的坐标系上玩捉迷藏，其范围为[1,r]。
初始时小红位于x，小紫位于y。
对于每次移动，若小红位于p(l≤p≤r),可以选择向左或者向右移动不超过a个距离，即移动后小红位于￥[max(l,p−a),min(r,p+a)]之一，且到每个位置的概率相等。
