#PQZ1046x5089. 环覆盖

    ID: 2506 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>QOJ官方数据QOJ公开样例级数据-覆盖不足来源赛事1046动态规划

环覆盖

环覆盖

题目描述

标题: 环覆盖 - Problem - QOJ.ac

Statistics

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 默认逐字节比对判定。