NOIP 模拟 $29\; \rm 最长不下降子序列$

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++

    struct nanfeng_stream{

        template<typename T>inline nanfeng_stream &operator>>(T &x) {

            ri f(1);x=0;register char ch(gc());

            while(!isdigit(ch)) {if (ch=='-') f=0;ch=gc();}

            while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

            return x=f?x:-x,*this;

        }

    }cin;

}

using IO::cin;

namespace nanfeng{

    #define FI FILE *IN

    #define FO FILE *OUT

    template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}

    template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}

    typedef long long ll;

    static const int N=1e5+7;

    int num[N*10],vis[N],dp[N*10],dpt[N],dpf[N],nm[N],suf[N],bg,lea,sl,len,cnt,t0,a,b,c,d;

    ll n;

    struct BIT{

        #define lowbit(x) ((x)&-(x))

        int c[N];

        inline void init() {memset(c,0,sizeof(int)*300);}

        inline void update(int x,int k) {for (ri i(x);i<=d;i+=lowbit(x)) c[i]=cmax(c[i],k);}

        inline int query(int x) {

            int res(0);

            for (ri i(x);i;i-=lowbit(i)) res=cmax(res,c[i]);

            return res;

        }

    }B;

    inline int main() {

        //FI=freopen("nanfeng.in","r",stdin);

        //FO=freopen("nanfeng.out","w",stdout);

        cin >> n >> t0 >> a >> b >> c >> d;

        vis[num[p(cnt)]=t0]=1;

        while(1) {

            p(cnt);

            num[cnt]=(a*num[cnt-1]*num[cnt-1]+b*num[cnt-1]+c)%d;

            if (vis[num[cnt]]) {len=cnt-vis[num[cnt]];break;}

            vis[num[cnt]]=cnt;

        }

        bg=vis[num[cnt]]-1;

        if (n<=(int)1e6) {

            ri ans(0);

            for (ri i(cnt+1);i<=n;p(i)) num[i]=(a*num[i-1]*num[i-1]+b*num[i-1]+c)%d;

            for (ri i(1);i<=n;p(i)) {

                dp[i]=B.query(num[i]+1)+1;

                B.update(num[i]+1,dp[i]);

                ans=cmax(ans,dp[i]);

            }

            printf("%d\n",ans);

        } else {

            for (ri i(1);i<=len;p(i)) nm[i]=num[bg+i];

            for (ri i(2);i<=len;p(i))

                for (ri j(1);j<=len;p(j)) nm[(i-1)*len+j]=nm[j];

            ll aln=(n-bg)/len-len,ans(0);

            sl=(int)(n-(aln+len)*len-bg);

            for (ri i(1);i<=sl;p(i)) suf[i]=nm[i];

            for (ri i(1);i<=bg;p(i)) {

                dpf[i]=B.query(num[i]+1)+1;

                B.update(num[i]+1,dpf[i]);

            }

            lea=len*len;

            for (ri i(0);i<=bg;p(i)) {

                B.init();

                ri res(0),mn(INT_MAX);

                B.update(num[i]+1,dpf[i]);

                ans=cmax(ans,(ll)dpf[i]);

                for (ri j(1);j<=lea;p(j)) {

                    if (nm[j]<num[i]) continue;

                    dp[j]=B.query(nm[j]+1)+1;

                    B.update(nm[j]+1,dp[j]);

                    res=cmax(res,dp[j]);

                }

                for (ri j(lea-len+1);j<=lea;p(j))

                    if (dp[j]==res) mn=cmin(mn,nm[j]);

                B.init();

                if (res) ans=cmax(ans,aln+res),B.update(mn+1,res);

                else mn=num[i];

                for (ri j(1);j<=sl;p(j)) {

                    if (suf[j]<mn) continue;

                    dpt[j]=B.query(suf[j]+1)+1;

                    B.update(suf[j]+1,dpt[j]);

                    ans=cmax(ans,aln+dpt[j]);

                }

            }

            printf("%lld\n",ans);

        }

        return 0;

    }

}

int main() {return nanfeng::main();}