#P10745. match

    ID: 9863 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600提高+/省选-配对策略Moore Nim数位 DP插板法补集计数阶乘逆元预处理滚动数组

match

题目描述

有 nn 把椅子排成一排,QQ 队和 BB 队各有 k/2k/2 名队员。初始时,每把椅子最多坐一个人。从左到右看坐着的队员,最左边属于 QQ 队,最右边属于 BB 队,相邻两人属于不同队伍。队内成员不作区分。

两队轮流行动,QQ 队先手。每回合,当前队伍选择 11 到 dd 名队员移动。每位选中的队员可以向左或向右移到另一把空椅子,不能越过旁边的其他队员。轮到一队却无法移动时,该队输。

求有多少种初始座位分布,使得 QQ 队有必胜策略。答案对 109+710^9+7 取模。

输入格式

一行三个整数 n,k,dn,k,d。

输出格式

一行一个整数,表示答案对 109+710^9+7 取模后的结果。

样例

4 2 1
3

数据范围

  • 对于 20%20\% 的数据,n≤10n\le10,k≤6k\le6。
  • 另有 15%15\% 的数据,k=2k=2。
  • 另有 15%15\% 的数据,d=1d=1。
  • 对于 70%70\% 的数据,n≤1000n\le1000。
  • 对于所有数据,1≤d≤k≤n≤100001\le d\le k\le n\le10000,k≤100k\le100,kk 为偶数。

原 PDF 题面