正題
題目連結:https://www.luogu.com.cn/problem/P2490
題目大意
一個長度為\(n\)的棋盤上放下\(k\)個棋子。
第一個要是白色，下一個要是黑色，在下一個是白色以此類推。
先手操控白，後手操控黑。白色隻能往右，黑色隻能往左。每次操作的可以移動\(d\)個棋子任意步。
求先手必勝的初始狀态數
\(1\leq d\leq k\leq n\leq 10^4,1\leq k\leq 100\)且\(k\)為偶數
解題思路
把兩個黑白棋子之間的長度看為石頭堆就是一個\(Nim_k\)遊戲了。
\(Nim_k\)遊戲的結論就是\(k+1\)進制下各個位置的\(1\)的個數\(\% (k+1)\)等于\(0\)的話先手必敗。
因為先手必勝比較麻煩，考慮減去先手必敗的情況
這個東西和昨天的一道\(ARC\)的題目很像，每個位分開考慮，設\(f_{i,j}\)表示前\(i\)個位都是\(0\)時，用了\(j\)個石頭的方案。
那麼轉移也十分顯然，枚舉一個選的倍數\(i\)然後配置設定到\(\frac{k}{2}\)個石頭堆中，方案數就是\(\binom{\frac{k}{2}}{i\times (d+1)}\)。
然後統計答案的時候對于石子和為\(i\)的貢獻就是\(\binom{n-\frac{k}{2}-i}{\frac{k}{2}}\)（因為每一堆的個數固定，是以選擇起點就好了）
時間複雜度\(O(nk\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e4+10,M=110,P=1e9+7;
ll n,k,d,ans,C[N][M],f[16][N];
signed main()
{
scanf("%lld%lld%lld",&n,&k,&d);
C[0][0]=1;n-=k;k/=2;d++;
for(ll i=1;i<N;i++)
for(ll j=0;j<M;j++)
C[i][j]=((j?C[i-1][j-1]:0)+C[i-1][j])%P;
ll z=0;ans=C[n+2*k][k*2];f[0][0]=1;
for(ll p=1;p<=n;p<<=1){
z++;
for(ll j=0;j<=n;j++)
for(ll i=0;j+i*p*d<=n&&i*d<=k;i++)
(f[z][j+i*p*d]+=f[z-1][j]*C[k][i*d]%P)%=P;
}
for(ll i=0;i<=n;i++)
(ans+=P-f[z][i]*C[n+k-i][k]%P)%=P;
printf("%lld\n",ans);
return 0;
}