「Codeforces 1114E」Arithmetic Progression

发表于 | | 阅读次数:
字数统计: 981 字

Description

题目链接：Codeforces 1114E

这是一道交互题！

有一个长度为 $n$ 的秘密的序列 $a_i$（不一定是有序的），满足 $0\le a_i\le 10^9$。这个序列有一个特点：升序排列后是一个等差数列。

你可以询问至多 $60$ 次，询问分为以下 $2$ 种类型：

  • 询问一个值 $i(1\le i\le n)$。你将得到 $a_i$ 的值。
  • 询问一个值 $x(0\le x\le 10^9)$。如果序列中存在严格大于 $x$ 的数字则返回 $1$ 否则返回 $0$。

在询问结束后，你要找出这个序列的最小元素和公差（排列后得到的等差序列的公差）。

数据范围：$2\le n\le 10^6$，$0\le a_i\le 10^9$

Solution

可以通过二分求出最大值，记为 $m$；难点是如何求出公差。

由于没有给出 $a_i​$ 的顺序，那么这个问题看似毫无头绪了。我们只能考虑随机化。也就是随机几个 $i​$ 询问 $a_i​$ 的值，然后求出 $\gcd(a_{i+1}-a_i)​$ 作为公差。

使用不同的随机数生成方法进行尝试，我们发现竟然能过？QAQ

这意味着，这种方法的成功概率是很大的。于是考虑证明这个概率（以下证明翻译自 官方题解 并增加部分解释说明）。

为了简单起见，我们假设序列 $a$ 为 $[0,1,2,\dots,n-1]$。假设我们随机询问 $k$（本题中剩余询问次数 $k=30$）次得到的序列 $S$ 为 $[s_1,s_2,\dots,s_k]$。

我们令 $D(S)=\gcd(s_{i+1}-s_i\mid 1\le i<k)​$。如果 $D(S)=1​$ 则意味着成功，否则为失败。记成功的概率为 $P​$，则失败的概率为 $1-P​$。

我们使用莫比乌斯反演来计算 $P$。定义 $f(x)$ 表示 $x$ 整除 $D(S)​$ 的概率。那么有：

即为：

接下来我们计算 $f(x)$ 的值。我们可以发现 $x$ 整除 $D(S)$ 当且仅当对于 $1\le i< k$ 都有 $s_i\equiv s_{i+1}\pmod x$；换言之，存在 $0\le r<x$ 使得对于 $1\le i\le k$ 都有 $s_i\equiv r\pmod x$。

定义 $g(r)$ 表示满足 $s_i\equiv r\pmod x$ 的序列 $S$ 的数量。那么就有：

如何计算 $g(r)$？我们把每个 $s_i$ 都表示成 $x\cdot j+r$ 的形式。换言之，$S$ 一定是 $a_r=[r,x+r,2x+r,\dots]$ 的一个子集。令 $q=\left\lfloor\frac{n}{x}\right\rfloor$。

  • 当 $r<n\bmod x$ 时，$\vert a_r\vert=q+1$，因此 $g(r)=\binom{q+1}{k}$。
  • 当 $n\bmod x\le r<x$ 时，$\vert a_r\vert=q$，因此 $g(r)=\binom{q}{k}$。

综上所述：

当 $n$ 的值较大时，我们可以通过代码计算得到失败的概率是极小的（概率大约为 $1.86185\times 10^{-9}$）。

时间复杂度：$O(60)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <cstdio>
#include <algorithm>

int n,m=30,ret,d,a[35];

int getmax() {
    int l=0,r=1e9,ans;
    while(l<=r) {
        int mid=(l+r)>>1;
        printf("> %d\n",mid),fflush(stdout),scanf("%d",&ret);
        ret?l=mid+1:r=(ans=mid)-1;
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    int mx=getmax();
    for(int i=1;i<=m;++i) {
        int x=1LL*rand()*rand()%n+1;
        printf("? %d\n",x),fflush(stdout),scanf("%d",&a[i]);
    }
    std::sort(a+1,a+m+1),a[++m]=mx;
    for(int i=1;i<m;++i) d=std::__gcd(d,a[i+1]-a[i]);
    printf("! %d %d\n",mx-d*(n-1),d),fflush(stdout);
    return 0;
}
0%