Codeforces Round #763 (Div. 2)

D. Robot Cleaner Revisit

题目链接：https://codeforces.com/contest/1623/problem/D
解题代码来自于cf某大佬 ：By AlanSkarica；

思路：

由于最多只有n ∗ * ∗m个点，所以循环的点最多n ∗ * ∗m个，又因为边缘只有两种状态，顶点只有一种状态，故共有4(m-1)(n-1)种状态点，且4(m-1)(n-1)一定是环的边长的整数倍，对于每k种状态x₁,x₂…x_k,每个状态可能的情况都是 p / 100 p/100 p/100，对于x₁，若在x₁点清扫 则需0s,若不在则需 x x x₂ + 1 + 1 +1 s,以此类推若此点可清楚x_k = (1-p/100)（1 + x₁），不能清楚则x_k = （1 + x₁）;
最终便可得到方程：
x=a1(1+a2(1+a3(1+…ak(1+x)…)))
a_i表示第i个点可以消除。
同时该式可改写成 x = u + vx 的形式，最后所求 x = u/(1-v)；

这里由于mod为质数，故可用费马小定理来求解 x⋅(1-v)≡u,最终 x = u*(1-v)^{mod - 2}^

代码：

#include<iostream>

using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;

int add(int x,int y){
	x += y;
	while(x >= mod) x -= mod;
	while(x < 0) x += mod;
	return x;
}

int mul(int x,int y){
	return ( x * 1ll* y) % mod;
}

int binpow(int x,int y){
	int c = 1;
	while(y){
		if(y % 2 == 1) c = mul(c,x);
		x = mul(x,x);
		y /= 2;
	}
	return c;
}

int inv(int x){
	return binpow(x,mod - 2);
}

int divide(int x,int y){
	return mul(x,inv(y));
}

void solve()
{
	int n,m,rb,cb,rd,cd,p;
	scanf("%d%d%d%d%d%d%d",&n,&m,&rb,&cb,&rd,&cd,&p);
	p = add(1,-divide(p,100));
	
	int u = 0 , v = 1 , dr = -1 , dc = -1;
	
	for(int i = 0 ; i < 4 * ( m - 1) * (n - 1) ; i++){
		if(rb + dr < 1 || rb + dr > n) dr *= -1;
		if(cb + dc < 1 || cb + dc > m) dc *= -1;
		rb += dr;
		cb += dc;
		
		u = add(u,1);
		if(rb == rd || cb == cd){
			u = mul(u,p);
			v = mul(v,p);
		} 
	}
	cout<<divide(u,add(1,-v))<<"\n";
}
int main()
{
	
	int tt;
	scanf("%d",&tt);
	while(tt--){
		solve();
	}
	return 0;
 }