题目来源: 2019 ICPC Asia EC Final: H. King

题目来源: XJTUOJ-1223 zxh的一气通贯

题目链接: https://oj.xjtuicpc.com/problem/1223

题面

一共 \(T\) 组数据.

给定素数 \(p\), 以及长度为 \(n\) 的序列 \(a_1,a_2,\cdots, a_n\).

需要找出满足下列条件的子序列 \(b_1,b_2,\cdots,b_m\) 的最大长度:

  1. 子序列长度 \(m\ge n/2\).
  2. \(\forall i\in[1,m)\cap\mathbb N\), \(\exists q\in\mathbb N\), s.t. \(qb_i\equiv b_{i+1}\pmod p\). 即子序列在模 \(p\) 意义下是等比子序列.

若不存在这种子序列, 输出 -1.

数据范围

\[ 1\le T<1000 \]

\[ 1\le n\le2\times10^5 \]

\[ 2\le p\le10^9+7 \]

\[ 1\le a_1,a_2,\cdots,a_n<p \]

保证输入的 \(p\) 是素数. 数据组中 \(n\) 的总和不超过 \(2\times10^5\).

题解

考虑在确定公比 \(q\) 的情况下, 找出最长的等比子序列. 记 \(dp[i]\) 为序列 \(a_i,a_{i+1},\cdots,a_n\) 的最长等比子序列的长度, 其中该等比子序列公比为 \(q\), 首项为 \(a_i\). 则若 \(i\) 之后的第一个 \(qa_i\bmod p\) 位置在 \(a_j\), 则 \[ dp[i]=dp[j]+1 \] 用vector<int> 存储同一个数字 \(a\) 的所有位置, 并用 map 建立 \(a\) 和其所有位置的映射. 由于位置是固定的, 且位置编号单调递增, 故寻找之后第一个 \(qa_i\bmod p\) 的位置可以在映射的所有位置中使用二分查找. 按该方法查找一次的复杂度为 \(O(\log n)\).

边界条件: 找不到 \(a_j\), 则最长等比子序列为 \(a_i\), 长度为 \(1\), \(dp[i]=1\).

确定公比 \(q\) 的情况下, 最长等比子序列的长度为: \[ \max_{1\le i\le n}dp[i] \] 求得长度的复杂度为 \(O(n\log n)\).

若直接枚举公比, 则每个可能的公比都形如 \(a_ia_j^{-1}\bmod p\), 至多有 \(O(n^2)\) 个公比可供选择, 不能接受.

考虑取公比 \(q\) 时, 若以 \(q\) 为公比的子序列长度不小于 \(n/2\), 则可以注意到: 这个子序列一定有一定量的相邻元素对, 在原序列的位置相邻或隔一. 考虑这样的相邻元素对的最小数量 \(s\). 若所有的相邻元素对在原序列的位置都相隔至少 \(2\), 则最多一共有 \((n-1)/3\) 对元素. 但由于子序列长度不小于 \(n/2\), 相邻元素对的数量不小于 \(n/2-1\). 故 \(s\) 的一个下界为: \[ s\ge \frac n2-\frac{n-1}3-1\tag1 \] 这个下界是 \(n/6\) 量级的.

考虑原序列中相邻或隔一的元素对, 每个元素对确定了一个公比 \(a_ia_j^{-1}\bmod p\), 这一共有 \(2n-3\) 个（可以重复的）取值, 而 \(q\) 要在这些取值中出现至少 \(s\) 次. 这是一个必要条件, 可以利用这个必要条件筛选掉不可能满足条件的公比. 使用下界(1)进行筛选, 最终最多只会剩 \(12\) 个左右的公比可能符合条件, 即公比只有 \(O(1)\) 个取值.

总复杂度为 \(O(n\log n)\).

备注

\(s\) 的一个更紧的下界为 \[ s\ge \frac n4-1\tag 2 \] 证明如下: 设有 \(k\) 个相邻元素对在原序列中的位置相隔至少 \(2\), 则有以下不等式: \[ \begin{align}3k+s+1&\le n\tag3\\k+s+1&\ge \left\lceil{n/2}\right\rceil\tag4\end{align} \] (3) 减 (4) 可得 \[ k\le \frac n4 \] 而根据 (4) 可知 \[ s\ge\frac n2-k-1\ge\frac n4-1 \]

代码实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 1; i <= n; ++i)
typedef long long llong;
const int mxn = 300000;
int dp[mxn];
llong n, p;
llong s[mxn], a[mxn], sv[mxn], inv[mxn];
map<llong, llong> cnt;
map<llong, vector<int>> fnd;
llong fpow(llong a, llong b)
{
    llong ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= a, ans %= p;
        b >>= 1;
        a *= a, a %= p;
    }
    return ans;
}
void fndinv()
{
    s[0] = 1;
    rep(i, n)
        s[i] = s[i - 1] * a[i] % p;
    sv[n] = fpow(s[n], p - 2);
    for (int i = n; i >= 1; --i)
        sv[i - 1] = sv[i] * a[i] % p;
    for (int i = 1; i <= n; ++i)
        inv[i] = sv[i] * s[i - 1] % p;
}
int fndl(int st, int ds)
{
    if (dp[st])
        return dp[st];
    llong nxvar = a[st] * ds % p;
    auto nx = upper_bound(fnd[nxvar].begin(), fnd[nxvar].end(), st);
    if (nx == fnd[nxvar].end())
        return dp[st] = 1;
    else
        return dp[st] = fndl(*nx, ds) + 1;
}
inline int nm(int n)
{
    return n / 2 - (n - 1) / 3 - 1;
}
int main()
{
    int t;
    scanf("%d", &t);
    rep(rt, t)
    {
        cnt.clear();
        fnd.clear();
        int ans = 1;
        scanf("%lld%lld", &n, &p);
        rep(i, n)
            scanf("%lld", &a[i]),
            fnd[a[i]].push_back(i);
        fndinv();
        for (int i = 2; i <= n; ++i)
            ++cnt[a[i] * inv[i - 1] % p];
        for (int i = 3; i <= n; ++i)
            ++cnt[a[i] * inv[i - 2] % p];
        for (auto sp : cnt)
            if (sp.second >= nm(n))
            {
                rep(i, n)
                    ans = max(ans, fndl(i, sp.first));
                rep(i, n)
                    dp[i] = 0;
            }
        if (ans * 2 >= n)
            printf("%d\n", ans);
        else
            printf("-1\n");
    }
    return 0;
}

花絮

笔者在现场比赛过程中未能通过本题, 但算法与本文一致. 在复现中使用相同的算法重写, 仍 Wrong Answer. 经排查算法未有错误, Wrong Answer 是代码中某运算未取模导致. 由于此问题, 笔者错失了 ICPC Asia EC Final 的银牌. 在发现这一问题后, 为防止再次出现类似问题, 笔者撰写了模 \(p\) 同余类模板.