题目传送门
题目大意： 有一个 1 × n 1\times n 1×n 的棋盘，上面有 k k k 颗棋子，一半白一半黑，并且相邻棋子颜色不同，两个人轮流操作，一个人只能将白棋子右移，一个人只能将黑棋子左移，每个人一次最多移动 d d d 颗棋子，问有多少种局面先手必胜（先手操作白棋子）。
将相邻的一对黑白棋子看成一堆石子，他们之间的距离就是石子数量，那么就一共有 k / 2 k/2 k/2 堆 石子，变成了一个 d d d 阶的 N i m Nim Nim 游戏。
考虑 1 1 1 阶 N i m Nim Nim 游戏的必败情况：假如所有石头数量异或和为 0 0 0 则必败，这等价于，将每堆石子数量转化为二进制数，然后对于所有 i i i，第 i i i 位为 1 1 1 的数的个数恰好为 2 2 2 的倍数。
类似的， d d d 阶 N i m Nim Nim 游戏的必败情况就是：对于所有 i i i，第 i i i 位为 1 1 1 的数的个数恰好为 d + 1 d+1 d+1 的倍数，证明也类似，因为 d d d 阶 N i m Nim Nim 游戏中，一个人一次操作可以将任意位的 1 1 1 的个数减少 1 1 1 ~ d d d 个，那么每一位就是一个 B a s h Bash Bash 游戏，所以如果都是 d + 1 d+1 d+1 的倍数就必败。
为了方便，先将 k k k 除以 2 2 2，则 k k k 的意义就变成了石子堆数。
求必胜局面数不好求，正难则反，考虑求出必败局面数，总局面数显然为 ( n − 2 ∗ k + 2 ∗ k + 1 − 1 2 ∗ k + 1 − 1 ) = ( n 2 ∗ k ) \binom {n-2*k+2*k+1-1} {2*k+1-1}=\binom n {2*k} (2∗k+1−1n−2∗k+2∗k+1−1)=(2∗kn)，即将空位插入到所有棋子中间。
设 f [ i ] f[i] f[i] 表示石子总数为 i i i，分成 k k k 份使先手必败的方案数。考虑枚举每一位上 1 1 1 的总数（一定是 d + 1 d+1 d+1 的倍数），然后将这些 1 1 1 用组合数分配到每个石子堆里就可以了。最后统计答案时， f [ i ] f[i] f[i] 的贡献为 f [ i ] × ( n − 2 ∗ k + k + 1 − 1 k + 1 − 1 ) f[i]\times\binom {n-2*k+k+1-1} {k+1-1} f[i]×(k+1−1n−2∗k+k+1−1)，组合数是表示将没用到的空位放到 k k k 堆石子的间隙中。
时间复杂度 O ( 13 n × n d + 1 ) O(13n\times \frac n {d+1}) O(13n×d+1n)，当 d = 1 d=1 d=1 时会被卡到 13 n 2 13n^2 13n2，但是众所周知理论时间复杂度和实际时间复杂度是两个东西，所以我这个代码不开 O 2 O2 O2 洛谷rk3，开了 O 2 O2 O2 在洛谷甚至以 22 m s 22ms 22ms 能跑到rk1（目前）……
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 10010 #define mod 1000000007 int n,k,d; int fac[maxn],inv[maxn],inv_fac[maxn]; void FacInit(){ fac[0]=inv_fac[0]=inv[1]=1; for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod; for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=n;i++)inv_fac[i]=1ll*inv_fac[i-1]*inv[i]%mod; } int Binom(int x,int y){return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;} int f[maxn],tmp[maxn]; void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);} int main() { scanf("%d %d %d",&n,&k,&d); k/=2;int N=n-2*k; FacInit();f[0]=1; for(int i=0;i<=13;i++){ int bin=1<<i; for(int j=0;j<=k&&j*bin<=N;j+=d+1){ for(int l=0;l+j*bin<=N;l++){ add(tmp[l+j*bin],1ll*f[l]*Binom(k,j)%mod); } } for(int j=0;j<=N;j++)f[j]=tmp[j],tmp[j]=0; } int ans=0; for(int i=0;i<=N;i++)add(ans,1ll*f[i]*Binom(N-i+k+1-1,k+1-1)%mod); ans=(Binom(n,k*2)-ans+mod)%mod; printf("%d",ans); }