[ICPC2019西安H] King

[ICPC2019西安H] King - 思维,随机化

Description

求带模的等比子序列最大长度，如果长度大于等于n/2向上取整就输出长度，否则输出 -1。

Solution

有解的情况下，被选择的数字之间的平均间距不可能太大，并且一定有距离不超过 2 的两个数

这样，我们随机选些数，就有很大概率选到那些处在答案序列的数上

对于每个随机挑选的数，我们向前向后扫描整个序列，计算出包含这个数的最大 King

随机做一百次，基本一定能找到

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 200005;

int a[N], n, p;

int qpow(int p, int q, int mod)
{
    return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2, mod) : 1) % mod;
}

int inv(int p, int mod)
{
    return qpow(p, mod - 2, mod);
}

int check(int p0, int q)
{
    int v0 = a[p0];
    int len = 1;
    int v = v0 * q % p;
    for (int i = p0 + 1; i <= n; i++)
        if (a[i] == v)
        {
            ++len;
            v = v * q % p;
        }
    int iq = inv(q, p);
    v = v0 * iq % p;
    for (int i = p0 - 1; i >= 1; i--)
        if (a[i] == v)
        {
            ++len;
            v = v * iq % p;
        }
    return len;
}

void solve()
{
    cin >> n >> p;
    memset(a, 0, sizeof a);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int _ = 1; _ <= 120; _++)
    {
        int p0 = rand() * rand() % n + 1;
        if (p0 + 1 <= n)
            ans = max(ans, check(p0, a[p0 + 1] * inv(a[p0], p) % p));
        if (p0 + 2 <= n)
            ans = max(ans, check(p0, a[p0 + 2] * inv(a[p0], p) % p));
    }
    if (ans < (n + 1) / 2)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

signed main()
{
    srand(time(NULL));
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}