B. Lunatic Never Content - 题解

题意简述/n/n给定长度为 $n$ 的非负整数序列 $a_1,a_2,/cdots,a_n$，定义 $f(a,x)$ 表示将每个 $a_i$ 取模 $x$ 后得到的序列 $a_1/bmod x,a_2/bmod x,/cdots,a_n/bmod x$。求最大的 $x$，使得 $f(a,x)$ 是一个回文序列。/n/n## 题解/n/n首先需要注意到一个结论：如果 $x$ 是满足条件的，那么对于所有 $y/ge x$，$y$ 都是满足条件的。/n/n证明：如果 $f(a,x)$ 是回文序列，那么对于所有 $i$，$a_i/bmod x=a_{n-i+1}/bmod x$，因此对于所有 $y/ge x$，都有 $a_i/bmod y=a_{n-i+1}/bmod y$。因此 $f(a,y)$ 也是回文序列。/n/n因此我们只需要找到最小的满足条件的 $x$ 即可。/n/n考虑如何判断 $f(a,x)$ 是否是回文序列。因为 $x$ 是给定的，我们可以先计算出所有 $a_i/bmod x$ 的值，然后判断这个值序列是否是回文序列。/n/n我们可以将这个值序列中的值按照出现次数从大到小排序，设这个序列的长度为 $m$。如果这个序列是回文序列，那么我们需要满足：/n/n- 对于所有 $i/le /lfloor /frac{m}{2}/rfloor$，第 $i$ 大和第 $m-i+1$ 大的值相等。/n- 对于所有 $i>/lfloor /frac{m}{2}/rfloor$，第 $i$ 大的值为 $0$。/n/n我们可以枚举 $x$，然后对于每个 $x$ 计算出 $f(a,x)$ 的值序列，并按照上述方法判断是否是回文序列。时间复杂度 $/mathcal{O}(n/log n/log w)$，其中 $w$ 是 $a_i$ 的范围。注意到 $x$ 的范围是 $[1,/max_i a_i]$，因此需要对每个 $x$ 分别计算 $f(a,x)$。如果直接暴力计算，时间复杂度会达到 $/mathcal{O}(t/cdot n^2/log w)$，无法通过此题。/n/n考虑如何优化计算 $f(a,x)$ 的过程。我们可以对每个 $i$ 预处理出 $a_i$ 对于所有 $x$ 的余数，即对于所有 $i$ 和 $x$，预处理出 $a_i/bmod 1,a_i/bmod 2,/cdots,a_i/bmod /max_i a_i$。这个预处理过程的时间复杂度是 $/mathcal{O}(n/log w)$。/n/n然后我们需要快速计算 $f(a,x)$。对于每个 $x$，可以预处理出 $f(a,x)$ 中每个值出现的次数，即对于每个 $x$ 和每个 $i$，预处理出 $a_j/bmod x=i$ 的 $j$ 的个数。这个预处理过程的时间复杂度是 $/mathcal{O}(n/log w)$。/n/n有了这些预处理，我们对于每个 $x$ 可以 $/mathcal{O}(1)$ 计算出 $f(a,x)$ 的值序列，并按照上述方法判断是否是回文序列。时间复杂度 $/mathcal{O}(n/log w)$，可以通过此题。/n/n## 代码实现/n/ncpp/n#include <bits/stdc++.h>/nusing namespace std;/n/nconst int maxn = 1e5 + 5;/nint a[maxn], cnt[maxn], mod[maxn][maxn];/n/nint main() {/n int t;/n cin >> t;/n while (t--) {/n int n;/n cin >> n;/n int mx = 0;/n for (int i = 1; i <= n; i++) {/n cin >> a[i];/n mx = max(mx, a[i]);/n }/n for (int i = 1; i <= n; i++) {/n for (int j = 1; j <= mx; j++) {/n mod[i][j] = a[i] % j;/n }/n }/n int ans = 0;/n for (int x = 1; x <= mx; x++) {/n memset(cnt, 0, sizeof(cnt));/n for (int i = 1; i <= n; i++) {/n cnt[mod[i][x]]++;/n }/n bool flag = true;/n int m = 0;/n for (int i = 0; i <= x; i++) {/n if (cnt[i]) {/n m++;/n }/n }/n for (int i = 1; i <= m / 2; i++) {/n if (cnt[i] != cnt[m - i + 1]) {/n flag = false;/n break;/n }/n }/n for (int i = m / 2 + 1; i <= m; i++) {/n if (cnt[i]) {/n flag = false;/n break;/n }/n }/n if (flag) {/n ans = x;/n break;/n }/n }/n cout << ans << endl;/n }/n return 0;/n}/n/n