NC20012. [HEOI2014]南园满地堆轻絮
描述
输入描述
由于数据规模可能较大，因此采用如下方式生成数据。每个数据包含6个数：n,Sa,Sb,Sc,Sd,A[1],Mod,意为共有 n 个音符，第一个音符为 A[1]。生成规则如下：定义生成函数F(x) = Sa*x^3 + Sb*x^2 + Sc*x + Sd; 那么给出递推公式A[i] = F(A[i-1]) + F(A[i-2])，此处规定A[0]=0.由于中间过程的数可能会特别大，所以要求每一步与A中的每个数都对一个给定的数 Mod 取模。
输出描述
输出一行，包含一个正整数 Ans。
示例1
输入:
3 815 6901 3839 178 199 10007
输出:
1334
C++(g++ 7.5.0) 解法, 执行用时: 893ms, 内存消耗: 19964K, 提交时间: 2023-01-05 11:41:58
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 5005005
using namespace std;
int n,ans,a[M];
long long Sa,Sb,Sc,Sd,mod;
int F(int x)
{
long long re=Sd,temp=x;
re+=Sc*temp%mod;(temp*=x)%=mod;
re+=Sb*temp%mod;(temp*=x)%=mod;
re+=Sa*temp%mod;
return int(re%mod);
}
int main()
{
int i,max_val=0;
cin>>n>>Sa>>Sb>>Sc>>Sd>>a[1]>>mod;
for(i=2;i<=n;i++)
a[i]=(F(a[i-1])+F(a[i-2]))%mod;
for(i=1;i<=n;i++)
{
max_val=max(max_val,a[i]);
ans=max(ans,(max_val-a[i]+1)>>1);
}
cout<<ans<<endl;
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 952ms, 内存消耗: 39552K, 提交时间: 2022-10-21 14:51:06
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+10;
int a[N],mx,n,sa,sb,sc,sd,mod,res;
inline int f(int x){return (sa*x%mod*x%mod*x%mod+sb*x%mod*x%mod+sc*x%mod+sd)%mod;}
signed main(){
cin>>n>>sa>>sb>>sc>>sd>>a[1]>>mod; mx=a[1];
for(int i=2;i<=n;i++)
a[i]=(f(a[i-1])+f(a[i-2]))%mod,res=max(res,mx-a[i]),mx=max(mx,a[i]);
cout<<(res+1)/2;
return 0;
}
pypy3(pypy3.6.1) 解法, 执行用时: 823ms, 内存消耗: 100912K, 提交时间: 2020-09-01 09:33:05
def gt():
return list(map(int, input().split()))
n,sa,sb,sc,sd,a1,mod = gt()
sa %= mod; sb %= mod; sc %= mod; sd %=mod;
F = lambda x : (sa*pow(x,3,mod) + sb*pow(x,2,mod)+ sc*x%mod + sd)%mod
A = [0,a1%mod] + [0]*(n-1)
lmax = A.copy()
ans = 0
for i in range(2, n+1):
A[i] = (F(A[i-1])+F(A[i-2]))%mod
lmax[i] = max(A[i],lmax[i-1])
ans = max(ans, lmax[i]-A[i]+1>>1)
print(ans)