Loading web-font TeX/Math/Italic
比赛场次 553
比赛名称 2022级DP专题练习赛3
比赛状态 已结束比赛成绩
开始时间 2023-02-17 18:30:00
结束时间 2023-02-17 22:00:00
开放分组 全部用户
注释介绍 以赛代练
题目名称 黑白棋
输入输出 sdoi2011_hbq.in/out
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试点数 9 简单对比
用户 结果 时间 内存 得分
Gravatar遥时_彼方 AWWWWAWAW 0.000 s 0.00 MiB 33
GravatarHeSn AWWWWAWAW 0.000 s 0.00 MiB 33
Gravatarzxhhh WWWWWWWWW 0.005 s 0.64 MiB 0

黑白棋

★★★   输入文件:sdoi2011_hbq.in   输出文件:sdoi2011_hbq.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

A 和小 B 又想到了一个新的游戏。


这个游戏是在一个 1 \times n 的棋盘上进行的,棋盘上有 k 个棋子,一半是黑色,一半是白色。


最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同。

A 可以移动白色棋子,小 B 可以移动黑色的棋子,其中白色不能往左,黑色不能往右。他们每次操作可以移动 1d 个棋子。


每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。


A 和小 B 轮流操作,现在小 A 先移动,有多少种初始棋子的布局会使他胜利呢?

【输入格式】

输入三个数 n,k,d

【输出格式】

输出小 A 胜利的方案总数。答案对 10^9+7 取模。

【样例1输入】

10 4 2

【样例1输出】

182

【样例2】

点击下载样例2

【数据规模与约定】

对于 30\% 的数据,有 k=2

对于 100\% 的数据,有 1 \leq d \leq k \leq n \leq 10^4,k 为偶数,k \leq 100

【来源】

SDOI 2011