[CF 512D] Fox And Travelling

作法：

這題簡單來說就是，每次操作可以把圖中一個度 <= 1 的點拔掉，問拔掉 k 個點有幾種順序，對於每個 k 都要輸出答案。首先考慮我們最多能拔幾個點，也就是先不斷的從圖中拔去度 <= 1 的點(類似拓僕排序的過程)，那麼最後剩下來的東西就是不管怎麼樣都沒辦法被拔掉的點們（我記得這東西叫作一個圖的核( core ) ，但網路上查到的都是另一個東西，可能是我記錯了）。因此整張圖就被分成了核和一堆樹了，其中有些樹是黏在核上的，有些樹是沒有黏在核上的。因此我們可以先對每棵樹分別求出「在這棵樹中拔掉 k 個點有幾種方法」的陣列，最後再把他們合併起來就好了。

但在處理單棵樹時，上面提到的那兩種樹的處理方法會不一樣，因為黏在核上的樹的根節點（也就是和核有連邊的那個點）一定要是最後被拔掉的，而沒有黏在核上的則是不必要，也就是我們要處理有根樹和無根樹的問題。先看有根樹的情形，對每個點 x 來說， 算出 dp[ x ][ k ] ( k = 0 ~ x 子樹的 size )，代表在 x 的子樹中拔掉 k 個點有幾種拔法。當 x 是葉子時他們的值是顯然的，而當 x 不是葉子時，假設他的子樹們為 T_1 ~ T_r ，那麼現在等於是要把這 r 個 dp 表格合併成一個 dp[ x ] 。假設我們現在要算 dp[ x ][ k ]，那麼總不能去枚舉所有的 b_1 ~ b_r 使得 b_1 + ... + b_r = k 吧！也就是如果要在 x 的子樹中拔 k 個點，那麼去枚舉每個子樹分別要拔幾個點。這樣複雜度顯然會爛掉，但如果只有兩個子樹，那麼事情就簡單多了，枚舉第一個子樹要砍的點的個數 j ，還有第二個子樹要砍的點的個數 k ，那麼 dp[ x ][ j+k ] 的值就要加上 C( j+k , j ) * dp[ T_1 ][ j ] * dp[ T_2 ][ k ]，其中要乘以 C( j+k , j ) 是因為 T_1 和 T_2 中的點可以輪流拔。因此這啟發了我們可以一棵一棵合併子樹，也就是先合併 T_1 , T_2 ，再把合併後的結果拿去跟 T_3 合併，以此類推。這樣就等於是在合併完 T_1 ~ T_i 時，表格裡存的東西是「在這 i 棵子樹中拔掉 k 個點的方法數」，因此把所有子樹都合併完之後就是我們需要的 dp[ x ] ，不過還必須記得要加上 dp[ x ][ sz ] = dp[ x ][ sz-1 ]，其中 sz 為 x 的子樹的大小，因為那 r 棵子樹的大小加起來剛好會是 sz-1 ，而 sz 的值也是需要的，但因為根永遠是最晚被拔的點，所以他的值就會等於 dp[ x ][ sz-1 ]。這樣看起來在計算 dp[ x ] 的時候複雜度會噴到 O( n^2 )，一次 DP 一棵樹的複雜度是 O(n^3) ，但實際上可以用和 TIOJ 1243 的解一樣的手法把複雜度壓成 O( n^2 )，這裡就不再詳細敘述。

處理完有根樹後再來是無根樹，而無根樹有個很重要的性質，就是如果我們直接把每個點都當成根算一次答案，把他們全部加起來，那麼對於任意一個在樹中拔掉 k 個點的拔法來講，他恰好會被算到 max( n-k , 1 ) 次！( 其中 n 是這棵樹的大小 )，也就是只要再把得到的答案分別乘上 n-k 的模逆元就可以了。最後在把所有有根樹和無根樹的答案合併起來的時候，也是用和在DP時同樣的方法就可以處理了，這樣總複雜度會是 O( n^3 )，不過事實上 O( n^4 )也可以過，也就是在 DP 的部份可以允許一次是 O( n^3 ) 的，畢竟 codeforces 主機跑超快XDD。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000009
using namespace std;
const int maxn=100+10 ;
 
LL power(LL x,int n)
{
    if(n<=1) return n ? x : 1LL ;
    LL tmp=power(x,n/2) ;
    if(n&1) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
LL inv(LL x)
{
    return power(x,MOD-2) ;
}
 
LL C[maxn][maxn] ;
void build_C()
{
    for(int i=0;i<maxn;i++) for(int j=0;j<=i;j++)
        C[i][j]=((j==0 || j==i) ? 1 : (C[i-1][j]+C[i-1][j-1])%MOD) ;
}
 
int n ;
vector<int> v[maxn] ;
 
bool core[maxn],vis[maxn] ;
void topo()
{
    queue<int> q ;
    int deg[maxn] ;
    for(int i=1;i<=n;i++)
    {
        deg[i]=v[i].size() ;
        if(deg[i]<=1) vis[i]=1 , q.push(i) ;
    }
    while(!q.empty())
    {
        int u=q.front() ; q.pop() ;
        for(auto i : v[u]) if(!vis[i] && ((--deg[i])==1))
        {
            vis[i]=1 ;
            q.push(i) ;
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]) core[i]=1 ;
}
 
LL dp[maxn][maxn],tmp[maxn] ;
int sz[maxn] ;
void DP(int x,int f)
{
    sz[x]=1 ;
    for(auto i : v[x]) if(i!=f && !core[i])
        DP(i,x) , sz[x]+=sz[i] ;
    if(sz[x]==1) { dp[x][0]=dp[x][1]=1 ; return ; }
 
    int cnt=0,sum=0 ;
    for(auto i : v[x]) if(i!=f && !core[i])
    {
        if(!(cnt++))
        {
            for(int j=0;j<=sz[i];j++) dp[x][j]=dp[i][j] ;
            sum=sz[i] ;
            continue ;
        }
        fill(tmp,tmp+sum+sz[i]+1,0) ;
        for(int j=0;j<=sum;j++) for(int k=0;k<=sz[i];k++)
            tmp[j+k]+=(C[j+k][j]*dp[x][j]%MOD)*dp[i][k]%MOD ,
            tmp[j+k]%=MOD ;
        for(int j=0;j<=sum+sz[i];j++) dp[x][j]=tmp[j] ;
        sum+=sz[i] ;
    }
    dp[x][sz[x]]=dp[x][sz[x]-1] ;
}
 
vector<int> tr[maxn] ;
int tcnt=0 ;
void dfs(int x)
{
    vis[x]=1 ;
    tr[tcnt].push_back(x) ;
    for(auto i : v[x]) if(!vis[i] && !core[i]) dfs(i) ;
}
 
int root[maxn],type[maxn] ; /// type=1 : rooted , type=2 : unrooted
void get_tree()
{
    memset(vis,0,sizeof(vis)) ;
    for(int i=1;i<=n;i++) if(core[i])
        for(auto j : v[i]) if(!core[j])
    {
        dfs(j) ;
        root[tcnt]=j ;
        type[tcnt]=1 ;
        tcnt++ ;
    }
    for(int i=1;i<=n;i++) if(!vis[i] && !core[i])
    {
        dfs(i) ;
        root[tcnt]=i ;
        type[tcnt]=2 ;
        tcnt++ ;
    }
}
 
LL ways[maxn][maxn] ;
void getways(int id)
{
    if(type[id]==1)
    {
        DP(root[id],-1) ;
        for(int i=0;i<=sz[root[id]];i++)
            ways[id][i]=dp[root[id]][i] ;
    }
    else
    {
        for(auto x : tr[id])
        {
            DP(x,-1) ;
            for(int i=0;i<=sz[x];i++)
                ways[id][i]=(ways[id][i]+dp[x][i])%MOD ;
        }
        int s=tr[id].size() ;
        for(int i=0;i<=s;i++)
        {
            if(i==s) ways[id][i]=ways[id][i-1] ;
            else ways[id][i]=ways[id][i]*inv(s-i)%MOD ;
        }
    }
}
 
LL ans[maxn] ;
void merge_ways()
{
    for(int i=0,sum=0;i<tcnt;i++)
    {
        int s=tr[i].size() ;
        if(!i)
        {
            for(int j=0;j<=s;j++) ans[j]=ways[i][j] ;
            sum=s ;
            continue ;
        }
 
        fill(tmp,tmp+sum+s+1,0) ;
        for(int j=0;j<=sum;j++) for(int k=0;k<=s;k++)
            tmp[j+k]+=(C[j+k][j]*ans[j]%MOD)*ways[i][k]%MOD ,
            tmp[j+k]%=MOD ;
        for(int j=0;j<=sum+s;j++) ans[j]=tmp[j] ;
        sum+=s ;
    }
}
 
main()
{
    build_C() ;
    int m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    topo() ;
    get_tree() ;
    for(int i=0;i<tcnt;i++) getways(i) ;
    merge_ways() ;
    if(!tcnt) ans[0]=1 ;
    for(int i=0;i<=n;i++) printf("%lld\n",ans[i]) ;
}