APIO2025 Hack 题解

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 文件为符合洛谷提交格式的文件，题解最后面的代码符合要求）

CPP

#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

内部的情况。

T_0

的两两之差形如

\{x,2x,\dots,kx\}

。可以对这个集合再用一次刚才的 BSGS 构造，用

\{x,2x,\dots,\sqrt kx,2\sqrt kx,3\sqrt kx,\dots,kx\}

即可在

O(\sqrt{\max(|S_0|,|T_0|)})

次的级别内检查

T_0

内部的情况。

那么现在的询问次数是

2\max(|S_0|,|T_0|)+3\min(|S_0|,|T_0|)+2\sqrt{\max(|S_0|,|T_0|)}

，取

|S_0|=18500,|T_0|=27027

，大约为

109880

，实际最大值在

112000

左右，可以获得 97pts。

100pts

上述询问次数计算中忽略了最后的枚举因子得出

n

的值的部分，这个部分使用的次数为

2d(m)

，其中

m

是我们找到的哈希冲突对的两数之差的绝对值，

d(m)

表示

m

因子个数，它的值是期望

O(\log m)

级别但并不总是这样，某些数的因子个数可能会非常巨大。例如当

m=735134400

时

d(m)=1344

（

\le10^9

的数中最多的），这个部分消耗了两千多的询问次数，可以 hack 上述做法。

设我们最后询问得到的

m

的质因数分解形式是

m=\prod p_k^{v_k}

，则询问所有

x=m\times p_k^{i-v_k}(0\le i\le v_k)

并对所有返回为

n

的倍数的

x

取 gcd 即可得到

n

的值，因为 gcd 之后所有的质因数都得到了它应有的指数。这样这个部分的询问次数就降到了质因子数的严格

O(\log n)

级别，严格不超过

2(1+\log_2n)

。

最终的询问次数的最大值是

109917

，可以 AC 本题。想不到这个

110000

竟然卡得如此之紧。

调参

对于这种次数卡得很紧且式子里需要取整的题目，调参时使用程序暴力枚举参数的值可能会比求导/不等式进行最小值的理论分析得到的结果更优。如果存在随机性，可在程序跑出的理论值附近手动调参使得实际运行结果更优。如果是多测取max，不仅要关注期望，还需要关注方差（随机波动性）带来的影响（当然也可以直接最小化多测取max之后的期望，但是这大概率比较难算）。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve vector<ll>
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
ll collisions(ve x);
ve meg(ve x,ve y){
	ve z=x;
	for(ll i:y)z.pb(i);
	return z;
}
ve div(ve x,ll t){
	ve y;
	for(ll i=0;i<x.size();i++)
		if((i&1)==t)y.pb(x[i]);
	return y;
}
int hack(){
	ll B=18500,B0=sqrt(max(B,(int)5e8/B+1))+1,w=0;
	ve s,t,z;
	for(ll i=1;i<=B;i++)s.pb(i);
	for(ll i=B;i<=5e8;i+=B)t.pb(i+5e8+B);
	for(ll i=1;i<=B0;i++)z.pb(i*B),z.pb((i+1)*B0*B);
	if(collisions(z)){
		for(ll i:z)for(ll j:z)
			if(i!=j&&collisions({i,j}))w=abs(i-j);
	}
	else{
		while(s.size()>1||t.size()>1){
			if(s.size()<t.size())swap(s,t);
			ve c[2]={div(s,0),div(s,1)};
			if(c[0].size()>c[1].size())swap(c[0],c[1]);
			s=c[collisions(meg(c[0],t))?0:1];
			c[0]=div(t,0),c[1]=div(t,1);
			if(c[0].size()>c[1].size())swap(c[0],c[1]);
			t=c[collisions(meg(c[0],s))?0:1];
		}
		w=abs(s[0]-t[0]);
	}
	s={w};
	ll x=w,ans=0;
	for(ll i=2;i*i<=w;i++)
		if(x%i==0){
			ll v=1;
			while(x%i==0)x/=i,v*=i;
			for(ll j=1;j<=v;j*=i)s.pb(w/v*j);
		}
	for(ll i:s)
		if(collisions({i+1,1}))ans=__gcd(ans,i);
	return ans;
}

文章操作

APIO2025 Hack!

相关推荐

评论

APIO2025 Hack 题解