题解：AT_xmascon21_c Count Me

tobie · 2024-12-31 16:30:35 · 题解

看了下大佬们的题解，我不觉得这个把 \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}，需要在这个情况下计算方案数。

• 如果 p=n 或 s_ps_{p+1}=\texttt{??}，分析同上，f_{n-1,l}\to f_{n,l} 贡献 n-l 次。
• 如果 s_p s_{p+1} = \texttt{?0}，则这个问号下只能是 \texttt{1}，f_{n-1,l}\to f_{n,l}。
• 如果 s_p s_{p+1} = \texttt{0?}，则问号下的数是 \texttt{1}，可以用 \texttt{1}=\texttt{?}-\texttt{0} 容斥掉，f_{n-1,l-1}-f_{n-1,l} \to f_{n,l}。

整理一下， 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 的答案的带容斥系数和。

• 如果 s_i=\texttt{0}，则 dp_{i,l-1}\times \frac 1 {l+1}\to dp_{i+1,l}。
• 如果 s_i=\texttt{?}，则 dp_{i,l}\to dp_{i+1,0}。
• 如果 s_i=\texttt{1}，则 dp_{i,l-1}\times \frac {-1} {l+1}\to dp_{i+1,l}，dp_{i,l}\to dp_{i+1,0}。

事实上状态数少的可怜，在模拟赛里能骗 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)。

O(n^2) submission

O(n\log ^2 n) submission