APIO2025 Hack 题解

20_200 · 2025-05-19 19:58:34 · 题解

APIO2025 Hack!

很好的交互题，充分展现人类智慧，但是它并不配被放在T1。

题意

有一个正整数 n\le 10^9，由交互库初始时生成，而后固定不变，但对你不可见。

你需要编写一个函数 int hack() 去猜测 n 的值。

你可以在 hack() 中调用交互库提供的 ll collisions(vector<ll>x) 函数，要求传入的 x 所有元素互不相同且为正整数，该函数返回 \sum_{i,j\in x,i\neq j}[x_i\bmod n=x_j\bmod n]，即该序列中模 n 后会产生哈希冲突的二元组数。

你需要保证所有调用传入的 x 的长度之和不超过 110000 才能获得满分，否则若不超过 10^6 也可获得一部分的分数。

交互库

一个可以直接用 VSCode F5/Dev F11 编译运行的交互库。（同目录下的 hack.h 文件为符合洛谷提交格式的文件，题解最后面的代码符合要求）

#include "hack.h"
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <map>
#include <set>

static int n = 0;
static int total_cost = 0;

long long collisions(std::vector<long long> x){
    total_cost += (int) x.size();
    if (total_cost > 1000000){
        printf("Total cost exceeded 1,000,000\n");
        exit(0);
    }

    long long res = 0;

    std::map<int, int> table;
    std::set<long long> seen;
    for (long long v : x){
        if (v < 1 || v > (long long)1e18){
            printf("x[i] is out of range\n");
            exit(0);
        }

        if (seen.find(v) != seen.end()){
            printf("x has a duplicate element\n");
            exit(0);
        }

        seen.insert(v);

        res += table[v % n];
        table[v % n]++;
    }

    return res;
}

int main(){
    int t=20;
    // assert(1 == scanf("%d", &t));

    std::vector<int> ns(t);
    mt19937 rnd(time(0));
    int mxc=0;
    for (int i = 0; i < t; i++){
        ns[i]=rnd()%(100000000)+9e8;
        ns[0]=735134400;
        ns[1]=768398400;
        // assert(1 == scanf("%d", &ns[i]));
        cout<<ns[i]<<'\n';
        total_cost = 0;
        n = ns[i];
        int ans = hack();
        printf("%d %d\n", ans, total_cost);

        mxc=max(mxc,total_cost);
    }
    cout<<"max:"<<mxc<<'\n';
    cout<<"score:"<<25+75*(mxc<110000?1:log(1e6/(mxc-9e4))/log(50));
    return 0;
}

分析

以下包含了本题各档不同得分的做法，每一档都是一个做法或者优化，建议看完一档后继续想一想再接着看，可能有利于更好的理解和启发做这类题的思路。

8pts

显然只需对 k=1,2,\dots,5\times10^5 全部询问一遍 \{1,k+1\} 即可。

25pts

若 n\le5\times10^5 ，则存在一个 n 的倍数在 (5\times10^5,10^6] 范围内，则只需对 (5\times10^5,10^6] 内的数询问一遍即可解决 n\le10^6。(这个优化非常重要，在后面还会用到，可以让询问次数变为原来的 \frac{1}{\sqrt2} 倍)

27pts

对于 n\le10^9 的数据，若要在 10^6 次内猜对，则 O(n) 级别的询问次数是不可接受的。需要设计一个根号或者略高于根号的算法。

题目背景是卡哈希，如果你真的被卡过哈希的话应该了解过生日悖论。随机生成 k 个 [1,10^{14}] 整数并对 n 取模，使得存在一对数相同。每一对整数取模后是否相同可近似视为相互独立，则存在两个整数模意义下相同的概率为 1-(1-\frac{1}{n})^{\binom{k}{2}}\approx1-e^{-\frac{k^2}{2n}}，若取 k=120000，则每次成功的概率大于 99.9\%。

那么现在的问题变成了从一个序列中找一对数模 n 相同（称之为哈希冲突对），保证存在。因为只要找到一个哈希冲突对就可以通过枚举该对两数之差的因子的方法使用很少的次数询问出 n 的值。

首先有一个非常简单的想法就是二分最短的存在哈希冲突的前缀，这样就可以找到最靠前的存在哈希冲突对的位置，然后再枚举另一个数就能找到一个哈希冲突对。

这个方法是 O(\sqrt{n}\log n) 的，精细调参后可以做到询问次数 \le10^6，但是顶多也就 27pts。

44pts

使用类似分治的方法把这个 log 去掉。具体的，尝试找到某种方法在序列长度级别的次数内把整个序列的规模减半。

对于当前的序列 S，把它分成 4 个序列 S_1,S_2,S_3,S_4，然后两两拼在一起进行询问就可以确定一个包含哈希冲突对的子序列 S_xS_y，然后把它变为新的 S ，则其长度变为原来的一半，继续向下递归直到其长度为 2 即可确定一个哈希冲突对。

这样询问次数的复杂度就变成了 O(\sqrt{n}) 。

在两两询问的过程中，一旦当前询问的序列包含哈希冲突对则后面的无需继续询问而可以直接向下递归，且最后一对是无需询问的，因为整个序列中哈希冲突对必定存在。这个算法每次递归期望需要 \frac{1+2+3+4+5+5}{2\times6}|S|=\frac{5}{3}|S| 询问次数，则整个过程的期望次数为 \frac{10}{3}|S|，大约为 400000，可以获得 44pts 左右。

62pts

发现序列长度为 120000 ，乘以 \frac{10}{3}|S| 实在太大了。考虑降低初始序列的长度，随机生成完后询问整个序列检查是否包含哈希冲突对，若一次不成功则重新随机直到成功为止。则期望询问次数变为了 (\frac{10}{3}+\frac{1}{1-e^{-\frac{|S|^2}{2n}}})|S|。由于需要随机生成序列，若失败则要整个重来，所以若序列长度太大，则方差会很大。考场上使用的这个做法，经过几十次 selfeval 精细调参后取了 |S|=40000，得分会在 [45,78] 中随机，最终得分 62pts。

69pts

找的 S 的一个哈希冲突对用了 \frac{10}{3}|S| 的询问次数，且稳定性很差，得分不高。

将 S 分成 S_0,T_0 。先询问 S_0,T_0 即可判断 S_0,T_0 是否单独包含哈希冲突对，若是的话则直接将其变为新的 S 即可使长度减半。

否则，哈希冲突对一定在 S_0 和 T_0 之间，将 S_0 再分成 S_1,S_2，T_0 再分成 T_1,T_2 。先将 S_1 和 T_0 拼起来询问即可确定哈希冲突对在 S_1 还是 S_2 中，从而得到长度减半的新的 S_0。 然后再将 T_1 和新的 S_0 拼起来询问即可确定哈希冲突对在 T_1 还是 T_2 中，从而得到长度减半的新的 T_0。

而且哈希冲突对一旦被确定在 S_0 和 T_0 之间，之后就不需要再判断 S_0 和 T_0，那么每次递归需要的询问次数就是 |S_0|+\frac{3}{2}|T_0|，总的次数为 2|S_0|+3|T_0|。

因为 |S_0| 和 |T_0| 的系数不同，所以初始划分时其最优大小也不相等，所以每次递归之前如果 |S_0|<|T_0| 则交换 S_0 和 T_0 。

加上一开始单独询问的 |S_0|+|T_0| 次和随机生成序列的需要的次数，总的期望次数为 (\frac{7}{2}+\frac{1}{1-e^{-\frac{|S|^2}{2n}}})|S|，期望虽略大，但方差远小于上一个算法，故在多测取max的情况下得分更高，大约 69pts。

76pts

初始随机生成序列时，由于需要检查是否成功而消耗了非常多的次数，且若失败还要重来，非常不稳定。

尝试构造一个初始序列使得其两两之差可以覆盖 \le10^9 的所有正整数。把 25pts 部分的优化加上，只需要覆盖 (5\times10^8,10^9] 的所有正整数即可。

BSGS 算法的思想 可以解决这个问题。取一个 \sqrt{n} 级别的阈值 B，让 S_0=\{1,2,\dots,B\},T_0=\{5\times10^8+B,5\times10^8+2B,\dots,5\times10^8+\lceil\frac{5\times10^8}{B}\rceil B\}，那么容易发现，这样的 S_0,T_0 可以覆盖所有 5\times10^8+xB-y(x\in[1,\lceil\frac{5\times10^8}{B}\rceil],y\in[1,B])，即 (5\times10^8,10^9] 的所有正整数。

经过调参，取 B=18500 较优，询问次数可以降低到 150000 左右，获得 76pts。

97pts

判断 S_0,T_0 内部是否单独包含哈希冲突对消耗了 |S_0|+|T_0| 次询问，这非常多，尝试优化这个部分。

在上面的构造方法中，S_0,T_0 都是等差数列，其内部两两之差可以覆盖的数也是等差数列。由于 S_0 的两两之差都可以乘 B 后在 T_0 的两两之差中找到，因此只需考虑 T_0 内部的情况。