#6497. 「雅礼集训 2018 Day1」图
Summarize
题目概括征集中~
Solution
特别屌的一个计数 DP。
记 $g(i)$ 表示以 $i$ 节点结尾的交错路径条数。
定义状态：$f[i][k][x][y]$ 表示考虑前 $i$ 个节点，奇偶性为 $k=0/1$； $x=0/1$ 表示是否存在 $g()$ 为奇数的黑色节点， $y=0/1$ 表示是否存在 $g()$ 为奇数的白色节点。
考虑转移：假设已经求出 $f[i][k][x][y]$。枚举第 $i+1$ 个节点的颜色。
当第 $i+1$ 个节点为白色时：
如果 $x=0$，即不存在 $g()$ 为奇数的黑色节点，那么无论如何连边，总的原方案的奇偶性一定会发生改变。考虑如果有黑色节点向 $i+1$ 连边，则交错路径会增加偶数条（即增加 $g()$）；如果有白色节点向其连边，则交错路径数不变；第 $i+1$ 个节点单独作为一条路径，因此交错路径增加了奇数条，奇偶性发生改变。
转移方程：
$$
f[i+1][k\oplus1][x][1]=f[i+1][k\oplus1][x][1]+2^i\times f[i][k][x][y]
$$
如果 $x=1$，那么情况会略微复杂；注意到如果有偶数个 $g()$ 为奇数的黑色节点向 $i+1$ 连边，则奇偶性一定改变；如果有奇数个 $g()$ 为奇数的黑色节点向 $i+1$ 连边，则奇偶性不会改变。假设 $g()$ 为奇数的黑色节点共有 $t$ 个。那么转移方程如下：
$$
f[i+1][k\oplus1][x][1]=f[i+1][k\oplus1][x][1]+({t\choose0}+{t\choose2}+..+{t\choose 2m})\times 2^{i-t}\times f[i][k][x][y]
$$
$$
f[i+1][k][x][y]=f[i+1][k][x][y]+({t\choose1}+{t\choose3}+..+{t\choose 2m+1})\times 2^{i-t}\times f[i][k][x][y]
$$
可以证明：
$$
{t\choose0}+{t\choose2}+..+{t\choose 2m}={t\choose1}+{t\choose3}+..+{t\choose 2m+1}=2^{t-1}
$$
因此转移方程可以简化为：
$$
f[i+1][k\oplus1][x][1]=f[i+1][k\oplus1][x][1]+2^{i-1}\times f[i][k][x][y]
$$
$$
f[i+1][k][x][y]=f[i+1][k][x][y]+2^{i-1}\times f[i][k][x][y]
$$
当第 $i+1$ 个节点为黑色时，情况类似。
代码实现非常简单，不再赘述。
Code
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MOD = 998244353;
int n, p;
int f[MAXN][2][2][2];
int c[MAXN];
int pow2[MAXN];
int main() {
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; ++i)
scanf("%d", &c[i]);
pow2[0] = 1;
for (int i = 1; i <= n; ++i) {
pow2[i] = pow2[i - 1] << 1;
if (pow2[i] > MOD) pow2[i] -= MOD;
}
f[0][0][0][0] = 1;
for (int i = 0; i < n; ++i)
for (int k = 0; k <= 1; ++k)
for (int x = 0; x <= 1; ++x)
for (int y = 0; y <= 1; ++y) {
int cur = f[i][k][x][y];
if (c[i + 1] == -1 || c[i + 1] == 0) {
if (x == 0)
f[i + 1][k ^ 1][x][1] =
(f[i + 1][k ^ 1][x][1] + 1ll * pow2[i] * cur) % MOD;
else
f[i + 1][k ^ 1][x][1] =
(f[i + 1][k ^ 1][x][1] + 1ll * pow2[i - 1] * cur) % MOD,
f[i + 1][k][x][y] =
(f[i + 1][k][x][y] + 1ll * pow2[i - 1] * cur) % MOD;
}
if (c[i + 1] == -1 || c[i + 1] == 1) {
if (y == 0)
f[i + 1][k ^ 1][1][y] =
(f[i + 1][k ^ 1][1][y] + 1ll * pow2[i] * cur) % MOD;
else
f[i + 1][k ^ 1][1][y] =
(f[i + 1][k ^ 1][1][y] + 1ll * pow2[i - 1] * cur) % MOD,
f[i + 1][k][x][y] =
(f[i + 1][k][x][y] + 1ll * pow2[i - 1] * cur) % MOD;
}
}
printf("%d", (f[n][p][0][0] + f[n][p][0][1] + f[n][p][1][0] + f[n][p][1][1]) % MOD);
return 0;
}
|