前言

在『江莉XCPC民间算法交流枢纽』有群友扔了这题，还挺有趣的。（这里是专有名词中英文之间不加括号没事的吧？）

题目翻译

给定 $u,v,p$，保证 $p$ 是质数，有 $3$ 种操作：

1. $u\gets u+1$
2. $u\gets u-1$
3. $u\gets u^{p-2}$

以上操作过后均对 $p$ 取模。

求一种不超过 $200$ 次操作使得 $u=v$ 的操作方案。

$0\leq u,v\lt p,3\leq p\leq 10^9+9$。

题目思路

$200$ 直接搜就算有很多操作重复也是会炸的。考虑直接双向搜索，从 $u,v$ 同时开搜。

你怎么知道我没睡醒两边各搜 100 个 TLE on 3。

为啥这样子时间复杂度是正确的？$u\gets u^{p-2}$ 其实就相当于随机选位置跳了，几乎一点关系没有。根据生日悖论，大概搜 $\mathcal O(\sqrt p)$ 次就能搜到，这样子跳到重复的概率其实是非常高的。

搜的时候记录一下前驱后驱，$v$ 搜碰到通过 $u$ 搜到的位置就可以停下输出了。我每个点都是不到 $40$ 次操作。

完整代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int x, y, p;
int pos;
inline int qpow(ll x, int y)
{
    ll ret = 1;
    for (; y > 0; y >>= 1)
    {
        if (y & 1)
            (ret *= x) %= p;
        (x *= x) %= p;
    }
    return ret;
}
inline int inv(int x) { return qpow(x, p - 2); }
map<int, int> frt;
map<int, int> bck;
map<int, pii> pre;
map<int, pii> suf;
queue<pii> q1;
queue<pii> q2;
bool ok;
inline int F(int x, int op)
{
    if (op == 1)
        return (x + 1) % p;
    if (op == 2)
        return (x + p - 1) % p;
    return inv(x);
}
inline bool in(int x) { return 1 <= x && x < p; }
void out_pre(int x)
{
    if (!pre[x].first)
        return;
    out_pre(pre[x].second);
    cout << pre[x].first << " ";
}
void out_suf(int x)
{
    if (!suf[x].first)
        return;
    cout << (suf[x].first == 3 ? 3 : 3 - suf[x].first) << " ";
    out_suf(suf[x].second);
}
int main()
{
    cin >> x >> y >> p;
    pre[x] = {0, 0};
    suf[y] = {0, 0};
    q1.push({x, frt[x] = 0});
    q2.push({y, bck[y] = 0});
    while (!ok && !q1.empty() && !q2.empty())
    {
        int u = q1.front().first, v = q2.front().first;
        int du = q1.front().second, dv = q2.front().second;
        // cout << u << " " << v << endl;
        q1.pop(), q2.pop();
        for (int op = 1; op <= 3; op++)
        {
            int tx = F(u, op);
            if (frt.count(tx))
                continue;
            pre[tx] = {op, u};
            q1.push({tx, frt[tx] = du + 1});
        }
        for (int op = 1; op <= 3; op++)
        {
            int ty = F(v, op);
            if (bck.count(ty))
                continue;
            suf[ty] = {op, v};
            q2.push({ty, bck[ty] = dv + 1});
            if (frt.count(ty))
            {
                ok = 1, pos = ty;
                break;
            }
        }
    }
    cout << frt[pos] + bck[pos] << endl;
    out_pre(pos);
    out_suf(pos);
    return 0;
}