F题
题意:有两个序列s和t,给你n,m,x,p,a,b,c。n,m分别表示s和t长度,从s的第一个元素开始,s[1]=(a x^2+bx+c),然后x=s[1],然后这样一直迭代,就可以得到s和t序列,求两个序列的最长公共子序列。
思路:因为两个序列都是通过相同的公式计算的 所以两个序列只要出现了相同的数,那么这个数后面的序列一定是一样的,所以就题目就变为在s序列里找t序列里数字出现的第一次位置在哪。可以先对s序列排序,然后用二分找到答案。 #代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t1[1000005];
struct ww{
int num;
int i;
};
ww s[1000005];
int cmp(ww a,ww b)
{
if(a.num==b.num)
return a.i<b.i;
return a.num<b.num;
}
int main(){
int t;
cin>>t;
while(t--)
{
ll a,b,c,n,m,x,p,ans=0,l,r,mid,cnt=0;
cin>>n>>m>>p>>x>>a>>b>>c;
for(int i=0;i<n;i++)
s[i].num=(x*x%p*a%p+b*x%p+c)%p,x=s[i].num,s[i].i=i;
//%与*和/都是同一优先级,只要注意计算顺序就行了。
for(int i=0;i<m;i++)
t1[i]=(x*x%p*a%p+b*x%p+c)%p,x=t1[i];
sort(s,s+n,cmp);
//排完序用二分快速找到位置。
for(int i=0;i<m;i++)
{
l=0,r=n-1;
while(r>=l)
{
mid=(l+r)/2;
if(s[mid].num>=t1[i])
r=mid-1,cnt=mid;
else
l=mid+1;
}
if(s[cnt].num==t1[i])
{
ans=max(ans,min(m-i,n-s[cnt].i));
}
}
cout<<ans<<endl;
}
}