「CF1114E」Arithmetic Progression

传送门

大概是写的第一道正常一点的交互题吧（

因为原序列是打乱的等差数列，任意两项的差一定形如 $kd$，其中 $k\in\mathbb{N}^{+}$。

于是我们想到，如果我们提取出序列中的一些项，比如说前 $m$ 项，差分，然后求出这些数的 gcd，就有可能是原等差数列的公差。

但这并不一定，因为这个 gcd 也有可能是 $kd$ 的形式。

那么把原序列随机打乱就行了。

求出公差之后二分找原序列最大值即可。

实测 $m$ 最大可以取到 $30$。

这样就可以 A 了。

评测记录。

那么问题来了，这个算法的正确率到底有多大（

我们将这个问题抽象为以下模型：

给定一长度为 $n$ 的随机排列 $p$ 和一正整数 $m$，$1\leqslant m\lt n$，令

$$q_{i}=|p_{i+1}-p_{i}|\quad(i\in[1,m])$$

试求

$$P\left(\gcd_{i=1}^{m}q_{i}=1\right)$$

不会。告辞 .jpg