JZOJ 6553 人生

发表于 | 分类于 |

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

设 \(\mathrm{end}(i)\) 表示以点 \(i\) 结尾的合法路径的条数。
设 \(f_{i,j,k,h}\) 表示前 \(i\) 个点，有 \(j\) 个白点满足其 \(\mathrm{end}\) 值为奇数，有 \(k\) 个黑点满足其 \(\mathrm{end}\) 值为偶数，\(\sum\limits_{i=1}^n \mathrm{end}(i) \equiv h \pmod 2\) 有多少方案。

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

然而注意到两点：

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

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

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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);
}