F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 2004. -- [Hnoi2010]Bus 公交线路

2004: [Hnoi2010]Bus 公交线路

Time Limit: 20 Sec  Memory Limit: 259 MB
Submit: 994  Solved: 713
[Submit][Status][Discuss]

Description

小Z所在的城市有N个公交车站,排列在一条长(N-1)km的直线上,从左到右依次编号为1到N,相邻公交车站间的距
离均为1km。 作为公交车线路的规划者,小Z调查了市民的需求,决定按下述规则设计线路:
1.设共K辆公交车,则1到K号站作为始发站,N-K+1到N号台作为终点站。
2.每个车站必须被一辆且仅一辆公交车经过(始发站和
终点站也算被经过)。 
3.公交车只能从编号较小的站台驶往编号较大的站台。 
4.一辆公交车经过的相邻两个
站台间距离不得超过Pkm。 在最终设计线路之前,小Z想知道有多少种满足要求的方案。由于答案可能很大,你只
需求出答案对30031取模的结果。

Input

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

Output

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

Sample Input

样例一:10 3 3
样例二:5 2 3
样例三:10 2 4

Sample Output

1
3
81

HINT

【样例说明】

样例一的可行方案如下: (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

Source

[Submit][Status][Discuss]

HOME Back