题目概述

有一个长度为奇数的 $01$ 串（有些位待定），每次可以把相邻三个合并成 $01$ 中数量多的，求最终能够变成 $1$ 的方案数。

解题报告

题解好像是大力分类，不过我们可以膜LPA20020220方便的解法。

首先先考虑如果要把一个串变成 $1$ 的策略，可以发现肯定尽量把相邻的 $000$ 都干掉，且尽量留下 $111$ ，由于其他方案都可以看做一个 $1$ 和一个 $0$ 抵消，所以可以直接消去，不需要管之前如何操作。

上面看起来正确，实际上漏了两种情况：$111$ 和 $100$ ，如果出现了 $111$ ，那么后面直接就不用管了，因为不管怎么合并都可以把 $111$ 和后面合并成 $1$ 。还有就是 $100$ ，我们不会想立刻消去 $100$ ，因为有可能会出现 $1000$ 。

由此可以设计一个自动机（其实就是转移，图片是盗来的QAQ）：

绿色边表示加 $0$ ，红色边表示加 $1$ ，其中特殊的点就是 $11$ 和 $100$ 。DP就好了。

示例程序

#include<cstdio>
using namespace std;//0:NULL,1:0,2:1,3:00,4:01,5:10,6:11,7:100
const int maxn=300000,MOD=1e9+7,son[8][2]={{1,2},{3,4},{5,6},{1,1},{1,2},{7,2},{6,6},{5,5}};

int n,f[maxn+5][8];char s[maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%s",s+1);for (n=1;s[n];n++);n--;f[0][0]=1;
    for (int i=1;i<=n;i++)
        for (int j=0;j<8;j++){
            if (s[i]!='0') AMOD(f[i][son[j][1]],f[i-1][j]);
            if (s[i]!='1') AMOD(f[i][son[j][0]],f[i-1][j]);
        }
    AMOD(f[n][2],f[n][6]);printf("%d\n",f[n][2]);return 0;
}