P3204 [HNOI2010]公交线路

    • 164通过
    • 335提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 状态压缩,状压 进制 2010 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    小Z所在的城市有N个公交车站,排列在一条长(N-1)km的直线上,从左到右依次编号为1到N,相邻公交车站间的距离均为1km。 作为公交车线路的规划者,小Z调查了市民的需求,决定按下述规则设计线路:

    1. 设共K辆公交车,则1到K号站作为始发站,N-K+1到N号台作为终点站。
    2. 每个车站必须被一辆且仅一辆公交车经过(始发站和终点站也算被经过)。
    3. 公交车只能从编号较小的站台驶往编号较大的站台。
    4. 一辆公交车经过的相邻两个站台间距离不得超过Pkm。

    在最终设计线路之前,小Z想知道有多少种满足要求的方案。由于答案可能很大,你只需求出答案对30031取模的结果。

    输入输出格式

    输入格式:

    仅一行包含三个正整数N K P,分别表示公交车站数,公交车数,相邻站台的距离限制。N<=10^9,1<P<=10,K<N,1<K<=P

    输出格式:

    仅包含一个整数,表示满足要求的方案数对30031取模的结果。

    输入输出样例

    输入样例#1: 复制
    样例一:10 3 3
    样例二:5 2 3
    样例三:10 2 4
    输出样例#1: 复制
    1
    3
    81

    说明

    【样例说明】

    样例一的可行方案如下: (1,4,7,10),(2,5,8),(3,6,9)

    样例二的可行方案如下: (1,3,5),(2,4) (1,3,4),(2,5) (1,4),(2,3,5)

    P<=10 , K <=8

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