13253번: 토러스

https://www.acmicpc.net/problem/13253


$O(nm)$

문제와 같이 움직이면 띠형태로 순환할 것이다.
이에 따라 다음 문제로 변형할 수 있다.

x=0, 1, ..., n 지점이 있다.
매 시도마다 좌우로 각각 1/2 확률로 움직인다.
x=k에서 시작해서 x=0 or x=n 에 최초로 도착할 때까지의 시도 횟수 기댓값 a[k]는?

a[k]들은 다음 식들을 만족한다.
a[1]=(a[0]+a[2])/2+1
a[2]=(a[1]+a[3])/2+1
...
a[n-1]=(a[n-2]+a[n])/2+1
a[0]=a[n]=0
위 식들의 좌우변을 각각 더하면
a[1]+a[n-1]=2n-2
a[1]=a[n-1] 이므로 a[1]=n-1
a[i]=(a[i-1]+a[i+1])/2+1
를 이용하면
a[k]=k(n-k)

#include<cstdio>
int n, m, x, y, t = -1, c, i, j;
int main() {
    scanf("%d%d%d%d", &n, &m, &x, &y);
    do {
        if (t<0 && i == x&&j == y) t = c;
        i = (i + 1) % n;
        j = (j + 1) % m;
        c++;
    } while (i | j);
    printf("%d", t<0 ? -1 : c*t - t*t);
    return 0;
}