目录

F Longest Common Subsequence

题目

​ 有长为n的序列a,长为m的序列m,利用xi+1=(ax2+bx+c)modpx_{i+1}=(ax^2+bx+c)modp依次生成序列a和b。求a和b的最长公共子序列。

分析

方法一

​ 易知当xi=xjx_i=x_j时,则f(xi)=f(xj)f(x_i)=f(x_j)。所以记录每一次x最先出现的位置,ans=max(ans,min(ni+1,mj+1))ans=max(ans,min(n-i+1,m-j+1))

方法二

​ 利用求最长公共子序列的优化方法。空间复杂度O(n+m),时间复杂度O((n+m)log(n+m))

代码

方法一

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=1e6+10,M=1e6+5;

int n,m,k,p,a,b,c;
int A[N],B[N];

inline int get(ll x) {
    return (a*x%p*x%p+b*x%p+c)%p;
}

void solve() {
    int x;
    cin>>n>>m>>p>>x>>a>>b>>c;
    unordered_map<int,int> ma;
    for(int i=1;i<=n;i++) {
         x=A[i]; A[i]=get(x);
        if(ma.find(x)==ma.end()) ma[x]=i;
    }
    int ans=0;
    for(int i=1;i<=m;i++) {
        x=get(x);
        if(ma.find(x)!=ma.end()) {
            int t=ma[x];
            ans=max(ans,min(n-t+1,m-i+1));
        }
    }
    cout<<ans<<endl;
}

int main(){
    //freopen("data.in","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
	while(T--) {
        //cout<<"Case#"<<T<<":\n";
        solve();
	}
	return 0;
}

方法二

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=1e6+10,M=1e6+5;

ll n,m,p,x,a,b,c;
int A[N],B[N];
vector<int> nums;

int lis(vector<int>& nums) {
    if(nums.size()<2) return nums.size();
    vector<int> seq{nums[0]};
    for(int i=1; i<nums.size(); i++)
    {
        int idx = lower_bound(seq.begin(), seq.end(), nums[i])-seq.begin();
        if(idx==seq.size()) seq.push_back(nums[i]);
        else seq[idx]=nums[i];
    }
    return seq.size();
}

int lcs1() {
	unordered_map<int, vector<int>> has;	// 统计字符出现的下标
	for(int i=m; i>=1; i--) has[B[i]].push_back(i);
    nums.clear();
	for(int i=1; i<=n; i++)
		for(int j=0; j<has[A[i]].size(); j++) nums.push_back(has[A[i]][j]);
	return lis(nums);	// 求seq的最长上升子序列即是答案
}

int get(ll x) {
    return (a*x%p*x%p+b*x%p+c)%p;
}

void solve() {
    cin>>n>>m>>p>>x>>a>>b>>c;
    for(int i=1;i<=n;i++) {
        x = get(x); A[i]=x;
    }
    for(int i=1;i<=m;i++) {
        x=get(x); B[i]=x;
    }
    int ans=lcs1();
    cout<<ans<<endl;
}

int main(){
    //freopen("data.in","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
	while(T--) {
        solve();
	}
	return 0;
}