【SDOI2011】黑白棋（Nim游戏&&DP）

Description

小A和小B又想到了一个新的游戏。
这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。
最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。
每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？

Solution

这样每对黑白棋之间的空格可以看成石子。
那么这道题就是k-nim游戏。
k-nim游戏有一个结论就是每堆石子二进制的每一位的个数和是(k+1)的倍数。
那么我们只要DP一下就好了，设f[i][j]为做到二进制第i位，放的数总和为j的方案数。
f[i+1][j+(l+1)* d * er[i]]+=f[i][j]* c[k/2][l* (d+1)]
最后求出来的值还要乘上一下组合数，因为这坨东西可以放在任意位置。

Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
 using namespace std;
 const int maxn=10007,mo=1e9+7;
 typedef long long ll;
 ll i,j,k,l,t,n,m,ans,ln,d;
 ll c[maxn],er[20],f[20][maxn];
 ll qsm(ll x,ll y){
     ll z=1;
for(;y;y/=2,x=x*x%mo)if(y&1)z=z*x%mo;
 return z;
 }
 ll cc(ll n,ll m){
 ll i,z=1;if(n<m)return 0;
 if(m>n-m)m=n-m;
 fo(i,1,m)z=z*(n-i+1)%mo*qsm(i,mo-2)%mo;
 return z;
}
 int main(){
 // freopen("fan.in","r",stdin);
     er[0]=1;fo(i,1,19)er[i]=er[i-1]*2;
     scanf("%d%d%d",&n,&k,&d);
     c[0]=1;fo(i,1,k/2)c[i]=c[i-1]*(k/2-i+1)%mo*qsm(i,mo-2)%mo;
     f[0][0]=1;ln=log(n-k)/log(2);
     fo(i,0,ln-1){
         fo(j,0,n-k){
if(!f[i][j])continue;
for(l=0;l*(d+1)<=k/2;l++){
if(j+l*(d+1)*er[i]>n-k)continue;
                 f[i+1][j+l*(d+1)*er[i]]=(f[i+1][j+l*(d+1)*er[i]]+f[i][j]*c[l*(d+1)]%mo)%mo;
             }
         }
     }
     ans=1;fo(i,1,k)
     ans=ans*(n-i+1)%mo*qsm(i,mo-2)%mo;
     fo(i,0,n-k)
     ans=(ans-f[ln][i]*cc(n-k/2-i,k/2)+mo)%mo;
printf("%lld\n",ans);
 }