mayoko’s diary

プロコンとかいろいろ。

SRM 487 div2 hard: BunnyConverter

解法

x の値から 次の y を考えるのは難しいですが, y の値から 元の x が何であったかを推定するのは, x = -y^2 - z^3 (mod n) と簡単に出来ます。よって, 各 y について対応する x を求め, x -> y に辺を貼るようなグラフを作った後, start から goal までの距離を幅優先探索すれば良いです。

class BunnyConverter {
public:
    int getMinimum(int n, int z, int start, int goal) {
        const int INF = 1e9;
        vector<vi> G(n);
        start %= n;
        goal %= n;
        ll z3 = 1;
        for (int i = 0; i < 3; i++) z3 = (z3*z)%n;
        for (ll y = 0; y < n; y++) {
            int x = (-y*y-z3) % n;
            x = (x+n)%n;
            G[x].push_back((int)y);
        }
        vector<int> d(n, INF);
        d[start] = 0;
        queue<int> que;
        que.push(start);
        while (!que.empty()) {
            int now = que.front(); que.pop();
            for (int next : G[now]) {
                if (d[next] > d[now]+1) {
                    d[next] = d[now]+1;
                    que.push(next);
                }
            }
        }
        int ans = d[goal];
        if (ans >= INF) ans = -1;
        return ans;
    }
};