DDOSvoid's Blog

CF 1623D Robot Cleaner Revisit

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/contest/1623/problem/D‘

简要题意：现在有一个 $n\times m$ 的网格图，以及一个以 $(r_b,c_b)$ 为起点的机器人，机器人每一秒会走一步，其坐标的增量为 $(dr,dc)$，初始时 $dr=dc=1$，每当机器人撞到横向或者竖向的墙壁后，$dr$ 或者 $dc$ 会变成 $-1$，机器人在每个位置都有 $p$ 的概率探测与其在横坐标或者纵坐标相同的所有点，当机器人探测到目标点 $(r_d,c_d)$ 后结束，求期望时间

$n\times m\le 10^5$

Solution

容易得到机器人的行动是有规律的，以 $lcm(n-1,m-1)$ 为一个循环，那么我们首先计算一个循环内期望，令其为 $tans$，同时一个循环内有 $k$ 次可能探测到目标点，第 $i$ 次的时间为 $t_i$，那么 $tans=\sum_{i=0}^{k-1}(1-p)^ipt_i=p\sum_{i=0}^{k-1}(1-p)^it_i$

注意到第 $L$ 次循环的期望为 $(1-p)^{k(L-1)}\sum_{i=0}^{k-1}(1-p)^ip(t_i+(L-1)lcm)$

化简一下得到 $(1-p)^{k(L-1)}(tans+(L-1)lcm\times p\sum_{i=0}^{k-1}(1-p)^i)$，同时我们令 $q=(1-p)^k$，那么最终答案

注意到我们需要枚举一个循环内的所有可以探测到目标点的时间，所以时间复杂度为 $O(nm)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define maxn 200010
#define INF 1000000000
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 

int n, m, sx, sy, tx, ty, pro;

void work() {
    cin >> n >> m >> sx >> sy >> tx >> ty >> pro; pro = pro * pow_mod(100, p - 2) % p;
    vector<int> vec; ll lcm = 2ll * (n - 1) * (m - 1) / gcd(n - 1, m - 1) % p;
    for (int i = 0, x = sx, y = sy, dx = x == n ? -1 : 1, dy = y == m ? -1 : 1; i < lcm; ++i) {
        if (x == tx || y == ty) vec.push_back(i);
        x += dx; y += dy;
        if (x == n || x == 1) dx *= -1;
        if (y == m || y == 1) dy *= -1;
    }
    ll tans = 0, q = pow_mod(1 - pro, vec.size());
    for (int i = 0; i < vec.size(); ++i) tans = (tans + pow_mod(1 - pro, i) * pro % p * vec[i]) % p;
    ll ans = (tans * pow_mod(1 - q, p - 2) + lcm * (1 - q) % p * q % p * pow_mod((1 - q) * (1 - q) % p, p - 2)) % p;
    cout << (ans + p) % p << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}