题解：P13945 [EC Final 2019] King

· · 题解

更好的阅读体验

我们会发现，如果我们知道了等比数列的公比，问题会容易很多。具体地，如果我们知道等比子序列的开头元素，然后我们往后扫。假设我们目前等比子序列的最后一个元素是 a_i，公比为 m，则我们往后找到第一个 a_j 使得 a_i \times m = a_j，那么我们直接把 j 加入子序列即可。

但是不知道公比就比较困难。

关注到答案特殊的输出格式：只有答案 \ge \frac{n}{2} 我们才要输出。这意味着，原来序列中离得很近的两个元素他们大概率是相邻的。由于答案 \ge \frac{n}{2}，我们充分发扬人类智慧，先随机出一个 i，然后以 a_{i+1} \times a_{i}^{-1} 为公比跑一次，再以 a_{i+2} \times a_{i}^{-1} 跑一次。

我们容易发现，一个数字有 \frac{1}{2} 的概率出现在最长的子序列中，所以我们随机的正确率为 \frac{1}{4}，随个 \lambda = 100 次差不多就对了。

那么这道题就做完了，复杂度 O(\lambda n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
using namespace std;
int T,n,MOD,a[N],ans;
mt19937 rnd(time(0));
inline int get(){return (((int)rnd())%n+n)%n+1;}
int qpow(int x,int y=MOD-2)
{
    if(y==0)return 1;if(y==1)return x%MOD;
    int ret=qpow(x,y>>1);return ret*ret%MOD*qpow(x,y&1)%MOD;
}
void solve(int x,int y,int m)
{
    int ret=2,now=a[x],im=qpow(m);
    for(int i=x-1;i;i--)
        if(im*now%MOD==a[i])now=a[i],ret++;
    now=a[y];
    for(int i=y+1;i<=n;i++)
        if(m*now%MOD==a[i])now=a[i],ret++;
    if(ret*2>=n)ans=max(ret,ans);
}
main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&MOD),ans=-1;
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=100;i++)
        {
            int pos=get();
            if(pos+1<=n)solve(pos,pos+1,a[pos+1]*qpow(a[pos])%MOD);
            if(pos+2<=n)solve(pos,pos+2,a[pos+2]*qpow(a[pos])%MOD);
        }
        printf("%lld\n",ans);
    }
    return 0;
}