题目描述
给定一张 n × m n \times m n×m的网格图，给定机器人起始位置和垃圾位置，每次机器人可以从 ( x , y ) (x ,y) (x,y)向 ( x + 1 , y + 1 ) (x + 1, y + 1) (x+1,y+1)运动，碰壁后对方向取反。每次可以将移动到的位置所在的横行和竖列清空掉，现在告诉你当机器人与垃圾同行同列时有 p % p\% p%概率清掉垃圾。问清理垃圾所需移动次数的期望。
题解
首先，机器人移动的过程一定存在循环节，也就是说从某点出发一直按照题目规则移动，一定会回到该点(证明略)。那么不妨设每 L L L步一循环，这 L L L步中有 k k k次与垃圾同行同列。
设 s i s_i si?表示到第 i i i个点所移动的步数，那么可以列出期望的表达式：
E [ i ] = ∑ j = 0 ∞ ( s i + j × L ) × ( 1 ? p ) j × k + i × p E[i] = \sum^{\infty}_{j = 0}(s_i + j \times L) \times (1 - p)^{j \times k+ i} \times p E[i]=j=0∑∞?(si?+j×L)×(1?p)j×k+i×p
对上式进行化简：
E [ i ] = ∑ j = 0 ∞ [ ( s i × p ) + ( j × L × p ) ] × ( 1 ? p ) j × k + i E[i] = \sum^{\infty}_{j = 0}[(s_i \times p) + (j \times L \times p) ] \times (1 - p)^{j \times k + i} E[i]=j=0∑∞?[(si?×p)+(j×L×p)]×(1?p)j×k+i
= ∑ j = 0 ∞ [ ( s i × p × ( 1 ? p ) i ) + ( j × L × p × ( 1 ? p ) i ) ] × ( 1 ? p ) j × k = \sum^{\infty}_{j = 0}[(s_i \times p \times (1 - p)^i) + (j \times L \times p \times (1 - p)^i) ] \times (1 - p)^{j \times k} =j=0∑∞?[(si?×p×(1?p)i)+(j×L×p×(1?p)i)]×(1?p)j×k
= ∑ j = 0 ∞ [ s i × p × ( 1 ? p ) i ] × ( 1 ? p ) j × k + [ j × L × p × ( 1 ? p ) i ] × ( 1 ? p ) j × k = \sum^{\infty}_{j = 0}[s_i \times p \times (1 - p)^i] \times (1 - p)^{j \times k} + [j \times L \times p \times (1 - p)^i] \times (1 - p)^{j \times k} =j=0∑∞?[si?×p×(1?p)i]×(1?p)j×k+[j×L×p×(1?p)i]×(1?p)j×k
= [ s i × p × ( 1 ? p ) i ] × ∑ j = 0 ∞ ( 1 ? p ) j × k + [ L × p × ( 1 ? p ) i ] × ∑ j = 0 ∞ j × ( 1 ? p ) j × k = [s_i \times p \times (1 - p)^i] \times \sum^{\infty}_{j = 0} (1 - p)^{j \times k} + [L \times p \times (1 - p)^i] \times \sum^{\infty}_{j = 0}j \times (1 - p)^{j \times k} =[si?×p×(1?p)i]×j=0∑∞?(1?p)j×k+[L×p×(1?p)i]×j=0∑∞?j×(1?p)j×k
对 ∑ j = 0 ∞ ( 1 ? p ) j × k \sum^{\infty}_{j = 0} (1 - p)^{j \times k} ∑j=0∞?(1?p)j×k，设 q = ( 1 ? p ) k q = (1 - p)^k q=(1?p)k，等比数列求和后，由于 ( 1 ? p ) ≤ 1 (1 - p) \leq 1 (1?p)≤1，故数列收敛，取极限得 1 1 ? q = 1 1 ? ( 1 ? p ) k \frac{1}{1 - q} = \frac{1}{1 - (1 - p)^k} 1?q1?=1?(1?p)k1?。
对 ∑ j = 0 ∞ j × ( 1 ? p ) j × k \sum^{\infty}_{j = 0}j \times (1 - p)^{j \times k} ∑j=0∞?j×(1?p)j×k，发现为一等差数列项 × \times ×等比数列项的形式，运用错位相减法求和后同样取极限得 ( 1 ? p ) k [ 1 ? ( 1 ? p ) k ] 2 \frac{(1 - p)^k}{[1 - (1 - p)^k]^2} [1?(1?p)k]2(1?p)k?
于是可得：
E
[
i
]
=
s
i
×
p
×
(
1
?
p
)
i
1
?
(
1
?
p
)
k
+
L
×
p
×
(
1
?
p
)
i
+
k
[
1
?
(
1
?
p
)
k
]
2
E[i] = \frac{s_i \times p \times (1 - p)^i}{1 - (1 - p)^k} + \frac{L \times p \times (1 - p)^{i + k}}{[1 - (1 - p)^k]^2}
E[i]=1?(1?p)ksi?×p×(1?p)i?+[1?(1?p)k]2L×p×(1?p)i+k?
求和得：
∑
i
=
0
k
?
1
E
[
i
]
=
∑
i
=
0
k
?
1
s
i
×
p
×
(
1
?
p
)
i
1
?
(
1
?
p
)
k
+
L
×
(
1
?
p
)
k
1
?
(
1
?
p
)
k
\sum_{i = 0}^{k - 1}E[i] = \frac{\sum_{i = 0}^{k - 1}s_i \times p \times(1- p)^i}{1 - (1 - p)^k} + \frac{L \times (1 - p)^k}{1 - (1 - p)^k}
i=0∑k?1?E[i]=1?(1?p)k∑i=0k?1?si?×p×(1?p)i?+1?(1?p)kL×(1?p)k?
那么直接模拟走的轮数求和即可。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N], b[N];
inline int binpow(int x, int y, int mod, int res = 1){
for (; y; y >>= 1, (x *= x) %= mod) if (y & 1) (res *= x) %= mod;
return res;
}
inline int inv(int x){ return binpow(x, MOD - 2, MOD); }
inline void solve(){
int n, m, rb, cb, rd, cd, p; cin >> n >> m >> rb >> cb >> rd >> cd >> p;
p = p * inv(100) % MOD;
int pre = 1, idx = 0, ans = 0, dr = 1, dc = 1;
map<tuple<int, int, int, int>, bool> mp;
while(true){
if (rb + dr < 1 || rb + dr > n) dr *= -1;
if (cb + dc < 1 || cb + dc > m) dc *= -1;
if (mp[{rb, cb, dr, dc}]) break;
else mp[{rb, cb, dr, dc}] = true;
if (rb == rd || cb == cd) {
ans = (ans + idx * pre % MOD * p % MOD) % MOD;
pre = pre * (1 - p + MOD) % MOD;
}
rb += dr, cb += dc, idx++;
}
ans = ((ans + idx * pre % MOD) % MOD) * inv((1 - pre + MOD) % MOD) % MOD;
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0);
int t = 0; cin >> t;
while(t--) solve();
return 0;
}
