F-Longest Common Subsequence

来源: 牛客多校训练营8 算法: LCS 题目链接: https://ac.nowcoder.com/acm/contest/33193/F 补完: Yes 完成时间: August 13, 2022

题解

给公式

\[ x_{i+1}=(ax_i^2+bx_i+c)\%P \]

给参数\(n,m,P,x_0,a,b,c\)

取\(x_1\sim x_n\)为第一个序列, 取\(x_{n+1}\sim x_{n+m}\)为第二个序列, 求最长公共子序列.

易发现\(x_i\)在迭代过程中可能回归, 当有\(x_i==x_j\)时, 以\(x_i\)为起点的\(t=j-i\)个数字为一个循环节, 自\(x_i\)开始反复出现, 有\(x_{i+k}==x_{i+k+lt}(k≤t,l\in N)\).定义第一个循环节的起点为\(x_{begin}\)

故若有循环节起点\(x_{begin}\)落在\(x_1\sim x_n\)范围内且循环节终点落在\(x_{1}\sim x_{n+m}\)范围内时, 两序列会有公共子序列,且公共子序列为循环结的不断重复.若无循环节在范围内出现则无公共子序列.

以\(x_{begin}\)为起点的循环节不断重复出现, 若第一个序列的最后一个元素是\(x_{n}=x_{begin+k}\), 则第二个序列的第一个元素是\(x_{n+1}=x_{begin+k+1}\), 则第二个序列第第一次出现循环节第一个元素\(x_{begin}\)的位置是\(x_{begin}=x_{n+(t-k)}\).或者说会有循环节被\(x_n\)打断, 其左边有\(llen\)个元素, 其右边有\(rlen\)个元素,即\(llen = k,rlen=t-k\).

考虑优先匹配第一个序列中的循环节, 则确定公共子序列的起点元素为\(x_{begin}\),

对应第一个序列中最大可能匹配起点为\(x_i\), 最大可能匹配终点为\(x_n\). 故在第一个序列中有最大匹配长度\(nlen = n-begin+1\).

对应到第二个序列中, 最大可能匹配起点为\(x_{n+(t-k)}\), 最大可能匹配终点为\(x_{n+m}\). 故在第二个序列中有最大匹配长度\(mlen-rlen\).

取小者为最长公共子序列长度.

\[ \min(mlen-rlen,nlen) \]
考虑优先匹配第二个序列中的循环节, 则确定公共子序列的起点元素为\(x_{llen+1}\),

对应第一个序列中最大可能匹配起点为\(x_{begin+llen}\), 最大可能匹配终点为\(x_n\), 故子第一个序列中有最大匹配长度\(nlen-llen\)

对应到第二个序列中, 最大可能匹配起点为\(x_{n+1}\), 最大可能匹配终点为\(x_{n+m}\). 故在第二个序列中有最大匹配长度\(mlen\).

取小者为最长公共子序列长度.

\[ \min(nlen-llen,mlen) \]

两者再取大者即为最长公共子序列长度

\[ \max\left(\min(mlen-rlen,nlen),\min(nlen-llen,mlen)\right) \]

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

unordered_map<ll, ll> mmap;
ll n,m,P,x,a,b,c;

ll add(ll a, ll b){
    return (a+b)%P;
}

ll mul(ll a, ll b){
    return (a*b)%P;
}

ll next(ll x){
    return add(add(mul(a,mul(x,x)),mul(b,x)),c);
}

void solve() {
    mmap.clear();
    cin>>n>>m>>P>>x>>a>>b>>c;
    for (ll i = 1; i <= n+m; i++){
        x = next(x);
        if (mmap[x] != 0) {
            ll begin = mmap[x];
            if(begin>n)break;
            ll t = i - begin;
            ll nlen = n-begin+1;
            ll llen = nlen%t;
            ll rlen = t - llen;
            cout<<max(min(nlen-llen,m),min(m-rlen,nlen))<<"\n";
            return;
        }
        else { 
            mmap[x] = i;
        }
    }
    cout<<"0"<<"\n";
}

int main() {
    int T = 1;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

Shelter

2022牛客多校训练营08

F-Longest Common Subsequence

题解

代码