E 奶龙与奥利奥自动机

题目大意

初始有个空的字符串 ，有 步操作，操作有 种：

1. 什么都不做；

2. 给 后面加个 "1"；

3. 给 后面加个 "0"；

4. 给 后面加个 "10"；

问最后有多少种不同结果的 。

数据范围 。

解题思路

由于是顺序加字符，且数据范围很线性，考虑能否使用顺序 dp。

对于 的答案，记作 。

若已知 的答案，考虑如何得到 的答案：

首先，可以从 得到，如果每种操作都执行一次，那么总数是 ，但是这样的计算会有重复计数，接下来考虑删除重复结果。

操作 是什么都不做，因为操作 任意换位不会影响字符串的结果，所以从 通过操作 得到的所有状态，都可以通过将操作 提前，使得状态与其他操作的状态相同。比如操作序列 等价于 。因此从 通过操作 得到的所有结果都会重复统计，总数减去 。由于空结果无法从其他操作得到，因此只有空结果没有重复统计，总数加 。这时总数删减为 。

操作 可能造成重复，重复只可能是操作序列 与 的结果（省略部分是结果相同且操作次数相同的操作序列）。即 通过操作 、操作 与 通过操作 、操作 重复了，因此总数减去 。这时总数删减为 。

得到最终递推式：。

最终代码

#include<bits/stdc++.h>
#define ll long long
#define MO 998244353ll
#define MXN 10000002
using namespace std;
ll T=1,n,f[MXN];
int main(){
    cin>>n;
    f[0]=1,f[1]=4;
    for(ll i=2;i<=n;++i)
        f[i]=(f[i-1]*3-f[i-2]+1+MO)%MO;//这里加一个 MO 能够防止结果为负数
    cout<<f[n];
}