题解：AT_xmascon21_c Count Me

重新看了一遍这题，我还是认为这不是人类能做的题。

考虑没有 ? 怎么做，把操作看做倒着删除，删 n−1 次的不同方案数。

考虑钦定去重，并简化操作：钦定每次删 0 只能删一段中末尾的 0，删 1 只能删一段中开头的 1。

在开头补一个 0，在结尾补一个 1。那么操作被简化为：每次将一个子串 01 变成 0 或 1，不能删开头的 0 和结尾的 1。

在序列中每两个数字之间添加一个删除时间标记，总共 n+1 个。每次删一对 01 时就把它们之间的标记标为第几个删，然后删掉这个标记和其中一个数。

将一种合法的删除方案双射到删除时间标记的顺序，也就是一个 n+1 的排列。（所有方案总数为 (n+1)!，与打表的结果相同）

对于 0，要求右边的标记比左边的标记先删除。对于 1，要求左边的标记比右边的标记先删除。

于是把 0 看做 <，1 看做 >，? 相当于没有限制，就是计数符合不等关系的排列个数。使用分治 NTT 解决，具体可见 「LibreOJ NOI Round #2」不等关系，时间复杂度 O(nlog 2 n)。