#P15254. [2026队内训练]集合计数
[2026队内训练]集合计数
题目描述
给定一张 个顶点的无向图 ,顶点编号为 。它可以由某个 的排列 生成。对于任意 ,顶点 之间有边当且仅当 。输入直接给出图的边,排列不作为输入。
点集 是独立集,当且仅当 中任意两个不同顶点均不相邻。它是支配集,当且仅当 以外的每个顶点至少与 中一个顶点相邻。
求同时是独立集与支配集的点集数量,对 取模。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,表示一条无向边。保证图由上述方式生成。
输出格式
一行一个非负整数,表示答案对 取模的结果。
样例
5 7
2 5
1 5
3 5
2 3
4 1
4 3
4 2
3
图对应排列 。三个独立支配集是 、、。
数据范围
,。原 PDF 将 的下界写为 ,本站评测包含无边图。
| 原子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 20 | |
| 2 | ||
| 3 | 60 | 无 |