“蔚来杯“2022牛客暑期多校训练营8，签到题F

题号 标题 已通过代码 通过率 团队的状态
A Puzzle: X-Sums Sudoku 点击查看 19/55
B Puzzle: Patrick’s Parabox 点击查看 1/70
C Puzzle: Hearthstone 点击查看 2/105
D Poker Game: Decision 点击查看 311/3285
E Poker Game: Construction 点击查看 1/64
F Longest Common Subsequence 点击查看 1332/9989
G Lexicographic Comparison 点击查看 12/159
H Expression Evaluation 点击查看 2/26
I Equivalence in Connectivity 点击查看 39/252
J Symmetry: Tree 点击查看 17/336
K Symmetry: Convex 点击查看 2/12
L Symmetry: Closure 点击查看 1/21

F.Longest Common Subsequence

链接：https://ac.nowcoder.com/acm/contest/33193/F
来源：牛客网

题目描述
Given sequence ss of length nn and sequence tt of length mm, find the length of the longest common subsequence of ss and tt.
输入描述:
There are multiple test cases. The first line of input contains an integer TT(1\le T\le 10^31≤T≤10
3
), the number of test cases.

For each test case:

The only line contains 77 integers, nn, mm, pp, xx, aa, bb, cc (1\le n1≤n, m\le 10^6m≤10
6
, 0\le x0≤x, aa, bb, c 9
). nn is the length of ss, mm is the length of tt.

To avoid large input, you should generate the sequences as follows:

For each i=1i=1, 22, \cdots⋯, nn in order, update xx to (ax^2+bx+c)\bmod p(ax
2
+bx+c)modp, and then set s_is
i
​
to xx. And then, for each i=1i=1, 22, \cdots⋯, mm in order, update xx to (ax^2+bx+c)\bmod p(ax
2
+bx+c)modp, and then set t_it
i
​
to xx.

It is guaranteed that the sum of nn and the sum of mm over all test cases does not exceed 10^610
6
.
输出描述:
For each test case:

Output an integer – the length of the longest common subsequence of ss and tt, in one line.
示例1
输入
复制
2
4 3 1024 1 1 1 1
3 4 1024 0 0 0 0
输出
复制
0
3
说明
In the first sample, s=[3,13,183,905]s=[3,13,183,905] and t=[731,565,303]t=[731,565,303].

In the second sample, s=[0,0,0]s=[0,0,0] and t=[0,0,0,0]t=[0,0,0,0].

题意：

• 给出n, m, p, x, a, b, c。 令$f(x)=(a{x}^2+bx+c)\%p$。
  让长为n的序列s，s[1]=f(x), s[2]=f(s[1]), s[3]=f(s[2])，依次递推。
  让长为m的序列t，t[1]=f(s[n]), t[2] = f(t[1]), t[3] = f(t[2])，依次类推。
• 最后求序列s和序列t的LCS（最长公共子序列）。

思路：

• 因为要%p，所以可以发现，到后面这两个序列都是循环的。换句话说，如果两个序列中有相同数字，那么后面的数字一定全一样。
• 开个map记录下序列s中每个数第一次出现的位置。对于t进行遍历的时候，找到这个数的位置，将序列t[j]与s[i]对上后，不难发现 [ t[j], m ] 与 [ s[i], n ] 这两个区间一定是一样的，因为都是往后无限循环，取个min就是LCS的大小。遍历一遍维护最大值即可。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;

int main(){
    LL T;  cin>>T;
    while(T--){
        LL n, m, p, x, a, b, c;  cin>>n>>m>>p>>x>>a>>b>>c;
        unordered_map<LL,LL>mp;        //每个数最早出现的位置
        for(LL i = 1; i <= n; i++){
            x = (a*x%p*x+b*x+c)%p;
            if(!mp.count(x))mp[x] = i;
        }
        LL ans = 0;
        for(LL i = 1; i <= m; i++){
            x = (a*x%p*x+b*x+c)%p;
            if(mp.count(x)){
                //LCS可选 [mp[x],n] 或 [i,m]
                ans = max(ans, min(n-mp[x], m-i)+1);
            }
        }
        cout<<ans<<"\n";
    }
    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