PA 2016 Runda 5 Pokrycia 题解

题目理解

本题要求计算在 n 个顶点的无向简单图中，最小顶点覆盖大小恰好为 k 的图的数量，并输出结果对 2 取模的值。

关键概念：

• 顶点覆盖：图中边的集合，使得每条边至少有一个端点在集合中
• 最小顶点覆盖：大小最小的顶点覆盖
• 无向简单图：无自环、无重边的图

算法分析

核心算法：动态规划 + 位运算

代码使用了动态规划和位运算技巧来解决这个问题：

1. 动态规划状态设计：

   • f[i][j] 表示在 i 个顶点的图中，满足某种性质的方案数的奇偶性
   • g[i][j] 是 f[i][j] 的某种前缀异或和

2. 状态转移方程：

   f[i][j] = f[i-1][j-1] XOR f[i-1][j+lowbit(j)-1]
   

3. 位运算优化：

   • 使用 bitset<N> 存储状态，高效处理位运算
   • lowbit(x) 函数获取 x 的最低有效位

算法思路

该算法基于组合数学和动态规划，通过巧妙的位运算来处理模 2 情况下的计数问题。核心思想是：

• 利用图的组合结构性质，将问题转化为可递推的形式
• 在模 2 意义下，异或运算等价于加法
• 通过预处理所有可能的 (n,k) 组合，实现 O(1) 查询

查询处理

对于每个查询 (n, k)，直接输出 g[n][n-k] 的值，即：

• 将最小顶点覆盖为 k 的问题转换为对应的预处理值
• 结果已经是模 2 后的值 (0 或 1)

代码特点

1. 高效预处理：在程序开始前计算所有可能的状态
2. 空间优化：使用 bitset 减少内存占用
3. 查询快速：预处理后每个查询 O(1) 时间
4. 模 2 优化：利用异或运算天然处理模 2 情况

总结

该解法通过巧妙的动态规划和位运算技巧，将看似复杂的图计数问题转化为高效的位操作，在模 2 的特殊要求下实现了最优解。