Problem1100--#2221. 「HEOI2014」南园满地堆轻絮

1100: #2221. 「HEOI2014」南园满地堆轻絮

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 27  Solved: 11
[Submit] [Status] [Web Board] [Creator:]

Description

小 Z 是 ZRP(Zombies’ Republic of Poetry,僵尸诗歌共和国)的一名诗歌爱好者,最近他研究起了诗词音律的问题。在过去,诗词是需要编成曲子唱出来的,比如下面这首《菩萨蛮》,唱出来的话其对应 的音符就是这样的:

南 园 满 地 堆 轻 絮, 愁 闻 一 霎 清 明 雨
1 1 5 5 6 6 5  4 4 3 3 2 2 1

因而可以发现,“1 1 5 5 6 6 5 4 4 3 3 2 2 1” 这串音符就成为了研究音律的关键。

小 Z 翻阅了众多史料发现,过去的一首曲子的音调是不下降的。小 Z 想要知道对于一首给定的曲子,如何通过提高音调或者降低音调,将它的音调修改得不下降, 而且使得修改幅度最大的那个音符的修改幅度尽量小。

即如果把一个包含 nnn 个音符的曲子看做是一个正整数数列 A1,…,AnA_1,\ldots,A_nA1,,An,那么目标是求另一个正整数数列 B1,…,BnB_1,\ldots,B_nB1,,Bn, 使得对于任意的 1≤i<n1 \leq i < n1i<nBi≤Bi+1B_i \leq B_{i+1}BiBi+1,而且使得 Ans=max1≤j≤n{∣Aj−Bj∣}\mathrm{Ans}= \max_{1 \leq j \leq n} \{|A_j-B_j|\}Ans=max1jn{AjBj} 尽量小。 小 Z 很快就想清楚了做法,但是鉴于他还忙着写诗, 所以这个任务就交给了你。

输入格式

由于数据规模可能较大,因此采用如下方式生成数据。

每个数据包含六个数:n,Sa,Sb,Sc,Sd,A1,Modn,S_a,S_b,S_c,S_d,A_1,\mathrm{Mod}n,Sa,Sb,Sc,Sd,A1,Mod,意为共有 nnn 个音符,第一个音符为 A1A_1A1
生成规则如下: 定义生成函数 F(x)=Sax3+Sbx2+Scx+SdF(x) = S_ax^3 + S_bx^2 + S_cx + S_dF(x)=Sax3+Sbx2+Scx+Sd
那么给出递推公式 Ai=F(Ai−1)+F(Ai−2)A_i = F(A_{i-1}) + F(A_{i-2})Ai=F(Ai1)+F(Ai2),此处规定 A0=0A_0 = 0A0=0
由于中间过程的数可能会特别大,所以要求每一步与 AAA 中的每个数都对一个给定的数 Mod\mathrm{Mod}Mod 取模。

输出格式

输出一行,包含一个正整数 Ans\mathrm{Ans}Ans

样例

样例输入

3 815 6901 3839 178 199 10007

样例输出

1334

样例解释

生成的数列为 199 4568 1901199~4568~1901199 4568 1901,此时将 456845684568 修改为 323432343234190119011901 也修改为 323432343234 即可,代价为 133413341334

数据范围与提示

对于 100%100\%100% 的数据,n≤5000000, Sa,Sb,Sc,Sd,A1≤10000, Mod≤1000000007n \leq 5000000,\ S_a,S_b,S_c,S_d,A_1 \leq 10000,\ \mathrm{Mod} \leq 1000000007n5000000, Sa,Sb,Sc,Sd,A110000, Mod1000000007


Source/Category

 

[Submit] [Status]