#P2675. 《瞿葩的数字游戏》T3-三角圣地

    ID: 1680 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Lucas数论数学组合数学贪心洛谷原创

《瞿葩的数字游戏》T3-三角圣地

题目背景

国王1带大家到了数字王国的中心:三角圣地。

题目描述

不是说三角形是最稳定的图形嘛,数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字,分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来,最底端就是一个比较大的数字啦!数字王国称这个数字为“基”。国王1希望“基”越大越好,可是每次都自己去做加法太繁琐了,他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大,所以请你输出它mod 10007 的结果。

任务:给定N,求三角形1~N的基的最大值 再去 mod 10007。

输入格式

一个整数N

输出格式

一个整数,表示1~N构成的三角形的最大的“基”

4
24
1125
700

提示

数据:

20% 0<=N<=100

50% 0<=N<=3000

100% 0<=N<=1000000

样例解释:

1 3 4 2

4 7 6

11 13

24 是N=4的时候的最大值,当然还有别的构成形式。

PS:它叫做三角圣地,其实它就是个三角形~

本题数据已经更新,目前全部正确无误!

不要面向数据编程!