#PQJ2877x16278. QOJ 2877_16278

    ID: 2878 传统题 2000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HNOI 2010组合数学

QOJ 2877_16278

小 Z 所在的城市有 𝑁 个公交车站,排列在一条长为 𝑁 − 1 公里的直线上,从左到右依次编号为 1 到 𝑁 ,相邻公交车站间的距离均为 1 公里。

作为公交车线路的规划者,小 Z 调查了市民的需求,决定按以下规则设计线路:

设共有 𝐾 辆公交车,则 1 到 𝐾 号车站作为始发站, 𝑁 − 𝐾 + 1 到 𝑁 号车站作为终点站。 每个车站必须被一辆且仅一辆公交车经停(始发站和终点站也算被经停)。 公交车只能从编号较小的车站驶向编号较大的车站。 一辆公交车经停的相邻两个车站间的距离不得超过 𝑃 公里。

注意“经停”是指经过并停车,因经过不一定会停车,故经停与经过是两个不同的概念。

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

输入格式

输入只有一行,其中包含用空格隔开的三个正整数 𝑁 , 𝐾 , 𝑃 ,分别表示公交车站数、公交车数、一辆公交车经停的相邻两个车站间的最大距离。

输入的数据保证 40 % 的数据满足 𝑁 ≤ 1000 。 100 % 的数据满足 1 < 𝑁 < 10 9 , 1 < 𝑃 ≤ 10 , 𝐾 < 𝑁 , 1 < 𝐾 ≤ 𝑃 。

输出格式

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

样例数据 样例 1 输入 10 3 3 样例 1 输出 1 样例 2 输入 5 2 3 样例 2 输出 3 样例 3 输入 10 2 4 样例 3 输出 81 样例解释

样例一满足要求的方案只有 1 种,即: ( 1 , 4 , 7 , 10 ) , ( 2 , 5 , 8 ) , ( 3 , 6 , 9 ) 。

样例二满足要求的方案有 3 种,即: ( 1 , 3 , 5 ) , ( 2 , 4 ) ; ( 1 , 3 , 4 ) , ( 2 , 5 ) 和 ( 1 , 4 ) , ( 2 , 3 , 5 ) 。