2022牛客多校第八场

F Longest Common Subsequence

题意：

给出初始x和a,b,c,p，通过x=( $a x^{2}$ + $b x$ + $c$ )%p不断更新的x构成长度n+m的序列，前n个数为一个序列，后m个数为另一个序列，问这两个序列的最长公共子序列长度。

思路：

打表找规律后发现，序列中会出现一个之前出现的数字，说明出现了循环，两个序列一旦出现相同的数，后面的数就一定相同。

第一个序列将每一个数出现的第一个位置存unordered_map容器，map会超时。 第二个序列遍历每个数开始的最长公共子序列长度。

代码；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+5;
ll p,x,a,b,c;
ll s[2000006];
int t,n,m; 
unordered_map<ll,ll> mp;
int main(){
    scanf("%d",&t);
    while(t--){
        mp.clear();
        scanf("%d%d",&n,&m);
        scanf("%lld%lld%lld%lld%lld",&p,&x,&a,&b,&c);
        s[0]=x;
        for(ll i=1;i<=n;i++){
            s[i]=(s[i-1]*a*s[i-1]+b*s[i-1]+c)%p;
            if(mp[s[i]]==0) mp[s[i]]=i;
        }
        ll ans=0;
        for(ll i=n+1;i<=m+n;i++){
            s[i]=(s[i-1]*a*s[i-1]+b*s[i-1]+c)%p;
            if(mp[s[i]]<0) break;
            if(mp[s[i]]>0) {
                ans=max(ans,min(n-mp[s[i]]+1,m+n-i+1));
                mp[s[i]]=-1;      
                     }
            
        }
        printf("%lld\n",ans);
    }
}