题解 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$ 随机异或一个数使得这个做法不容易被卡，但是我们追求完全确定性做法。） ```cpp #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; } ``` ```cpp #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$ 是错的） ```plain 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$ 可以保证通过： - $n=614$ 时，取 $X=897,612,484,786,617,601=2^8 \times 3^4 \times 5^2 \times 7^2 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37 + 1$，只有 $308$ 条边不可以保证得出正确答案。 - $n=615$ 时可以证明一定可以得出正确答案。