题解

给你一个长度为$n$的$01$串$s$。你可以进行不超过$n−1$次操作。每次操作，你可以选择一个位置$i(1≤i<|s|)$，令$s_i:=max(s_i,s_{i+1})$，然后删掉$s_{i+1}$。删掉后，左右两边会自动拼接起来，并且$s$的长度会减$1$。请求出，有多少种不同的串，能通过对$s$进行不超过$n−1$次操作得到。答案对$10^9+7$取模。

首先我们发现生成的数列一定是原序列的一个子序列，然后又要求本质不同的子序列个数，这就让我们想到序列自动机。

我们先看一下对$a_i,a_{i+1}$操作的几种不同的后果：

$$00→0$$

$$01→1$$

$$10→1$$

$$11→1$$

可以发现，只有当两个$1$的时候才有可能删掉一个$1$。

所以我们构造如下的一个自动机：（相比一般的序列自动机，起始状态，接收状态集合，转移函数均有所变化）

字符集：$0,1$。

状态集合：类似于子序列自动机，序列中每个状态代表一个位置。

起始状态：第一个$1$的位置代表的状态。（因为最后一个$1$不可消除，可参考$101$仔细想想）

接受状态集合：所有$1$的位置代表的状态均为接受状态，其余都不是。（因为最后一个$1$不可消除，可参考$101$仔细想想）

转移函数：设当前状态为$zeta$，则$(zeta,1)$为下一个$1$的位置，$(zeta,0)$为下一个$len[x]=len[ζ]+1$的状态$x$（其中$len[ζ]$表示以该状态代表的位置为结尾，连续的$0$的个数，这个转移函数是整个题目的精髓）。比如一个序列$1000110000$，现在在位置$4$，想在这个后面加一个$0$，那么我们必须把位置$[2,5]$的数全部清掉，然后把位置$[6,9]$的数加进来才能达到目的（可以仔细想一想）。

我们对一个输入的序列，先把头尾的$0$全部删掉（最后累计进答案里）（根据自动机的构造我们必须这样做），然后可以发现我们要计数的东西其实就是从初始节点开始到任何一个接受状态的路径的个数（此处与序列自动机求本质不同的子序列个数是一样的），由于我们已经保证了任何一个最后可能生成的序列在自动机上遍历的时候一定遍历到它第一次出现的位置（类似于序列自动机），所以本质不同的要求我们也满足了。最后对自动机这个$DAG$跑一遍$DP$就可以了。

对这种要求本质不同的有条件的子序列个数的题，我们构建自动机时要注意：

  1. 自动机里的路径代表的子序列有且仅有题目要求的合法子序列。

  2. 对于任意一个合法子序列，在自动机里跑一遍后必须是在它第一次出现的位置。

  3. 与一般的子序列自动机不同，不一定每个状态都是接受状态。