题目链接 - CodeForces ↗
地板有 n n n m m m ( r b , c b ) (r_b, c_b) ( r b , c b ) ( r d , c d ) (r_d, c_d) ( r d , c d )
每过一秒，机器人的坐标会 ( r , c ) → ( r + d r , c + d c ) (r, c)\rightarrow (r+d_r, c+d_c) ( r , c ) → ( r + d r , c + d c )
初始时 d r = d c = 1 d_r=d_c=1 d r = d c = 1 d r , d c d_r,d_c d r , d c
若机器人碰到上/下边界（r = 1 r=1 r = 1 r = n r=n r = n d r ← − d r d_r\leftarrow -d_r d r ← − d r
若机器人到达左/右边界（c = 1 c=1 c = 1 c = m c=m c = m d c ← − d c d_c\leftarrow -d_c d c ← − d c
每一秒内，位于 ( r , c ) (r,c) ( r , c ) p 100 \frac{p}{100} 100 p r r r c c c 之后 ，它将按照上面的规则进行移动。
若每次清理的结果相互独立，求清理掉障碍物 ( r d , c d ) (r_d, c_d) ( r d , c d )
参考了由 darkkcyan ↗ 提供的 Codeforces Round #763 (Div. 2) Editorial ↗ 。
首先，设 p ‾ = 1 − p 100 \overline{p}=1-\frac{p}{100} p = 1 − 100 p
样例一#
从样例一开始分析。
循环共两步，设 x 1 x_1 x 1 ( 1 , 1 ) (1,1) ( 1 , 1 ) x 2 x_2 x 2 ( 2 , 2 ) (2,2) ( 2 , 2 ) 。
当位于 ( 1 , 1 ) (1, 1) ( 1 , 1 ) 如果成功 ，花费时间 0 s 0s 0 s 若否 ，走到 ( 2 , 2 ) (2,2) ( 2 , 2 ) 1 s 1s 1 s x 2 x_2 x 2
{ x 1 = p ⋅ 0 + p ‾ ( 1 + x 2 ) = p ‾ ( 1 + x 2 ) x 2 = p ⋅ 0 + p ‾ ( 1 + x 1 ) = p ‾ ( 1 + x 1 ) \begin{cases}
x_1=p\cdot 0 + \overline{p}(1+x_2)=\overline{p}(1+x_2)\\
x_2=p\cdot 0 + \overline{p}(1+x_1)=\overline{p}(1+x_1)\\
\end{cases} { x 1 = p ⋅ 0 + p ( 1 + x 2 ) = p ( 1 + x 2 ) x 2 = p ⋅ 0 + p ( 1 + x 1 ) = p ( 1 + x 1 ) 联立一下，得到关于 x 1 x_1 x 1
x 1 = p ‾ ( 1 + p ‾ ( 1 + x 1 ) ) x_1=\overline{p}(1+\overline{p}(1+x_1)) x 1 = p ( 1 + p ( 1 + x 1 )) 逐层展开求解，x 1 x_1 x 1
样例二#
再看样例二。
循环共四步：( 1 , 1 ) → ( 2 , 2 ) → ( 1 , 3 ) → ( 2 , 2 ) (1,1)\rightarrow (2,2)\rightarrow (1,3)\rightarrow (2,2) ( 1 , 1 ) → ( 2 , 2 ) → ( 1 , 3 ) → ( 2 , 2 ) 其中 ( 1 , 1 ) (1,1) ( 1 , 1 ) ，其余位置均有可能。
同理，设 x 1 x_1 x 1 ( 1 , 1 ) (1,1) ( 1 , 1 ) x i x_i x i i i i x 2 ≠ x 4 x_2\neq x_4 x 2 = x 4
与样例一类似地，有：
{ x 1 = 1 + x 2 x 2 = p ‾ ( 1 + x 3 ) x 3 = p ‾ ( 1 + x 4 ) x 4 = p ‾ ( 1 + x 1 ) \begin{cases}
x_1 = 1 + x_2\\
x_2 = \overline{p}(1 + x_3)\\
x_3 = \overline{p}(1 + x_4)\\
x_4 = \overline{p}(1 + x_1)\\
\end{cases} ⎩ ⎨ ⎧ x 1 = 1 + x 2 x 2 = p ( 1 + x 3 ) x 3 = p ( 1 + x 4 ) x 4 = p ( 1 + x 1 ) 联立，得到关于 x 1 x_1 x 1
x 1 = 1 + p ‾ ( 1 + p ‾ ( 1 + p ‾ ( 1 + x 1 ) ) ) x_1=1 + \overline{p}(1 + \overline{p}(1 + \overline{p}(1 + x_1))) x 1 = 1 + p ( 1 + p ( 1 + p ( 1 + x 1 ))) 若我们已知循环共有 k k k
联立后的方程形如：
x = a 1 ( 1 + a 2 ( 1 + a 3 ( 1 + ⋯ a k ( 1 + x ) ⋯ ) ) ) x=a_1(1+a_2(1+a_3(1+\cdots a_k(1+x)\cdots))) x = a 1 ( 1 + a 2 ( 1 + a 3 ( 1 + ⋯ a k ( 1 + x ) ⋯ ))) 其中 a i ∈ { 1 , p ‾ } a_i\in\{1,\overline{p}\} a i ∈ { 1 , p } 当循环中第 i i i a i = p ‾ a_i=\overline{p} a i = p a i = 1 a_i=1 a i = 1 .
由于数据范围 4 ≤ n ⋅ m ≤ 1 0 5 4\leq n\cdot m\leq 10^5 4 ≤ n ⋅ m ≤ 1 0 5 暴力搜索找到循环 。
求解方程时，考虑从内向外逐层展开，过程中记录：常数项 u u u v v v
初始 u = 0 u=0 u = 0 v = 1 v=1 v = 1 每次展开时先算出 a a a { v ← a ⋅ v u ← a ⋅ ( u + 1 ) \begin{cases}v\leftarrow a\cdot v\\u\leftarrow a\cdot (u+1)\end{cases} { v ← a ⋅ v u ← a ⋅ ( u + 1 ) 。
循环长度#
我们把机器人的移动，分解在 x / y x/y x / y 2 ( n − 1 ) 2(n-1) 2 ( n − 1 ) 2 ( m − 1 ) 2(m-1) 2 ( m − 1 )
因此，4 ( n − 1 ) ( m − 1 ) 4(n-1)(m-1) 4 ( n − 1 ) ( m − 1 ) lcm ( 2 ( n − 1 ) , 2 ( m − 1 ) ) \operatorname{lcm}(2(n-1), 2(m-1)) lcm ( 2 ( n − 1 ) , 2 ( m − 1 )) 是循环长度的整数倍 。
所以不必通过暴力搜索找到循环，对于所有数据都直接迭代 4 ( n − 1 ) ( m − 1 ) 4(n-1)(m-1) 4 ( n − 1 ) ( m − 1 )
注意倒序。
#include <bits/stdc++.h> #define int long long using namespace std ; const int mod = 1 e 9 + 7 ; inline int power ( int x , int k ) { int ret = 1 ; while (k) { if (k & 1 ) ret = ret * x % mod; x = x * x % mod; k >>= 1 ; } return ret; } inline int inv ( int x ) { return power (x % mod, mod - 2 ); } int T, n, m, ax, ay, bx, by, dx, dy, p, pp; signed main () { cin >> T; while (T -- ) { cin >> n >> m >> ax >> ay >> bx >> by >> p; pp = ( 100 - p) * inv ( 100 ) % mod; p = p * inv ( 100 ) % mod; int u = 0 , v = 1 ; dx = dy = - 1 ; //倒序 for ( int cas = 1 ; cas <= 4 * (n - 1 ) * (m - 1 ); cas ++ ) { //迭代4(n-1)(m-1)次 if (ax + dx > n || ax + dx < 1 ) dx = - dx; if (ay + dy > m || ay + dy < 1 ) dy = - dy; ax += dx; ay += dy; u = (u + 1 ) % mod; if (ax == bx || ay == by) u = u * pp % mod, v = v * pp % mod; } cout << u * inv (mod + 1 - v) % mod << endl; } return 0 ; } cpp
