F Longest Common Subsequence

题意:给定两个长度分别为 n,mn,m 的序列 S,TS,T,问其最长公共子序列长度。其中 SSTT 都是通过 xi+1=f(xi)=(axi2+bxi+c)modpx_{i+1}=f(x_i)=(ax_i^2+bx_i+c) \bmod p 迭代产生。S,T1×106|S|,|T| \leq 1\times 10^6

解法:容易注意到,若 Si=TjS_i=T_j,则从这两个位置开始,后面都一定完全一样,因而对答案的贡献为 min(ni+1,mj+1)\min(n-i+1,m-j+1)。因而可以直接暴力使用 map 记忆 SS 中每个元素的第一次出现位置。这样的时间复杂度为 O(nlogn)\mathcal O(n \log n)

基于以上性质,可以发现二者匹配的一定是一个后缀。因而对两个串进行翻转然后跑对两个串依次做一次字典串,利用 KMP 也可以得到答案。这样的复杂度为 O(n)\mathcal O(n)。原题数据范围是 1×1071\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;
}