更差的閱讀體驗

我們會發現，如果我們知道了等比數列的公比，問題會容易很多。具體地，如果我們知道等比子序列的開頭元素，然后我們往后掃。假設我們目前等比子序列的最后一個元素是 \(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;
}