F Longest Common Subsequence
题意:给定两个长度分别为 的序列 ,问其最长公共子序列长度。其中 与 都是通过 迭代产生。。
解法:容易注意到,若 ,则从这两个位置开始,后面都一定完全一样,因而对答案的贡献为 。因而可以直接暴力使用 map
记忆 中每个元素的第一次出现位置。这样的时间复杂度为 。
基于以上性质,可以发现二者匹配的一定是一个后缀。因而对两个串进行翻转然后跑对两个串依次做一次字典串,利用 KMP 也可以得到答案。这样的复杂度为 。原题数据范围是 ,为了降低难度于是减少了一个零。
#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;
}