jzoj4915. 【GDOI2017模拟12.9】最长不下降子序列（数列）

旧城等待， 2021-12-23 05:37 153阅读 0赞

## 题面 ##

![1442599-20190224202449356-605254199.png][]

![1442599-20190224202451141-1794312829.png][]

![1442599-20190224202454333-131365192.png][]

## 题解 ##

调了好几个小时啊……话说我考试的时候脑子里到底在想啥……

首先，这个数列肯定是有循环节的，而且循环节的长度\\(T\\)不会超过\\(D\\)

那么就可以把数列分成三份，\\(L+S+R\\)，其中\\(L,R\\)为左右两边剩下的，\\(S\\)为中间的循环数列。对于\\(L\\)，算出\\(pre\_i\\)表示最后一个数小于等于\\(i\\)的最长的子序列的长度，对于\\(R\\)算出\\(suf\_i\\)表示最开始的一个数大于等于\\(i\\)的最长的子序列的长度。然后用中间出现过的每一个数以及\\(pre\\)和\\(suf\\)更新答案就好了

然后中间的部分要怎么计算呢？

通过观察可以发现，设中间的\\(LIS\\)长度为\\(len\\)，那么这个\\(LIS\\)最多只有\\(L-1\\)对两两不一样的。而且如果这个数列是长成\\(xu+F+v\\)的形式，就是\\(x\\)个\\(u\\)加上一串\\(F\\)加上一个\\(v\\)，那么它也可以变成\\(u+F+xv\\)的形式，也就是说相等的数字无论与谁相等都是不会影响结果的

那么我们考虑把从\\(S\\)中选取的\\(LIS\\)分成三部分\\(LL+k\\times SS+RR\\)，其中\\(k\\times SS\\)就是那段相等的部分。又因为每个周期中至少选择一个数，所以\\(LL\\)和\\(RR\\)最多包含\\(T\\)个周期，那么长度不会超过\\(T^2\\)，用和之前算\\(L\\)和\\(R\\)一样的方法计算就行了

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define ll long long
    #define inf 0x3f3f3f3f
    #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
    #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
    using namespace std;
    const int N=1e6+5;
    int p,q,t,h,A,B,C,D,l,r,len,v[N],b[N],pos[155],Pre[155],suf[155];ll n,res,k,sz,dp[N];
    inline bool in(R int x){return x>=l&&x<=r;}
    void qwq(){
        for(p=1;!pos[t];t=(A*t*t+B*t+C)%D,++p)v[p]=t,pos[t]=p;
        sz=p-pos[t],k=(n-p+1)/sz+1;
        fp(fff,1,sz-1)for(R int i=1;i<=sz;++i,t=(A*t*t+B*t+C)%D,++p)v[p]=t;
        --p,len=0,b[0]=-inf;
        fp(i,1,p){
            if(v[i]>=b[len])b[++len]=v[i],cmax(Pre[v[i]],len);
            else{
                int g=upper_bound(b+1,b+1+len,v[i])-b;
                b[g]=v[i],cmax(Pre[v[i]],g);
            }
        }
        p=1,h=t;
        fp(fff,1,sz)for(R int i=1;i<=sz;++i,t=(A*t*t+B*t+C)%D,++p)v[p]=-t;
        for(R int i=1,j=(n-pos[t]+1)%sz;i<=j;++i,++p,h=(A*h*h+B*h+C)%D)v[p]=-h;
        --p,len=0;
        reverse(v+1,v+p+1),b[0]=-inf;
        fp(i,1,p){
            if(v[i]>=b[len])b[++len]=v[i],cmax(suf[-v[i]],len);
            else{
                int g=upper_bound(b+1,b+1+len,v[i])-b;
                b[g]=v[i],cmax(suf[-v[i]],g);
            }
        }
        k-=sz+sz;
        fp(i,1,D-1)cmax(Pre[i],Pre[i-1]);
        fd(i,D-2,0)cmax(suf[i],suf[i+1]);
        h=(A*t*t+B*t+C)%D;
        for(;h!=t;h=(A*h*h+B*h+C)%D)cmax(res,k+Pre[h]+suf[h]);
        cmax(res,k+Pre[t]+suf[t]);
        printf("%lld\n",res);
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        freopen("lis.in","r",stdin);
        freopen("lis.out","w",stdout);
        scanf("%lld%d%d%d%d%d",&n,&t,&A,&B,&C,&D);
        if(n<=D*D*2+D+D+D){
            b[0]=-inf;
            fp(i,1,n){
                if(t>=b[len])b[++len]=t,dp[i]=len;
                else{
                    int k=upper_bound(b+1,b+1+len,t)-b;
                    b[k]=t,dp[i]=k;
                }
                t=(A*t*t+B*t+C)%D;
            }printf("%d\n",len);
        }else qwq();
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10427777.html

[1442599-20190224202449356-605254199.png]: /images/20211223/90d54cdbc44d4e8fbef400630bc0aec0.png
[1442599-20190224202451141-1794312829.png]: /images/20211223/636cd712f1084247af3e1166e73564e2.png
[1442599-20190224202454333-131365192.png]: /images/20211223/f12d8b2e66d54e08b9da14d119a350a6.png