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;
}