题意：一个1*n的棋盘上有k个棋子，一半是黑一半是白，并且是白黑白黑白黑...白黑的形式，A每次最多可以将d个白棋子向右移动，B每次最多可以将d个黑棋子向左移动，不能不移动棋子，谁最后无法移动棋子谁就输了，A先手，问有多少种布局可以使得A获胜
Solution
Nim-K博弈+动态规划
可以把棋子之间的间隔看做是石子的堆数，那么就变成了Nim-K问题
如果所有数上每一位的1的个数%(d+1)==0，这种就是必败的，我们用总的减去必败的就是答案
令dp[i] [j]表示1-i位上异或和为0，用了j个石子的方案数
那么对于下一位而言，每次转移的时候都必须改变这一位上(d+1)个数才行，我们枚举(d+1)的个数x*(d+1)
在k/2堆石子里面选取x(d+1)个，于是有
$$
dp[i+1][j+x(1<<i)(d+1)]+=dp[i][j]C(k/2,x(d+1))
$$
最后统计方案数的时候，需要考虑每一堆石子的位置，去掉需要空的间隔总共i个空格以及k/2个终点的位置，在其中选出k/2个起点，一共有Σdp[最高位] [i]C(n-i-k/2,k/2)
答案就是ans-Σdp[最高位] [i]*C(n-i-k/2,k/2)
// Problem: P2490 [SDOI2011]黑白棋
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2490
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
//#define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define FOR(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int lowbit(int x) { return -x & x; }
//const int mod = 998244353;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const int M = 6e5 + 5;
int ksm(int x, int y, int mod1 = mod) {
int res = 1;
x %= mod1;
while (y > 0) {
if (y & 1)
{
res = res * x % mod1;
}
y >>= 1;
x = (x * x) % mod1;
}
return res;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
typedef pair<int, int> pii;
int fac[N];
int inv[N];
int C(int n,int m)
{
if(n<m||m<0)return 0;
else return ((fac[n]*inv[n-m])%mod*inv[m])%mod;
}
int dp[20][10005];
void solve()
{
int n,k,d;cin>>n>>k>>d;
fac[0]=1;
for(int i=1;i<=100000;i++)
{
fac[i]=(fac[i-1]*i)%mod;
}
inv[100000]=ksm(fac[100000],mod-2);
for(int i=99999;i>=0;i--)
{
inv[i]=(inv[i+1]*(i+1))%mod;
}
int sum=C(n,k);
int res=0;
dp[0][0]=1;
//cout<<sum<<"\n";
for(int i=0;i<=15;i++)
{
for(int j=0;j<=n-k;j++)
{
int p=1<<(i);
for(int kk=0;j+p*kk*(d+1)<=n-k&&kk*(d+1)<=k/2;kk++)
{
dp[i+1][j+p*kk*(d+1)]=(dp[i+1][j+p*kk*(d+1)] + dp[i][j]*C(k/2,kk*(d+1))%mod)%mod;
}
}
}
for(int i=0;i<=n-k;i++)
{
sum=((sum-(dp[15][i]*C(n-i-k/2,k/2))%mod)%mod+mod)%mod;
}
cout<<sum<<"\n";
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin>>t;
while (t--)
{
solve();
}
return 0;
}