AquaMoon and Chess 题解

思路

一次操作只会把连续片段 110 与 011 互相转换，也就是让一个空位与一个相邻的双棋子块交换位置。

从左到右扫描字符串：遇到 11 就把这两个字符配成一块并跳过它们，否则只前进一步。设得到 $p$ 个互不重叠的双棋子块，原串中有 $z$ 个零。没有被配对的单个 1 的相对约束不会改变；所有可达状态恰好对应于把 $p$ 个相同的双棋子块与 $z$ 个相同的空位重新排列。因此答案是

任意一次合法操作只交换相邻的空位与双棋子块，所以不会改变这两类对象的数量，也不会越过未配对棋子破坏上述表示。反过来，任意两个由这些对象组成的排列都能通过相邻交换互相到达。因此组合数既不会漏计，也不会重复计数。

做法

先对所有测试数据预处理阶乘和逆阶乘到最大的 $n$。对每个字符串统计零的数量，并从左到右贪心统计不重叠 11 的数量，随后用阶乘公式计算组合数。

第一档可以把二进制串编码成状态，用广度优先搜索枚举所有通过 110 与 011 转换可达的状态。第二档在得到 $z,p$ 后使用 Pascal 递推以二次时间计算组合数。满分算法用阶乘与逆阶乘把每组组合数计算降到常数时间。

复杂度

预处理和扫描所有字符串的总时间复杂度为 $O(\sum n)$，空间复杂度为 $O(\max n)$。