跳转至

牛客多校8 F

Longest Common Subsequence

题目链接

题目大意

根据二次函数的构造方式，求出s和t的最长公共子序列长度

题解

由于两者的构造方式相同，因此只需找到一个相同的值，后面必然都是相同的，利用map记录值在第一个数组中出现的位置即可

代码

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1995781;

int n;
int m;
int x, a, b, c;
int p;

int lib[N];
int arr[N];
int dp[N];

int s[N];
int t[N];
int len = 0;

int tmparr[N];

bool vis[N];
int h[N];
int pos[N];

int find(int x)
{
    int k = (x % N + N) % N ;

    while(vis[k] && h[k] != x)
    {
        k ++ ;
        if(k == N ) k = 0;
    }

    return k;
}


void solve() {
    memset(vis, false, sizeof(vis));
    int temp;
    int len = 1;
    cin >> n >> m >> p >>  x >> a >> b >> c;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        x = (a * x % p * x % p + b * x % p + c) % p;
        int pp = find(x);
//         cout << pp << " ";
        if(!vis[pp]) {
            pos[pp] = i;
            h[pp] = x;
            vis[pp] = true;
        }
    }
//     cout << '\n';
    for (int i = 1; i <= m; i++) {
        x = (a * x % p * x % p + b * x % p + c) % p;
        int pp = find(x);
//         cout << pp << " ";
        if (vis[pp]) {
            ans = max(ans, min(n - pos[pp] + 1, m - i + 1));
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    //_ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}