[数学记录]P2490 [SDOI2011]黑白棋
command_block
·
·
个人记录
题意 ： 有一个 1\times n 的棋盘，其中有 2k 颗棋子。
一半是黑色，一半是白色，最左侧的棋子是白色，最右侧的棋子是黑色，相邻的棋子颜色不同。
小 A 可以移动白色棋子，小 B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。
两人轮流操作，每次可以同时操作 1\sim d 颗棋子。无法移动者负。
现在小 A 先手，问有多少种棋盘布局使得小 A 必胜。
答案对 10^9+7 取模。
------------
这种题成早期 SDOI 传统艺能了都……
不难发现，将一对相邻的黑白棋之间的空位个数看做一堆石子数目，即转化为 $\rm Nim_k$。
总方案数为 $\dbinom{n}{k}$ ，故可以转为统计先手必败。
根据 $\rm Nim_k$ 的结论，问题现在转化成了 ：
用隔板将 $n-k$ 拆分成 $k+1$ 个整数，使得排名为奇数的（$k/2$ 个）数的 $\rm Nim_k$ 和为 $0$。
设 $f[n,k]=n$ 拆分成 $k$ 个整数，使得 $\rm Nim_k$ 和为 $0$ 的方案数。
则有 ：
$${\rm Ans}=\sum_{i=0}f[i,k/2]\dbinom{n-k/2-i}{k/2}$$
其中 $\dbinom{n-k/2-i}{k/2}$ 是将剩下的 $n-k-i$ 个空位 分配到 $k/2+1$ 个空隙中的方案数。
剩下的问题就是计算 $f$ 了。
不难想到朴素的 $\rm DP$ : $g[n,k,s]$ 表示还剩 $n$ 未拆分，还需要拆分 $k$ 个数，得到的 $\rm Nim_k$ 和为 $s$ 的方案数。
可惜这样的状态量至少是 $O(n^2k)$ 的，无法通过。
我们没有充分利用 “ $\rm Nim_k$ 和为 $0$ ” 这一关键约束。
$\rm Nim_k$ 和的每一位是独立的，于是分位考虑。
设 $g[n,t]$ 为（从低到高）考虑到二进制第 $t$ 位，已经使用了 $n$ 颗石子，且保证所有低位上 $\rm Nim_k$ 和为 $0$ 的方案数。
转移时可以枚举第 $t$ 位 $1$ 的个数 $c$ （需满足 $(d+1)|c$），则有转移 ：
$$g[n+c*2^t,t+1]+=g[n,t]\times \dbinom{k/2}{c}$$
其中 $\dbinom{k/2}{c}$ 是从 $k/2$ 堆石子中选取 $c$ 堆的方案数。
最终 $f[n,k/2]=g[n,\lceil\log_2n\rceil]$。
复杂度 $O(nk\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 10500
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
int n,k,d;
ll g[18][MaxN];
int main()
{
scanf("%d%d%d",&n,&k,&d);
Init(max(n,k));
g[0][0]=1;
int lim=0;while((1<<lim)<=n)lim++;
for (int t=0;t<lim;t++)
for (int m=0;m<=n;m++)if (g[t][m])
for (int c=0;c<=k/2;c+=d+1)
if (m+(c<<t)<=n-k)
g[t+1][m+(c<<t)]=(g[t+1][m+(c<<t)]+g[t][m]*C(k/2,c))%mod;
ll ans=0;
for (int i=0;i<=n-k;i++)
ans=(ans+g[lim][i]*C(n-k/2-i,k/2))%mod;
printf("%lld",(C(n,k)+mod-ans)%mod);
return 0;
}
```