题解 P2490 【[SDOI2011]黑白棋】

· · 题解

题面显然有误，如果允许白往左、黑往右，这游戏玩不完。

毕竟我是在博弈论的题单里发现这道题的

很快就反应过来：把各对相邻黑白棋子之间的距离视作一堆石子即可。 于是问题转化为一个 一次限制取d个 的Nim游戏。

这种类型问题有个结论：SG[x]=x\%(d+1)。 即题目本质是要 各堆石子个数异或和\%(d+1)=0。

怎么统计方案？（注意下状态）

显然异或和模d+1为0这种情况很方便设计DP状态。于是先统计后者胜利的情况，再用方案总数C_n^k减去它得到答案。

设f[i][j]表示确定异或和二进制第1-i位均为0、现有j个石子的方案数。

枚举该位需要x倍d+1个石子。

此时，该位对石子数的贡献取决于各堆石子该位是否为1。

于是要从k/2个堆选出x*(d+1)个,把这些堆石子数 该位置为1，贡献C_{k/2}^{x*(d+1)}种方案。

同时，我们要选出各堆的位置，相当于在n-j-k/2（k/2个位置被终点占）个位置中选出k/2个起点，贡献C_{n-j-k/2}^{k/2}种方案。

综上得方程式：

f[i+1][j+(1<<i)*x*(d+1)]+=f[i][j]*c[k/2][x*(d+1)] f[i][j]=f[i][j]*C[n-j-k/2][k/2] 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7;
int n,k,d,C[10005][205],dp[18][100005];
ll ans;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();k=gi();d=gi();
  C[0][0]=1;
  fp(i,1,n)
    {
      C[i][0]=1;
      fp(j,1,200) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
  dp[0][0]=1;
  fp(i,0,16)
    fp(j,0,n-k)
    for(re int x=0;(1ll<<i)*x*(d+1)<=n-k&&x*(d+1)<=k/2;++x)
      (dp[i+1][j+(1ll<<i)*x*(d+1)]+=1ll*dp[i][j]*C[k/2][x*(d+1)]%mod)%=mod;
  fp(i,0,n-k) ans=(ans+1ll*dp[17][i]*C[n-i-k/2][k/2]%mod+mod)%mod;
  printf("%lld\n",(C[n][k]-ans+mod)%mod);
  return 0;
}