“蔚来杯“2022牛客暑期多校训练营8 补题题解（F）
“蔚来杯“2022牛客暑期多校训练营8
- F Longest Common Subsequence
比赛地址
这场好像很难，暂且只补两题吧
F Longest Common Subsequence
比赛时候队友找出规律了，但是想了太多没写出来，还是答案有错，看了大佬的题解不禁惊叹真是简洁之美啊，自己要学的还有很多
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, m;
ll p, x, a, b, c;
map<int, int>mp;
int A[N], B[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin>>T;
while(T -- ){
mp.clear();
cin>>n>>m>>p>>x>>a>>b>>c;
for(int i = 1; i <= n; i ++ ){
A[i] = x = (a * x % p * x + b * x + c) % p;
}
for(int i = 1; i <= m; i ++ ){
B[i] = x = (a * x % p * x + b * x + c) % p;
}
//注意mp.count(A[i])比直接mp.[A[i]]快，很神奇的特性
for(int i = 1; i <= n; i ++ ){
if(!mp.count(A[i])) mp[A[i]] = i; //记录这个数第一次出现的位置
}
int asnm = 0;
for(int i = 1; i <= m; i ++ ){
if(mp.count(B[i])) asnm = max(asnm, min(n - mp[B[i]] + 1, m - i + 1));
}
cout<<asnm<<endl;
}
return 0;
}