# CodeForces 512D Fox And Travelling

Author: Fanyi Pu

Published: 2020-02-14

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/cf512d>

CodeForces 512D Fox And Travelling 题解。

有一张 $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$ 便使答案了。

最后每个连通块的合并直接暴力卷一下就可以了，别忘了乘个组合数。

[代码在这里](https://codeforces.com/contest/512/submission/71034596)

```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();
}
```