P2233 [HNOI2002]公交车路线

    • 348通过
    • 599提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 矩阵乘法 各省省选 2002 湖南
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    在长沙城新建的环城公路上一共有8个公交站,分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行,因此你从某一个公交站到另外一个公交站往往要换几次车,例如从公交站A到公交站D,你就至少需要换3次车。

    Tiger的方向感极其糟糕,我们知道从公交站A到公交E只需要换4次车就可以到达,可是tiger却总共换了n次车,注意tiger一旦到达公交站E,他不会愚蠢到再去换车。现在希望你计算一下tiger有多少种可能的乘车方案。

    题目描述

    输入输出格式

    输入格式:

    输入文件由bus.in读入,输入文件当中仅有一个正整数n(4<=n<=10000000),表示tiger从公交车站A到公交车站E共换了n次车。

    输出格式:

    输出到文件bus.out。输出文件仅有一个正整数,由于方案数很大,请输出方案数除以 1000后的余数。

    输入输出样例

    输入样例#1: 复制
    6
    输出样例#1: 复制
    8

    说明

    8条路线分别是:

    (A→B→C→D→C→D→E),(A→B→C→B→C→D→E),

    (A→B→A→B→C→D→E),(A→H→A→B→C→D→E),

    (A→H→G→F→G→F→E),(A→H→G→H→G→F→E),

    (A→H→A→H→G→F→E),(A→B→A→H→G→F→E)。

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