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

    • 157通过
    • 486提交
  • 题目提供者 Great瞿葩
  • 评测方式 云端评测
  • 标签 卢卡斯,Lucas 数论,数学 组合数学 贪心 洛谷原创
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

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

    题目描述

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

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

    输入输出格式

    输入格式:

    一个整数N

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4
    输出样例#1: 复制
    24
    输入样例#2: 复制
    1125
    输出样例#2: 复制
    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:它叫做三角圣地,其实它就是个三角形~

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

    不要面向数据编程!

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。