P2490 [SDOI2011]黑白棋

题意：一个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;
}