2022牛客多校·第八场

垃圾场...

比赛链接："蔚来杯"2022牛客暑期多校训练营8

F.Longest Common Subsequence（签到）

题意：给你n,m,p,x,a,b,c表示的是给你两个序列s,t分别长度为n和m，序列不是直接输入给你的，而是需要进行计算：
$$
x:=ax^2+bx+c
$$

求两个序列的最长公共子序列

思路：既然是给出规定的，那么就是找循环节，如果出现过一样的那么就进行更新答案，如果没有出现过那么当然是0。

那么如何找呢，我发现两种情况都可以用一个式子表示，主要是有循环节在s上以及一部分在s上一部分在t上。

我用map来存一个数字的出现的最早的地方,然后找在t中每次的x是否出现过，如果出现过的话则比较两个序列的最小值

• s出现的可作为答案的长度为：n-mp[x]+1
• t出现的可作为答案的长度为：m-i+1

这场唯一有教训的地方就是，当计算$ax^2$的时候，但是他们的范围又是1e9的时候，需要乘一下取一次模，而不是a*x*x%p，而应该是a*x%p*x%p。

代码：

map<int,int> mp;
inline int calc(int x)
{
    return (a*x%p*x%p+b*x%p+c)%p;
}
inline void Case_Test()
{
    cin>>n>>m>>p>>x>>a>>b>>c;
    mp.clear();
    for (int i=1;i<=n;i++)
    {
        x = calc(x);
        if (mp.find(x)==mp.end()) mp[x]=i;
    }
    ans = 0;
    for (int i=1;i<=m;i++)
    {
        x = calc(x);
        if (mp.find(x)==mp.end()) continue;
        ans = Max(ans, Min(n-mp[x]+1,m-i+1));//两段取min
    }
    cout<<ans<<endl;
}