“蔚来杯“2022牛客暑期多校训练营8 补题题解（F）

---

比赛地址

这场好像很难，暂且只补两题吧

F Longest Common Subsequence

比赛时候队友找出规律了，但是想了太多没写出来，还是答案有错，看了大佬的题解不禁惊叹真是简洁之美啊，自己要学的还有很多

#include

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43