5627번: BAKTERIJE

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

풀이는 http://hsin.hr/coci/archive/2012_2013/에서 contest #6의 6번 참조

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
typedef long long ll;
int n, m, k, ex, ey, ck[51][51][4], u[51][51];
ll res = -1;
vector<pair<int, int> > v[5], pa;
int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }
void ee(ll a, ll b, ll &x, ll &y) {
    if (b) ee(b, a%b, y, x), y -= a / b*x;
    else x = 1 / a, y = 0;
}
ll multi(ll x, ll y, ll mod) {
    if (!y) return 0;
    ll ret = multi(x, y / 2, mod);
    return (ret * 2 + y % 2 * x) % mod;
}
void crt() {
    int maxi = 0;
    vector<pair<int, int> > t = pa;
    for (int i = 0; i < k; i++) {
        if (maxi < t[i].second) maxi = t[i].second;
        if (!t[i].first) {
            for (auto it : t)
                if (!it.first && t[i].second != it.second || it.first && (t[i].second < it.second || (t[i].second - it.second) % it.first)) return;
            if (!~res || res > t[i].second) res = t[i].second;
            return;
        }
        for (int j = 0; j < i; j++) if ((t[i].second - t[j].second) % gcd(t[i].first, t[j].first)) return;
    }
    ll a = 1, b = 0;
    for (int i = 2; i < 1e4; i++) {
        ll tp, p = 1, r = 0, x, y, ta;
        for (int j = 0; j < k; j++) {
            tp = 1;
            while (t[j].first%i == 0) t[j].first /= i, tp *= i;
            if (p < tp) p = tp, r = t[j].second%p;
        }
        if (p > 1) {
            ee(p, a, x, y);
            ta = a*p;
            b = (multi(multi(p, x, ta), b, ta) + multi(multi(a, y, ta), r, ta)) % ta;
            a = ta;
        }
    }
    while (b < maxi) b += a;
    if (!~res || res > b) res = b;
}
void f(int h) {
    if (h == k) crt();
    else for (auto it : v[h]) {
        pa.push_back(it);
        f(h + 1);
        pa.pop_back();
    }
}
int main() {
    scanf("%d%d%d%d%d", &n, &m, &k, &ex, &ey);
    for (int i = 0; i < k; i++) {
        int x, y, d, cnt = 1;
        char c;
        scanf("%d%d %c", &x, &y, &c);
        for (int j = 1; j <= n; j++) for (int k = 1; k <= m; k++) scanf("%1d", u[j] + k);
        memset(ck, 0, sizeof(ck));
        for (int j = 0; j < 4; j++) if ("URDL"[j] == c) d = j;
        while (!ck[x][y][d]) {
            ck[x][y][d] = cnt++;
            d = (d + u[x][y]) % 4;
            if (x + dx[d] < 1 || x + dx[d] > n || y + dy[d] < 1 || y + dy[d] > m) d = (d + 2) % 4;
            x += dx[d]; y += dy[d];
        }
        for (int it : ck[ex][ey]) if (it) v[i].push_back({ it < ck[x][y][d] ? 0 : cnt - ck[x][y][d],it });
    }
    f(0);
    printf("%lld", res);
    return 0;
}