riteme.site

无尽的黄金 (gold.cpp/in/out)

时间限制:3s / 空间限制:512MB / 打开-O2优化

题目描述

探险家Lunk发现了一个藏在大山深处的洞穴。经过五天五夜的探索,Lunk在洞中发现了一个非常神奇的地方。这里有一个不断生成黄金的小口,每分钟可以取出一个黄金,不然这个黄金就会马上消失。取出的黄金自然会变成Lunk的了。贪婪的资本家绝对不会错过这个发财的大好时机,Lunk想要取走大量的黄金。

然而在这旁边却立着一个牌子,上面写着:

Hello, Lunk,

恭喜你,你非常机智地发现了这个奇妙的地方,我早已知道你到底想干什么。不如我们来玩个游戏,你可随意取走黄金,但是任意连续$K$分钟内,你不可以取走过多的黄金,否则,你将找不到出去的路。

Best wishes

——XL

这让Lunk感到十分害怕,它担心自己一不留神就会触犯的这个可怕的规则。但是贪婪的资本家是不会放弃的,Lunk想知道究竟有多少种取走黄金的方法(可以全都不取),使得自己不会葬身于山洞之中。

Lunk现在还有一些时间,希望你能够快速给出答案。

输入格式

每个数据仅一行,包含三个整数$T$$K$$C$

$T$表示Lunk还剩下的时间,单位为分钟。

$K$$C$表示Lunk在任意连续的$K$分钟内可以取走少于$C$个黄金。

输出格式

输出一行一个整数,表示Lunk取走黄金的方案数。由于答案可能非常大,所以请将答案对$1073741824$取模。

样例输入

1
2 2 2

样例输出

1
3

样例解释

只要Lunk不把所有黄金取走就好了,共有三种取法。

数据限制

本题采用捆绑测试,共$6$个子任务。

每个子任务和数据点约定如下:

子任务 (分值) $T$的限制 $K$的限制 $C$的限制
$1$ ($10\%$) $\le 10^3$ $= 2$ $= 2$
$2$ ($10\%$) $\le 10^3$ $= 3$ $= 2$
$3$ ($10\%$) $\le 10^3$ $\le 9$ $\le K$
$4$ ($20\%$) $\le 10^5$ $\le 9$ $\le K$
$5$ ($20\%$) $\le 2 \times 10^7$ $\le 6$ $\le K$
$6$ ($30\%$) $\le 2 \times 10^7$ $\le 9$ $\le K$

对于$100\%$的数据,均保证$1 \le T \le 2 \times 10^7$$1 \le K \le 9$$0 \le C \le K$

时间限制:$2\text{s}$

空间限制:$512\text{MB}$