P2100 凌乱的地下室

    • 31通过
    • 74提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 字符串 矩阵运算 高精 高性能
  • 难度 提高+/省选-
  • 时空限制 400ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小Z家的地下室里并排放n个小方块(小Z是一位MC狂热爱好者,喜欢用小方块装饰他家的地下室),并且每个方块都不一样(小Z喜欢各不相同的东西),比如有草方块、大理石、黑曜石等。

    小Z喜欢以一种特殊的顺序摆放这些小方块,比如:草方块、大理石、黑曜石。一天,小D帮助小Z整理地下室,可是智商捉急的小D将所有小方块搬出来后忘记了它们原来的具体位置,凭着模糊的印象,他可能把原来放在第i个位置上的小方块放到第(i-1)、i、(i+1)个位置中的任意一个上(当然,第1个不可能放到第0个位置上,第n个不可能放到第(n+1)个位置上),比如(对应上面那个例子):大理石、草方块、黑曜石。

    小Z是一个心胸宽广的人,他希望计算一下小D一共会有几种可能的摆放结果,并不追究小D的责任(追究了只会更乱……)。由于他自己的智商也比较捉急,所以如果答案很大的话他只想看到最后的8位(前导零就不要给他看了)。

    输入输出格式

    输入格式:

    一行,一个正整数n,代表小Z家的地下室一共有n个小方块。

    输出格式:

    一行,一个正整数,表示小D一共有几种可能的摆放结果,只输出后8位,前导零不输出。

    输入输出样例

    输入样例#1: 复制
    3
    输出样例#1: 复制
    3
    输入样例#2: 复制
    987
    输出样例#2: 复制
    223731

    说明

    【样例解释1】

    接着题目中的例子,一共有3种:(草方块,大理石,黑曜石)、(大理石,草方块,黑曜石)、(草方块,黑曜石,大理石)。

    【样例解释2】

    一共有……00223731种摆放结果,由于前导零不输出,因此输出223731。

    【数据规模】

    一共有50个测试点。

    其中第1~15个:1<n<=10^6

    其中第16~25个:10^6<n<=10^16

    其中第26~50个:10^16<n<=10^1000

    【时空限制】

    0.2s/64MB

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