#P6825. [2019年广州]覆盖

    ID: 6657 传统题 1500ms 512MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-构造与建模对称性分析补集转化图论最大权独立集动态规划计数 DP多项式与生成函数生成函数求系数组合数学Lucas 定理位运算位并行动态规划滚动数组CF2900

[2019年广州]覆盖

覆盖

题目描述

对于简单无向图 G=(V,E)G=(V,E),点覆盖是一个顶点集合 S⊆VS\subseteq V,使每条边至少有一个端点在 SS 中,即

∀(u,v)∈E,u∈S ∨ v∈S.\forall (u,v)\in E,\qquad u\in S\ \lor\ v\in S.

最小点覆盖大小是所有点覆盖的最小大小。

给定 n,kn,k,求有多少张顶点编号为 1,2,…,n1,2,\ldots,n 的图,其最小点覆盖大小恰好为 kk。图不含自环和重边;只要存在一条边在两图中的存在情况不同,就认为这两图不同。顶点编号不同的图分别计数。

答案对 22 取模。

输入格式

第一行一个整数 qq,表示询问个数。

接下来 qq 行,每行两个整数 n,kn,k。

输出格式

输出 qq 行,每行一个整数 00 或 11,表示相应图的数量对 22 取模的结果。

样例 1 输入

1
3 1

样例 1 输出

0

样例 1 解释

三个顶点共有 88 张简单无向图。除空图和完全图外,其余 66 张图的最小点覆盖大小均为 11,故答案为 6 mod 2=06\bmod2=0。

样例 2

原题面引用 cover/cover2.in 和 cover/cover2.ans。当前本地附件未包含这些公开样例文件。

数据范围与子任务

所有数据满足 1≤q≤50001\le q\le5000,1≤k≤n≤10001\le k\le n\le1000。

子任务 分值 附加限制
1 2020 n≤20n\le20
2 n≤60n\le60
3 n≤200n\le200
4 q≤10q\le10
5 无