更差的阅读体验
我们会发现，如果我们知道了等比数列的公比，问题会容易很多。具体地，如果我们知道等比子序列的开头元素，然后我们往后扫。假设我们目前等比子序列的最后一个元素是 \(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;
}