题目分析

题目要求统计满足“交错路数量奇偶性为 (p)”的图和颜色组合数。交错路定义为相邻点颜色不同的有向路径，需结合颜色选择和边的选择，通过动态规划（DP）跟踪关键状态的奇偶性。

解题思路

1. 状态定义：

   • f[i][x][y][z]：前 (i) 个点中，最后一个点颜色为 (y)（0白/1黑），前 (i) 个点中以白色结尾的点数量奇偶性为 (x)，交错路总数奇偶性为 (z) 的方案数。

2. 状态转移：

   • 对第 (i) 个点的颜色（0/1）分别处理，考虑与前 (i-1) 个点的连边情况：
     • 若第 (i) 个点为黑色（(y=1)），则与前 (i-1) 个白色点的连边会增加交错路，需更新奇偶性。
     • 若第 (i) 个点为白色（(y=0)），则与前 (i-1) 个黑色点的连边会增加交错路，需更新奇偶性。
   • 边的选择数通过预处理的 (2) 的幂次快速计算。

3. 结果计算：

   • 统计所有颜色组合下，交错路奇偶性为 (p) 的方案数之和。

代码实现（带注释）

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int kMaxN = 2e5 + 10;
const int kMod = 998244353;

int n, p;
int c[kMaxN];               // 节点颜色（0白/1黑/-1不确定）
int f[kMaxN][2][2][2];      // DP状态：f[i][x][y][z]
int pow2[kMaxN];            // 预处理2的幂次

// 模加法
void add(int &x, int y) {
    x += y;
    if (x >= kMod)
        x -= kMod;
}

int ans;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> p;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];

    // 预处理2的幂次
    pow2[0] = 1;
    for (int i = 1; i <= n; ++i)
        pow2[i] = pow2[i - 1] * 2 % kMod;

    // 初始化：前0个点，无颜色，交错路数为0
    f[0][0][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int x = 0; x < 2; ++x) {   // 前i-1个点中白色结尾的数量奇偶性
            for (int y = 0; y < 2; ++y) {   // 前i-1个点的最后颜色
                for (int z = 0; z < 2; ++z) {   // 前i-1个点的交错路奇偶性
                    // 尝试将第i个点设为黑色（1）
                    if (c[i] == 1 || c[i] == -1) {
                        if (!x) {  // 前i-1个点中白色结尾的数量为偶数
                            // 所有边都连向黑色，增加交错路，奇偶性翻转
                            add(f[i][x][1][z ^ 1], f[i - 1][x][y][z] * pow2[i - 1] % kMod);
                        } else {  // 前i-1个点中白色结尾的数量为奇数
                            // 一半边连向黑色（不增加交错路），一半连向白色（增加交错路）
                            add(f[i][x][y][z], f[i - 1][x][y][z] * pow2[i - 2] % kMod);
                            add(f[i][x][1][z ^ 1], f[i - 1][x][y][z] * pow2[i - 2] % kMod);
                        }
                    }

                    // 尝试将第i个点设为白色（0）
                    if (c[i] == 0 || c[i] == -1) {
                        if (!y) {  // 前i-1个点的最后颜色为白色
                            // 所有边都连向白色，增加交错路，奇偶性翻转
                            add(f[i][1][y][z ^ 1], f[i - 1][x][y][z] * pow2[i - 1] % kMod);
                        } else {  // 前i-1个点的最后颜色为黑色
                            // 一半边连向白色（不增加交错路），一半连向黑色（增加交错路）
                            add(f[i][x][y][z], f[i - 1][x][y][z] * pow2[i - 2] % kMod);
                            add(f[i][1][y][z ^ 1], f[i - 1][x][y][z] * pow2[i - 2] % kMod);
                        }
                    }
                }
            }
        }
    }

    // 统计所有颜色组合下，交错路奇偶性为p的方案数
    for (int a = 0; a < 2; ++a) {
        for (int b = 0; b < 2; ++b) {
            add(ans, f[n][a][b][p]);
        }
    }

    cout << ans << '\n';
    return 0;
}

代码解释

1. 预处理幂次：预先计算 (2^k \mod 998244353)，用于快速计算边的选择数。
2. DP初始化：前0个点的初始状态为无颜色、无交错路。
3. 状态转移：对每个点的颜色（0/1）分别处理，根据前序状态更新当前状态的交错路奇偶性。
4. 结果统计：累加所有颜色组合下满足奇偶性要求的方案数。