CF995E Number Clicker 题解

题意：

有三种操作：

令 $u \gets u + 1 \pmod p$

令 $u \gets u - 1 \pmod{p}$

令 $u \gets u^{p-2} \pmod{p}$

给定 $u,v$ 和质数 $p$ ，构造一种方案让 $u$ 变成 $v$ ，操作数不超过 $200$ 次。

输入格式：

一行， $u,v,p$ 。

输出格式：

第一行输出操作次数，第二行输出每次操作的序号 $c_i(1\le c_i \le 3)$ 。

数据范围：

$0 \le u,v \le p - 1,~3 \le p \le 10^9 + 9$ 。

直接 bfs 的话肯定是过不了的，不过因为这里的操作都是可逆的，所以我们可以尝试双向 bfs 。

因为 $u^{p-2} \bmod{p}$ 的值难以预测，所以 $u \gets u^{p-2} \pmod{p}$ 这个操作可以近似看作随机的。

由于我们的算法可以看作在 $[0,p-1]$ 随机了 $n\le 2k$ 个点，

那么根据生日悖论，至少两个点相同的概率 $p(n)$ ，可以用以下公式逼近。

$p(n)\, \sim\, 1-\frac{1}{\exp \left(\frac{n^2}{2N}\right)} = 1 - \frac{1}{\exp \left(\frac{n^2}{2\times (10^9 + 9)}\right)}$

用 wolfram 跑了一下，$n$ 大约在 $10^5$ 的时候 $p(n) > 0.99$ ，假装它是 $\mathcal{O}(\sqrt{p})$ 的吧。

因此时间复杂度大约是 $\mathcal{O}(\sqrt{p} \log p)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)())

int P, top, stk[233];
queue<int> q1, q2; unordered_map<int, int> vis1, vis2, nxt, pre;
int qpow(int a, int b)
{
    int r = 1;
    for(a %= P; b; b >>= 1, a = (ll)a * a % P)
        if(b & 1) r = (ll)r * a % P;
    return r;
}
void output(int u)
{
    cout << vis1[u] + vis2[u] - 2 << '\n';
    int x = u; top = 0;
    while(x != -1) { stk[++top] = x, x = pre[x]; }
    for(; top > 1; --top)
    {
        const int a = stk[top]; 
        const int b = stk[top - 1];
        if((a + 1) % P == b) cout << "1 ";
        else if((a + P - 1) % P == b) cout << "2 "; else cout << "3 ";
    }
    for(x = u; nxt[x] != -1; x = nxt[x])
    {
        if((x + 1) % P == nxt[x]) cout << "1 ";
        else if((x + P - 1) % P == nxt[x]) cout << "2 "; else cout << "3 ";
    }
}
void work()
{
    static int u, a, b, c;
    u = q1.front(); q1.pop();
    if(vis2[u]) { output(u); exit(0); }
    a = (u + 1) % P, b = (u + P - 1) % P, c = qpow(u, P - 2);
    if(!vis1[a]) { q1.push(a); vis1[a] = vis1[u] + 1; pre[a] = u; }
    if(!vis1[b]) { q1.push(b); vis1[b] = vis1[u] + 1; pre[b] = u; }
    if(!vis1[c]) { q1.push(c); vis1[c] = vis1[u] + 1; pre[c] = u; }
    u = q2.front(); q2.pop();
    a = (u + 1) % P, b = (u + P - 1) % P, c = qpow(u, P - 2);
    if(!vis2[a]) { q2.push(a); vis2[a] = vis2[u] + 1; nxt[a] = u; }
    if(!vis2[b]) { q2.push(b); vis2[b] = vis2[u] + 1; nxt[b] = u; }
    if(!vis2[c]) { q2.push(c); vis2[c] = vis2[u] + 1; nxt[c] = u; }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int u, v; cin >> u >> v >> P;
    q1.push(u); vis1[u] = 1; pre[u] = -1;
    q2.push(v); vis2[v] = 1; nxt[v] = -1;
    while(!q1.empty()) work();
    return 0;
}