序列题解

lewisak / 2024-11-26 / 原文

哈哈哈我也有个唐氏做法

也是考虑一个朴素 dp ，设 $dp_{i}$ 表示以 $i$ 结尾的字串最长是多少，则容易想到若 $a_{i-1}$ 和 $a_i$ 是等比数列的一部分就一定能从 $dp_{i-1}$ 转移到 $dp_i$，证明最后讲

那么如何判断 $a_{i-1}$ 和 $a_i$ 是否为等比数列的一部分呢？

首先设 $d=max(a_i,a_{i-1}),x=min(a_i,a_{i-1}),c=d/x$

变量名记忆方法

其实就是大，小，除的拼音首字母啦qwq

那么首先发现，如果 $d\%x≠0$ 那就明显不是等比数列的一部分
接着考虑 $d==x$ 的情况，发现若$dp_{i-1}$ 是通过相同转移的则 $dp_{i}=dp_{i-1}+1$，否则 $dp_{i}=dp_2$
但是这就很尬了呀，我咋知道 $dp{i-1}$ 是从那里转移的呢？
没有关系，直接新开一个数组 $f_i$ 表示 $dp_i$ 是从哪里转移的（这个数组是一个伏笔）
最后就是正常情况了，很容易发现若 $c$ 能拆解成 $a^b$ ，那么就能转移成功……吗？
发现必须和 $dp_{i-1}$ 转移来源的 $a$ 相同，所以fw回收再立用一下，使用 $f$ 数组来存 $a$

最后的细节：和dyc一样离散化来去重

妈

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100100],n,dp[100100],inv[100100],tot=0,b[100100],lyh[100100],yz[170],f[100100],vis[100100],cnt=1;
int qpow(int x,int y){
	int aaa=1;
	while(y){
		if(y&1){
			aaa*=x;
		}
		x*=x;
		y>>=1;
	}
	return aaa;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int tt=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		lyh[i]=lower_bound(b+1,b+1+tt,a[i])-b;
	}
	//↑离散化 
	inv[++tot]=2;
	for(int i=3;i<=1000;i++){
		for(int j=2;j<i;j++){
			if(i%j==0){
				break;
			}
			if(j==i-1){
				inv[++tot]=i;
			}
		}
	}
	//↑预处理1000以内的质数 
	dp[1]=1;
	vis[lyh[1]]=1;
	//vis[i]代表 i 是否用过 
	for(int i=2;i<=n;i++){
		int bbh=1;
		dp[i]=1;
		int x=min(a[i],a[i-1]),d=max(a[i],a[i-1]);
		if(d%x){
			cnt++;
			//cnt表示版本号 
			vis[lyh[i]]=cnt;
			continue;
		}
		if(d==x){
			if(!f[i-1]){
				dp[i]=dp[i-1]+1;
			}
			else{
				dp[i]=2;
				cnt++;
				vis[lyh[i]]=cnt;
			}
			continue;
		} 
		int c=d/x,t=0,tflag=0;
		for(int j=1;j<=tot;j++){
			yz[j]=0;
		}
		int maxn=0;
		for(int j=1;j<=tot;j++){
			while(c%inv[j]==0){
				yz[j]++;
				c/=inv[j];
			}
			maxn=max(maxn,yz[j]);
		}
		//↑分解质因数 
		if(c!=1){
			cnt++;
			vis[lyh[i]]=cnt;
			continue;
		}
		for(int k=1;k<=maxn;k++){
			int flag=1,sum=1;
			for(int j=1;j<=tot;j++){
				if(yz[j]%k){
					flag=0;
					break;
				}
				sum*=qpow(inv[j],yz[j]/k);
				if(sum>1000){
					flag=0;
					break;
				}
			}
			if(flag){
				tflag=1;
				f[i]=sum;
				if((sum==f[i-1]||!f[i-1])&&vis[lyh[i]]!=cnt){
					dp[i]=dp[i-1]+1;
					vis[lyh[i]]=cnt;
				}
				//↑成功转移 
			}
		}
		if(tflag){
			if(dp[i]<2){
				dp[i]=2;
				cnt++;
				vis[lyh[i]]=cnt;
			}
		}
		else{
			cnt++;
			vis[lyh[i]]=cnt;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}