题解：AT_xmascon21_c Count Me

看了下大佬们的题解，我不觉得这个把 $\texttt{01}$ 看成不等号的等价转换是人类能想出来的东西，来一个我自己的思考过程吧。

本题还有一个思考方向：保留 $\texttt{?}$，去掉 $\texttt{1}$，通过容斥算贡献。

直接考虑题目中的过程，为了不算重，考虑加一个限制：每次删掉的数要满足 $i=n \vee s_i\neq s_{i+1}$。

首先我们考虑一个基本的问题：对于一个长度为 $n$ 的全问号串，求 $f_n$。

考虑枚举我们现在删掉了哪个位置，设为 $p$。

我们此时需要确定 $p$ 上的数是什么东西。现在我们翻开这个问号，发现 $s_p=\texttt{1}$，则根据限制可以推得 $s_{p+1}=\texttt{0}$；同理如果 $s_p=\texttt{0}$，则 $s_{p+1}=\texttt{1}$。

这一步相当于说，我们翻开了相邻的两个位置，并且删除了左边那个数。这里可以利用 $\texttt{01}$ 的对称性重新用问号盖上右边那个数，这样就划归到了子问题 $f_{n-1}$。

特别的，如果 $p=n$，则右边没有数，需要算两次贡献。

得到递推式 $f_n=(n+1)f_{n-1}$，所以 $f_n=(n+1)!$。

接下来考虑有一些位置是 $\texttt{0}$ 的情况。我们现在假设 $\texttt{0}$ 在中间形成了一个长度为 $l$ 的连续段，整个串长度为 $n$，设答案为 $f_{n,l}$。

手玩以下有边界条件 $f_{n,n}=1,f_{n,0}=(n+1)!$。

枚举我们现在删掉了哪个位置。不同于之前的是，我们事先知道了一些位置上的值为 $\texttt{0}$，需要在这个情况下计算方案数。

整理一下， $f_{n,l}=(n-l) f_{n-1,l}+f_{n-1,l-1}$，得到 $f_{n,l}=\frac {(n+1)!}{(l+1)!}$。

归纳可得，如果存在多段连续的 $\texttt{0}$，则答案为 $(n+1)!$ 除以所有连续段长度加一的阶乘。

我们现在将原字符串中的 $\texttt{1}$ 拆成 $\texttt{?}-\texttt{0}$，设 $dp_{i,l}$ 表示当前考虑到为止 $i$，最后一段长度为 $l$ 的答案的带容斥系数和。

事实上状态数少的可怜，在模拟赛里能骗 80pts。（骄傲）

会了 $O(n^2)$ 做法，剩下的就很简单了。

我们得先把这个 dp 式子压成一维的，枚举上一个被钦定为问号的位置 $j$，则 $i,j$ 中间夹着的东西全是 $\texttt{0}$，贡献为 $(-1)^{\mathrm{cnt}}\frac 1 {(\mathrm{len}+1)!}$ ，可以拆成只和 $i,j,j-i$ 有关的形式。使用分治 NTT 复杂度可以做到 $O(n\log ^2 n)$。