JZOJ 6553 人生

既然是从小编号连至大编号，那么有一个简单的想法是按照编号顺序进行 DP。

设 end(i) 表示以点 i 结尾的合法路径的条数。
设 fi,j,k,h 表示前 i 个点，有 j 个白点满足其 end 值为奇数，有 k 个黑点满足其 end 值为偶数，n∑i=1end(i)≡h(mod2) 有多少方案。

考虑转移。
转移时考虑新加入的点的颜色，若新点为黑色，则从 j 个 end 值为奇数的白点中枚举有多少个点与新点有边，并更新 k,h。
这样子即是 O(n4) 的。

然而注意到两点：

1. 实际上，并不需要关心具体有多少个 end 值为奇数的异色点与新点有边，我们只需要关心点数的奇偶性。
   
2. 观察转移系数可以发现，实际上转移系数仅与 i 和 j,k 是否超过 0 有关。

由此优化，可以得到一个 O(n) 的状态，而完成这个 DP 也只需要 O(n)。

代码：

#include <cstdio>
using namespace std;
const int N = 2e5;
const int mod = 998244353;
int n,a[N + 5],pw[N + 5];
int f[N + 5][2][2][2],ans;
int main()
{
    freopen("life.in","r",stdin),freopen("life.out","w",stdout);
    scanf("%d",&n),pw[0] = 1;
    for(register int i = 1;i <= n;++i)
        pw[i] = 2LL * pw[i - 1] % mod,scanf("%d",a + i);
    f[0][0][0][0] = 1;
    for(register int i = 0;i < n;++i)
        for(register int j = 0;j < 2;++j)
            for(register int k = 0;k < 2;++k)
                for(register int h = 0;h < 2;++h)
                {
                    (a[i + 1] ^ 1) && (
                        f[i + 1][j][k][h] = (f[i + 1][j][k][h] + (long long)f[i][j][k][h] * (k > 0 ? pw[i - 1] : 0)) % mod,
                        f[i + 1][j | 1][k][h ^ 1] = (f[i + 1][j | 1][k][h ^ 1] + (long long)f[i][j][k][h] * pw[i - k]) % mod
                    );
                    a[i + 1] && (
                        f[i + 1][j][k][h] = (f[i + 1][j][k][h] + (long long)f[i][j][k][h] * (j > 0 ? pw[i - 1] : 0)) % mod,
                        f[i + 1][j][k | 1][h ^ 1] = (f[i + 1][j][k | 1][h ^ 1] + (long long)f[i][j][k][h] * pw[i - j]) % mod
                    );
                }
    for(register int i = 0;i < 2;++i)
        for(register int j = 0;j < 2;++j)
            ans = (ans + f[n][i][j][1]) % mod;
    printf("%d\n",ans);
}