2022 年牛客多校第八场 F 题题解

F Longest Common Subsequence

题意：给定两个长度分别为 $n,mn,m$ 的序列 $S,TS,T$，问其最长公共子序列长度。其中 $SS$ 与 $TT$ 都是通过 $x_{i+1}=f(x_i)=(a{x}_i^2+b{x}_i+c)\mathrm{m}\mathrm{o}\mathrm{d}px\_\{i+1\}=f(x\_i)=(ax\_i^2+bx\_i+c)\; \backslash bmod\; p$ 迭代产生。$\mathrm{\mid }S\mathrm{\mid },\mathrm{\mid }T\mathrm{\mid }\le 1\times 10^6|S|,|T|\; \backslash leq\; 1\backslash times\; 10^6$。

解法：容易注意到，若 $S_i=T_{j}S\_i=T\_j$，则从这两个位置开始，后面都一定完全一样，因而对答案的贡献为 $\min (n-i+1,m-j+1)\backslash min(n-i+1,m-j+1)$。因而可以直接暴力使用 map 记忆 $SS$ 中每个元素的第一次出现位置。这样的时间复杂度为 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$。

基于以上性质，可以发现二者匹配的一定是一个后缀。因而对两个串进行翻转然后跑对两个串依次做一次字典串，利用 KMP 也可以得到答案。这样的复杂度为 $\mathcal{O}(n)\backslash mathcal\; O(n)$。原题数据范围是 $1\times 10^{7}1\backslash times\; 10^7$，为了降低难度于是减少了一个零。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
long long s[N + 5], t[N + 5];

int main()
{
    int caset, n, m;
    long long p, a, b, c, x;
    scanf("%d", &caset);
    while(caset--)
    {
        map<long long, int> pos;
        scanf("%d%d%lld%lld%lld%lld%lld", &n, &m, &p, &x, &a, &b, &c);
        for (int i = 1; i <= n;i++)
        {
            s[i] = x = (a * x % p * x % p + b * x % p + c) % p;
            if (pos.count(s[i]) == 0)
                pos[s[i]] = i;
        }
        int ans = 0;
        for (int i = 1; i <= m;i++)
        {
            t[i] = x = (a * x % p * x % p + b * x % p + c) % p;
            if (pos.count(x))
                ans = max(ans, min(m - i + 1, n - pos[x] + 1));
        }
        printf("%d\n", ans);
    }
    return 0;
}