#P6825. [2019年广州]覆盖
[2019年广州]覆盖
覆盖
题目描述
对于简单无向图 ,点覆盖是一个顶点集合 ,使每条边至少有一个端点在 中,即
最小点覆盖大小是所有点覆盖的最小大小。
给定 ,求有多少张顶点编号为 的图,其最小点覆盖大小恰好为 。图不含自环和重边;只要存在一条边在两图中的存在情况不同,就认为这两图不同。顶点编号不同的图分别计数。
答案对 取模。
输入格式
第一行一个整数 ,表示询问个数。
接下来 行,每行两个整数 。
输出格式
输出 行,每行一个整数 或 ,表示相应图的数量对 取模的结果。
样例 1 输入
1
3 1
样例 1 输出
0
样例 1 解释
三个顶点共有 张简单无向图。除空图和完全图外,其余 张图的最小点覆盖大小均为 ,故答案为 。
样例 2
原题面引用 cover/cover2.in 和 cover/cover2.ans。当前本地附件未包含这些公开样例文件。
数据范围与子任务
所有数据满足 ,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | 无 |