P2490 [SDOI2011] 黑白棋 笔记

前置知识：K-Nim 游戏。

由于白棋和黑棋交错放并且只能向中间走，相邻的两个白黑棋中间的格子数即可看作一堆石子。

问题转换为：有 $N=n-k$ 个完全相同的物品，$M=\frac{k}{2}$ 个不同的盒子，把若干个物品放进盒子里，要求每个盒子内物品数量的二进制，每位的和 $modK=0$（$K=d+1$），求方案数。

考虑每次只往盒子里放 $2^i$ 个物品，这样子每次放数都只和当前位有关，设 $f_{i,j}$ 表示考虑 $[i,14]$ 位二进制每位和均为 $0$，并且还剩 $j$ 个物品没放进盒子。为了保证第 $i$ 位和为 $0$，每次至少选择 $xK$ 个盒子（$x\ge 0$），故：

$$f_{i,j-xK\times 2^i}\leftarrow f_{i+1,j}\times (\genfrac{}{}{0ex}{}{M}{xK})$$

最终没选的物品随便插到盒子中间：$\sum f_{0,i}\times (\genfrac{}{}{0ex}{}{M+i}{i})$。

时间复杂度 $O(KN\log N)$。