2018.07.22 bzoj3613: [Heoi2014]南园满地堆轻絮(逆序对结论题)

时间:2023-01-24 12:35:56

传送门

做这道题有一个显然的结论,就是要使这个数列单调不减,就要使所有逆序对保证单调不减,也就是求出所有逆序对的最大差值,然后除以2然后就没了。

代码如下:

#include<bits/stdc++.h>
#define N 5000005
using namespace std;
inline long long read(){
    long long ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
long long a[N],mod,sa,sb,sc,sd,maxn,ans;
int n;
inline long long fff(long long x){return (((sa*x%mod)*(x*x%mod))%mod+(sb*x%mod*x%mod)+(sc*x%mod)+sd)%mod;}
int main(){
    a[0]=0;
    scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&sa,&sb,&sc,&sd,&a[1],&mod),maxn=0,ans=0;
    maxn=max(maxn,a[1]);
    for(register int i=2;i<=n;++i)a[i]=(fff(a[i-1])+fff(a[i-2]))%mod,maxn=maxn>a[i]?maxn:a[i],ans=ans>maxn-a[i]+1?ans:maxn-a[i]+1;
    printf("%lld",ans>>1);
    return 0;
}