随机化算法

给定一个序列$$a_1, a_2, ...a_n$$和一个质数p，从序列中选出若干个数，在顺序不变的情况下，构成模p下的等比数列。求最长的等比数列的长度。若长度小于n/2，输出-1，否则输出数列长度。

解：若存在该数列，则数列长度大于等于n/2，那么该数列相邻两个数在原数列上的位置间隔必定小于等于2。可以随机取两个位置间隔小于等于2的数，计算它们的模p下的比值q，并统计该数列长度。只要随机次数足够多，就有很大概率得到正确答案。（随机取1次是1/4，取n次成功概率为$$1 - (\frac{3}{4})^n$$

C++中<cstdlib>的rand随机数不够随机，可能会错。需要用C++11的std::mt19937（在random头文件中）（MersenneTwister算法的实现）

另一个类似的生成器是 mt19937_64 ，使用方式同 mt19937 ，但随机数范围扩大到了 unsigned long long 类型的取值范围。

#include <algorithm>
#include <cstdio>
#include <ctime>
#include <random>

constexpr int N = 200001;
long long a[N];

long long fast_pow(long long base, long long idx, long long mod) {
    if (base == 0 || mod == 1)
        return 0;
    long long result = 1;
    base %= mod;
    while (idx > 0) {
        if (idx & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        idx >>= 1;
    }
    return result;
}

long long solve(int left, int right, long long n, long long p) {
    long long q = a[right] * fast_pow(a[left], p - 2, p) % p;
    long long prev = a[right], length = 2;
    for (int i = right + 1; i <= n; ++i) {
        if (prev * q % p == a[i]) {
            prev = a[i];
            ++length;
        }
    }
    prev = a[left];
    for (int i = left - 1; i >= 1; --i) {
        if (a[i] * q % p == prev) {
            prev = a[i];
            ++length;
        }
    }
    return length;
}

int main() {

    std::mt19937 random(time(nullptr));
    int t;
    scanf("%d", &t);
    while (t--) {
        long long n;
        long long p;
        scanf("%lld %lld", &n, &p);
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", a + i);
        }

        long long result = 0;
        for (int i = 0; i < 200; ++i) {
            int left = std::min(random() % (n - 1) + 1, n - 1);
            result = std::max(result, solve(left, left + 1, n, p));
            if (left + 2 <= n)
                result = std::max(result, solve(left, left + 2, n, p));
        }
        if (result * 2 >= n)
            printf("%lld\n", result);
        else
            puts("-1");
    }
    return 0;
}