【BZOJ2281】【Sdoi2011】黑白棋
Description
小A和小B又想到了一个新的游戏。
这个游戏是在一个\(1\)*\(n\)的棋盘上进行的，棋盘上有\(k\)个棋子，一半是黑色，一半是白色。
最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。
小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动\(1\)到\(d\)个棋子。
每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？
先手不能左移，后手不能右移
Input
共一行，三个数，\(n,k,d\)。
Output
输出小A胜利的方案总数。答案对\(1000000007\)取模。
HINT
\(1<=d<=k<=n<=10000\), \(k\)为偶数，\(k<=100\)。
越发的觉得自己是个低能儿了...
注意原题是没有“先手不能左移，后手不能右移”这个条件的，不过被黄学长hack了，于是部分oj加上了
然后发现先手有个必败局面是所有对应的黑白棋相邻。
然后我们发现移动会造成对应的相邻黑白棋的距离缩小
于是可以发现是个\(k-nim\)游戏
关于这个东西有个结论，若子游戏\(SG\)每一位的\(1\)的总个数都可以被\((d+1)\)整除，当前局面是必败局面。
然后问题转换成，在序列上选取若干个不相交区间，保证区间的长度满足一些要求。
因为要求是按位的，所以做数位\(dp\)
\(dp_{i,j}\)代表前\(i\)位满足条件且选取的区间总长度是\(j\)的方案数。
\(dp_{0,0}=1\)是初始状态，表示区间长度为\(0\)
然后推出去会比较好些，我们先不讨论每个区间的位置，只讨论区间的长度的方案。
于是有\(dp_{i,j+len*x*(d+1)}+=dp_{i,j}*\binom{k/2}{x(d+1)}\)
\(len\)当前位数对应的长度，\(x\)枚举是几倍，然后组合数选那几个区间
最后确定位置每个状态乘上\(\binom{n-j-k/2}{k/2}\)就可以了
Code:
#include <cstdio>
#define ll long long
const ll mod=1e9+7;
const int N=1e4+10;
ll inv[N<<3],fac[N<<3],dp[16][N];
ll qp(ll d,ll k)
{
ll f=1;
while(k)
{
if(k&1) f=f*d%mod;
d=d*d%mod;
k>>=1;
}
return f;
}
ll C(int m,int n)
{
if(n<0||m<n) return 0;
return fac[m]*inv[m-n]%mod*inv[n]%mod;
}
int main()
{
int n,k,d;
scanf("%d%d%d",&n,&k,&d);
fac[0]=1;int le=1<<15;
for(int i=1;i<=le;i++) fac[i]=fac[i-1]*i%mod;
inv[le]=qp(fac[le],mod-2);
for(int i=le-1;~i;i--) inv[i]=inv[i+1]*(i+1)%mod;
dp[0][0]=1;
for(int i=0;i<=14;i++)
{
int len=1<<i;
for(int x=0;x*len*(d+1)<=n;x++)
for(int j=0;j+x*len*(d+1)<=n;j++)
(dp[i+1][j+x*len*(d+1)]+=dp[i][j]*C(k/2,x*(d+1)))%=mod;
}
ll ans=0;
for(int i=0;i<=n;i++) (ans+=dp[15][i]*C(n-i-k/2,k/2))%=mod;
printf("%lld\n",(C(n,k)-ans+mod)%mod);
return 0;
}
2018.12.18