有一张 \(n\) 个点 \(m\) 条边的简单无向图，每次选择一个度数小于等于 \(1\) 的点然后将其删除，对于每个 \(k\) 求删去 \(k\) 个点的方案数。\(n\le 100,\,m\le \frac{n\times(n-1)}{2}\)。
首先环上点肯定删不掉，如果一个连通块之间有两个环，那么被两个环夹着的点肯定也删不掉。
接下来我们考虑两件事情，一件事情就是如果一个连通块本身不是一棵树，那么如果它的一部分点能被删掉，那这部分点肯定组成一个森林，每棵树肯定之靠着一个环。外面的点先被删，而环旁边的点是最后被删的，那我们相当于对于每棵树就可以以环旁边那个点为根，然后 dp 上去。这个 dp 很方便，考虑到没两个点只会在其 LCA 上被合并一次，所以这部分的复杂度是 \(\mathcal{O}(n^2)\) 的。
然后我们考虑这个连通块本身就是一棵树的情况，这个情况下其实就是每个点都是可以作为 dp 的根的，这样做出来的话如果全删完那显然是对的，但是发现如果不删完的话是会算重的。我们考虑不删完的一种方案，如果留了 \(x\) 个节点，那么对于留下来的这 \(x\) 个节点，每个节点作为根 dp 的时候都会把这种方案算一遍。于是其实就是这种方案对答案的贡献是 \(x\) 而不是 \(1\) 了。于是我们就可以直接把 dp 出来的结构除以 \(x\) 便使答案了。
最后每个连通块的合并直接暴力卷一下就可以了，别忘了乘个组合数。
cpp
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x * 10) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
#define lowbit(x) (x & -x)
namespace dfcmd {
typedef long long LL;
const int maxn = 105;
const int mod = 1000000009;
inline int plus(int x, const int y) {
x += y;
if (x >= mod) {
x -= mod;
} else if (x < 0) {
x += mod;
}
return x;
}
inline void add(int& x, const int y) {
x += y;
if (x >= mod) {
x -= mod;
} else if (x < 0) {
x += mod;
}
}
inline int ksm(int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = (LL) a * a % mod) {
if (b & 1) {
ans = (LL) ans * a % mod;
}
}
return ans;
}
int n, m;
int mp[maxn][maxn];
int C[maxn][maxn];
int inv[maxn];
int du[maxn];
int rt[maxn];
int tg[maxn];
int vis[maxn];
inline vector<int> merge(const vector<int>& a, const vector<int>& b) {
vector<int> ans;
ans.resize(a.size() + b.size() - 1);
for (unsigned i = 0; i < a.size(); ++i) {
for (unsigned j = 0; j < b.size(); ++j) {
add(ans[i + j], (LL) a[i] * b[j] % mod * C[i + j][i] % mod);
}
}
// cout << "merge " << a.size() << ' ' << b.size() << ' ' << ans.size() << endl;
return ans;
}
int viss[maxn];
inline vector<int> dfs(int now) {
viss[now] = 1;
vector<int> ans;
ans.clear();
ans.push_back(1);
for (int to = 1; to <= n; ++to) {
if (!viss[to] && mp[now][to] && tg[to]) {
ans = merge(ans, dfs(to));
}
}
ans.push_back(*(--ans.end()));
return ans;
}
inline void Merge(vector<int>& ans, const vector<int>& b) {
ans.resize(max(ans.size(), b.size()));
for (unsigned i = 0; i < b.size(); ++i) {
add(ans[i], b[i]);
}
}
inline vector<int> bfs(int from) {
queue<int> q;
while(!q.empty()) {
q.pop();
}
q.push(from);
vis[from] = true;
vector<int> ans;
ans.clear();
while (!q.empty()) {
int now = q.front();
// cout << "now = " << now << endl;
q.pop();
// vector<int> xx;
memset(viss, 0, sizeof(viss));
Merge(ans, dfs(now));
/*
cout << "bfs " << now << ' ';
for (auto x : xx) {
cout << x << ' ';
}
cout << endl;
*/
for (int i = 1; i <= n; ++i) {
if (mp[now][i] && !vis[i] && tg[i]) {
vis[i] = true;
q.push(i);
}
}
}
/*
cout << "bfs ";
for (auto x : ans) {
cout << x << ' ';
}
cout << endl;
*/
for (unsigned i = 0; i < ans.size(); ++i) {
ans[i] = (LL) ans[i] * inv[ans.size() - i - 1] % mod;
}
/*
cout << "bfs ";
for (auto x : ans) {
cout << x << ' ';
}
cout << endl;
*/
return ans;
}
int Main() {
read(n), read(m);
inv[0] = 1;
for (int i = 1; i <= n; ++i) {
inv[i] = ksm(i, mod - 2);
}
for (int i = 1, u, v; i <= m; ++i) {
read(u), read(v);
mp[u][v] = mp[v][u] = 1;
du[u]++, du[v]++;
}
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; ++j) {
C[i][j] = plus(C[i - 1][j - 1], C[i - 1][j]);
}
}
queue<int> q;
while (!q.empty()) {
q.pop();
}
for (int i = 1; i <= n; ++i) {
if (du[i] <= 1) {
q.push(i);
tg[i] = 1;
}
}
while (!q.empty()) {
int now = q.front();
// cout << "Bfs " << now << endl;
q.pop();
for (int i = 1; i <= n; ++i) {
if (!tg[i] && mp[now][i]) {
// cout << "Bfs to " << i << endl;
du[i]--;
if (du[i] <= 1) {
q.push(i);
tg[i] = 1;
}
}
}
}
/*
cout << "tg = ";
for (int i = 1; i <= n; ++i) {
cout << tg[i] << ' ';
}
cout << endl;
*/
for (int i = 1; i <= n; ++i) {
if (tg[i] && !vis[i]) {
bool flg = false;
for (int j = 1; j <= n; ++j) {
if (mp[i][j] && !tg[j]) {
flg = true;
break;
}
}
if (flg) {
while (!q.empty()) {
q.pop();
}
q.push(i);
rt[i] = 1;
vis[i] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int j = 1; j <= n; ++j) {
if (mp[now][j] && tg[j] && !vis[j]) {
q.push(j);
vis[j] = 1;
}
}
}
}
}
}
vector<int> ans;
ans.clear();
ans.push_back(1);
for (int i = 1; i <= n; ++i) {
if (!vis[i] && tg[i]) {
ans = merge(ans, bfs(i));
}
}
/*
cout << "rt = ";
for (int i = 1; i <= n; ++i) {
cout << rt[i] << ' ';
}
cout << endl;
*/
for (int i = 1; i <= n; ++i) {
if (rt[i]) {
// cout << "rt " << i << endl;
memset(viss, 0, sizeof(viss));
/*
auto xx = dfs(i);
for (auto x : xx) {
cout << x << ' ';
}
cout << endl;
*/
ans = merge(ans, dfs(i));
}
}
for (auto x : ans) {
writeln(x);
}
for (int i = ans.size(); i <= n; ++i) {
puts("0");
}
return 0;
}
}
int main() {
return dfcmd::Main();
}