翻硬币：题解

思路

设当前状态与目标状态的汉明距离为 $j$。一次操作在 $j$ 个错误位置中翻转 $x$ 个，并在其余 $N-j$ 个正确位置中翻转 $M-x$ 个。新距离为

对应的翻转集合数为

这个数只依赖 $j$，因此可以把 $2^N$ 个具体状态压缩成 $N+1$ 个距离状态。

做法

令 $f_t[j]$ 表示恰好进行 $t$ 次操作后，结尾状态与目标状态距离为 $j$ 的操作序列数。初始距离为 $d$，则 $f_0[d]=1$。

对每个 $j$ 枚举

向 $j+M-2x$ 加上

每个大小为 $M$ 的翻转集合按其与错误位置集合的交集大小 $x$ 唯一分类，所以上述转移不重不漏。距离零只对应目标状态本身，答案为 $f_K[0]$。

组合数用 Pascal 递推预处理。模内乘积必须使用 64 位整数。

复杂度

时间复杂度为 $O(N^2+KNM)$，空间复杂度为 $O(N^2+N)$。

部分分

• $N\le4,K\le5$：枚举所有大小为 $M$ 的翻转集合，再枚举长度恰为 $K$ 的有序操作序列，复杂度 $O(\binom NM^K N)$。
• $N\le10$：对全部 $2^N$ 个具体硬币状态做位掩码 DP，复杂度 $O(K2^N\binom NM)$。

边界证书

• $K=0$ 时只有空操作序列，初态等于目标态答案为 1，否则为 0。
• $M=0$ 时状态不变。
• $M=N$ 时每次只能翻转全部硬币，答案只能为 0 或 1。
• $K=1$ 时当且仅当初末汉明距离为 $M$，答案为 1。
• 若初末汉明距离与 $KM$ 奇偶不同，则答案为 0。