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);
}