题目内容

小红和小紫在一个一维度的坐标系上玩捉迷藏，其范围为$[1,r]$。

初始时小红位于$x$，小紫位于$y$。

对于每次移动，若小红位于$p(l≤p≤r)$,可以选择向左或者向右移动不超过$a$个距离，即移动后小红位于￥$[max(l,p-a),min(r,p+a)]$之一，且到每个位置的概率相等。

题面描述

小红和小紫在一个一维坐标系上玩捉迷藏，坐标范围为$[1, r]$。初始时，小红位于$x$，小紫位于$y$。每次移动，小红可以选择向左或向右移动不超过$a$个距离，小紫可以选择向左或向右移动不超过$b$个距离。求经过$t$秒后，小红和小紫位于同一个位置的概率。答案需要对$10^9+7$取模。

思路

我们使用动态规划结合二维差分优化来解决这个问题。定义状态 dp[t][i][j] 表示经过 t 秒后，小红位于 i，小紫位于 j 的概率。通过二维差分数组记录每一步的移动概率更新，利用前缀和还原状态，最终累加所有 dp[t][i][i] 得到两人位于同一位置的概率。整个过程通过模运算和逆元计算确保结果的正确性，时间复杂度为$O(t * n^2)$，空间复杂度为$O(n^2)$。

1. 状态表示：我们可以用动态规划来解决这个问题。定义$dp[t][i][j]$表示经过$t$秒后，小红位于$i$，小紫位于$j$的概率。