题解 P10539 - [APIO2024] 魔术表演

· · 题解

这里讲一下赛时 20 分钟想到的垃圾做法。

对于 Alice，我们充分发扬人类智慧，考虑对任意 2 \leq v \leq n，都让 X \bmod (v-1) + 1 向 v 连边。

对于 Bob 只需把所有边的信息都用数论知识合并起来即可得出 x 的值。

事实上，本题不需要 excrt，因为 n 只有 5000。暴力枚举（假设已知答案模 p 余 q，就每次把 q 加上 p 直到满足下一个同余条件）时间复杂度 O(n^2)，可以通过。并且取 n=75 时可以通过赛时评测，峰值运行时间 0 毫秒。

事实上，在交互库足够强的情况下，n=75 无法保证一定得出正确答案，具体说明见文章结尾处。（事实上，也可以随机一个置换或者对 X 随机异或一个数使得这个做法不容易被卡，但是我们追求完全确定性做法。）

#include<bits/stdc++.h>
#include"Alice.h"
using namespace std;
const int N=5000;

vector<pair<int,int>> Alice(){
    long long x=setN(N);
    vector<pair<int,int>> edges;
    for(int i=2;i<=N;i++)
        edges.emplace_back(x%(i-1)+1,i);
    return edges;
}
#include<bits/stdc++.h>
#include"Bob.h"
using namespace std;

long long Bob(vector<pair<int,int>> edges){
    __int128 answer=0,nowmod=1;
    for(pair<int,int> edge :edges){
        int r=edge.first-1,mod=edge.second-1;
        while(answer%mod!=r)answer+=nowmod;
        nowmod*=mod/__gcd(nowmod,(__int128)mod);
        if(nowmod>1e18)return answer;
    }
    return answer;
}

考虑优化，容易发现在最初的做法中，一些素数只要删除一次或者两次就无法对答案造成贡献，这样会产生大量的信息浪费，所以考虑构造 a_i < i，然后对于任意 2 \leq v \leq n，令 X \bmod (a_v-1) + 1 向 v 连边。（一开始想到了这么优化，结果因为脑子问题一直以为这么改是变劣的，直到 lhx 大神指点这样居然变优了。）

如果令 a 中每个数为素数的幂，那么可以用暴力搜索和动态规划找出一个较优秀的解。在数列 a 的细节继续优化，目前可以构造出数列 a 使得只需要 n = 99 个结点保证确定性。（之前的 n=95 是错的）

1 2 3 4 5 5 7 7 9 9 11 11 11 13 13 13 16 17 17 17 19 19 19 23 23 23 25 25 27 29 29 29 29 31 31 31 31 32 37 37 37 37 41 41 41 41 43 43 43 43 47 47 47 47 49 49 53 53 53 53 59 59 59 59 61 61 61 61 64 67 67 67 67 71 71 71 71 71 73 73 73 73 79 79 79 79 83 83 83 83 83 89 89 89 89 79 97 97

直觉上 n 可以再小，不知道能不能通过数学证明得出理论最小的 n，可是我太菜了。

附：最简易的数论做法需要 n=615 可以保证通过：