#PQZ1046x5089. 环覆盖
环覆盖
环覆盖
题目描述
标题: 环覆盖 - Problem - QOJ.ac
The problem was used in the following contests:
形式化题意:给定一张 n 个点,m 条边的简单无向图,对每个 i∈[0,m],计算它只保留 i 条边,使得剩下的图是一个可环覆盖图的方案数。可环覆盖的定义是,可以将边集划分成若干个子集,使得每个子集都形成一个环。
答案对 109+7 取模。
输入格式
第一行两个整数 n,m。
接下来 m 行,每行两个数 u,v,代表一条边。
输出格式
一行 m+1 个整数,第 k 个表示题面中 i=k−1 时的答案。
样例输入1
3 3
1 2
1 3
2 3
样例输出1
1 0 0 1
样例1解释
只有保留 0 条边和保留 3 条边的两个方案是合法的。
样例输入2
6 10
1 2
1 3
1 4
1 5
1 6
2 4
3 4
3 5
4 5
4 6
样例输出2
1 0 0 6 8 4 4 6 3 0 0
数据范围
对于所有数据,1≤n≤25,0≤m≤n(n−1)2。
Subtask 1(5pts):n,m≤20。
Subtask 2(15pts):n≤20,m≤40。依赖 Sub 1。
Subtask 3(15pts):n=25,m=45,图连通。
Subtask 4(30pts):n≤20。依赖 Sub 2。
Subtask 5(35pts):无特殊限制。依赖 Sub 4。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
官方测试点 25 个;落地 2 个;时限 1.0s,内存 512MB。
样例
样例 1
3 3
1 2
1 3
2 3
1 0 0 1
样例 2
6 10
1 2
1 3
1 4
1 5
1 6
2 4
3 4
3 5
4 5
4 6
1 0 0 6 8 4 4 6 3 0 0
数据来源:QOJ 公开题包官方 .in/.out;本题落地 2 个测试点,QOJ 元数据标注官方共 25 点,覆盖级别:部分公开样例级数据。时限 1.0s,内存 512MB。按 Hydro 默认逐字节比对判定。