快手笔试，A卷第三题，这个思路哪里出了问题？

刚结束的快手笔试，前两道题特别简单，后两道题特别难=-=

第四题是一道计算几何，微积分好久不摸了，勉强用暴力骗到20分；

第三题：

给定0 < S, A, B, P < 200000，以如下方式生成序列：

1）arr[0] = S, i = 1

2）x = (arr[i-1]*A+B)%P,

3）若x已在arr[0]~arr[i-1]中出现两次则终止，否则i=i+1, arr[i] = x，转1

现在给出两组S A B P，求生成的两个序列的最长公共子序列的长度

——————————————————————————————

记第一序列为a[]，第二序列为b[]。

序列的长度最长为399998，显然不能直接求LCS。由于序列的每个元素都在[0, P)中，且最多出现两次，故考虑对于每个 $i \in [0, P)$ 记录它在第二序列中出现的位置pos[i][0]和pos[i][1]。对于出现不足两次的情况，用-1标记。（即，若只出现一次，则pos[i][1] = -1，若不出现，则pos[i][0] = pos[i][1] = -1）

由于最长公共子序列的各个元素在原序列中的下标都是递增的，那么可以把a[]和b[]的LCS转化为求 $F = [f_0, f_1, \cdots, f_{n-1}]$ 的最长上升子序列，其中

$f_i$ 有 $pos\left[a[i]\right]\left[0\right]$ 和 $pos\left[a[i]\right][1]$ 两个可选值。

而最长上升子序列是可以O(nlogn)求的，不会超时：

$mx_{i00} = max(dp[j][0]+1): pos[a[j]][0]\neq -1 \wedge pos[a[j]][0] < pos[a[i]][0] \wedge j<i$
$mx_{i10} = max(dp[j][1]+1): pos[a[j]][1]\neq -1 \wedge pos[a[j]][1] < pos[a[i]][0] \wedge j<i$
$dp\left[i\right][0]=max(\mathbf{1}(pos[a[i]][0] \neq -1), mx_{i00}, mx_{i10})$

同理求得dp[i][1]

———————————————————————————————

但是，利用这个思路写出来的代码并没有通过，通过率0%。问题出在了哪里？请各位大佬赐教QwQ

#include <iostream>
#include <cstring>
typedef long long LL;
const int MAXP = 2e5+5;
int a[MAXP*3], b[MAXP*3], dp[MAXP][2];
int found[MAXP][2];
int min_b[MAXP*3];
using namespace std;
void Generate(int S, int A, int B, int P, char arr_mark, int &n){
    int *arr = (arr_mark == 'a' ? a : b);
    int vis[MAXP];
    memset(vis, 0, sizeof(vis));
    if(arr_mark == 'b'){
        memset(found, -1, sizeof(found));
    }
    arr[0] = S;
    if(arr_mark == 'b'){
        found[S][0] = 0;
    }
    vis[S] = 1;
    n = 1;
    for(;; n++){
        int tmp = int((LL(arr[n-1])*A+B)%P);
        if(vis[tmp] == 2)break;
        if(arr_mark == 'b'){
            found[tmp][vis[tmp]] = n;
        }
        vis[tmp] ++;
        arr[n] = tmp;
    }
}
int BSearch(int l, int r, int k, int* arr){
    while (l < r){
        int mid = (l+r)/2;
        if(arr[mid] >= k) r = mid;
        else l = mid+1;
    }
    //cout << l << endl;
    return l-1;
}
int main(){
    int T,S,A,B,P,Sb,Ab,Bb,Pb, na, nb;
    cin >> T;
    while(T--){
        na = 0;
        nb = 0;
        cin >> S >> A >> B >> P;
        Generate(S, A, B, P, 'a', na);
        cin >> S >> A >> B >> P;
        Generate(S, A, B, P, 'b', nb);
        //for(int i = 0; i < na; i++)cout << a[i] << ' ';
        //cout << endl;
        //for(int i = 0; i < nb; i++)cout << b[i] << ' ';
        //cout << endl;
        memset(dp, 0, sizeof(dp));
        memset(min_b, 0x3f, sizeof(min_b));
        min_b[0] = -1;
        for(int i = 0; i < na; i++){
            int fd0 = found[a[i]][0];
            int fd1 = found[a[i]][1];
            //cout << "I = " << i << " FD0 = " << fd0 << " FD1 = " << fd1 <<endl;
            dp[i][0] = dp[i][1] = 0;
            if(fd0 != -1){
                dp[i][0] = 1;
                min_b[1] = min(min_b[1], fd0);
            }
            if(fd1 != -1){
                dp[i][1] = 1;
                min_b[1] = min(min_b[1], fd1);
            }
            if(i > 0){
                if(fd0 != -1){
                    int idx = BSearch(0, 3*MAXP-1, fd0, min_b);
                    dp[i][0] = idx+1;
                    min_b[dp[i][0]] = min(min_b[dp[i][0]], fd0);
                }
                if(fd1 != -1){
                    int idx = BSearch(0, 3*MAXP-1, fd1, min_b);
                    dp[i][1] = idx+1;
                     min_b[dp[i][1]] = min(min_b[dp[i][1]], fd1);
                }
            }
            //cout << "I = " << i << " dp0 = " << dp[i][0] << " dp1 = " << dp[i][1] <<endl;

        }
        cout << max(dp[na-1][0], dp[na-1][1]) <<endl;

    }
    return 0;
}

#快手笔试##快手##笔试题目#