CF512D Fox And Travelling

题意

给定一张\(n\)个点\(m\)条边的无向图。
一个点只有当与它直接相连的点中最多只有一个点未被遍历过时才可被遍历。
询问对于每个\(k \in [0,n]\)，遍历\(k\)个点的方案数。
\(n \le 100，m \le \frac{n(n-1)}2\) ，答案对\(10^9+9\)取模。
传送门

思路

首先，在环中的点以及被两个环夹着的点一定不会被遍历。

用类似拓扑排序的过程可以这些无法被排到的点全部扔掉（遇到不能确定的就不排了），剩下的点会构成若干个有根树和无根树，其中有根树的根是树中唯一与环中的点相连的点。

对于有根树，设\(dp_{i,j}\)，为\(i\)的子树中选\(j\)个的方案数，那么就是树上背包。合并两个背包时，两背包内物体的相对顺序没有关系，两个序列可以随意插，所以要乘上\(C(k+j,k)\)。最后考虑这个点要不要选，选择一个点，它的子树必须全部都被访问到且它一定是最后一个所以\(dp[i][size]=dp[i][size-1]\)。

对于无根树，以树中每个点为根做一次有根树的树上背包，这样会发现每种选择\(i\)个点的方案会被多算\(size - i\)次（不在方案内的点都可以做一次根），那么除掉即可。

每棵树求出答案后，01 背包合并即可。

#include <bits/stdc++.h>
using std::queue;
const int N=105,M=N*N,mu=1000000009;
int to[M],edge,Next[M],last[N],Inv[N],inv[N],p[N],ans[N],t[N],dp[N][N],s[N];
int n,m,x,y,rt[N],d[N],size[N],vis[N];
queue <int> q; 
void add(int x,int y){
    to[++edge]=y;
    Next[edge]=last[x];
    last[x]=edge;
}
int ksm(int x,int y){
    int ans=1;
    for (;y;y>>=1,x=x*1ll*x%mu)
        if (y&1) ans=ans*1ll*x%mu;
    return ans; 
}
void init(){
    Inv[0]=1;
    for (int i=1;i<=n;i++) Inv[i]=ksm(i,mu-2);
    p[0]=inv[0]=1;
    for (int i=1;i<=n;i++) p[i]=p[i-1]*1ll*i%mu,inv[i]=inv[i-1]*1ll*Inv[i]%mu;
}
int C(int x,int y){
    return 1ll*p[x]*inv[y]%mu*inv[x-y]%mu; 
}
void dfs(int x,int y){
    rt[x]=y;
    s[x]=1;
    for (int i=last[x];i;i=Next[i]){
        int u=to[i];
        if (d[u]==0 && !rt[u]){
            dfs(u,y);
            s[x]+=s[u]; 
        }
    }
}
int Dfs(int x,int fa){
    dp[x][0]=1;
    size[x]=0;
    for (int i=last[x];i;i=Next[i]){
        int u=to[i];
        if (u==fa || rt[u]!=rt[x]) continue;
        Dfs(u,x);
        for (int j=size[x]+1;j<=size[x]+size[u];j++) dp[x][j]=0;
        for (int j=size[x];j>=0;j--)
            for (int k=1;k<=size[u];k++)
                dp[x][j+k]=(dp[x][j+k]+dp[u][k]*1ll*dp[x][j]%mu*C(j+k,j))%mu; 
        size[x]+=size[u];
    }
    size[x]+=1;
    dp[x][size[x]]=dp[x][size[x]-1];
}
int main(){ 
    scanf("%d%d",&n,&m);
    init();
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
        d[x]++,d[y]++;
    }
    for (int i=1;i<=n;i++) if (d[i]<=1) q.push(i),vis[i]=1;
    while (!q.empty()){
        int x=q.front();
        q.pop();
        for (int i=last[x];i;i=Next[i]){
            int u=to[i];d[u]--;
            if (d[u]<=1 && !vis[u]){
                vis[u]=1;
                q.push(u);
            }
        }
    }
    for (int i=1;i<=n;i++)//有根树
        if (d[i]==1) dfs(i,i);
    for (int i=1;i<=n;i++)
        if (d[i]==0 && !rt[i]) dfs(i,i);
    int now=0;
    ans[0]=1;
    for (int i=1;i<=n;i++){
        if (i!=rt[i]) continue; 
        if (d[i]){
            Dfs(i,0);
            for (int j=0;j<=s[i];j++) t[j]=dp[i][j];
        }else{
            for (int j=0;j<=s[i];j++) t[j]=0;
            for (int j=1;j<=n;j++)
                if (rt[j]==i) {
                    Dfs(j,0);
                    for (int k=0;k<=s[i];k++) t[k]=(t[k]+dp[j][k])%mu;
                }
            for (int j=0;j<=s[i];j++) t[j]=1ll*t[j]*Inv[s[i]-j]%mu;
        }
        for(int j=now;j>=0;j--)
             for (int k=1;k<=s[i];k++)
                ans[j+k]=(ans[j+k]+ans[j]*1ll*t[k]%mu*C(j+k,k))%mu;
        now=now+s[i];
    } 
    for (int i=0;i<=n;i++) printf("%d\n",ans[i]);
}

后记

效率低下的一个早上

CF512D Fox And Travelling

原文：https://www.cnblogs.com/flyfeather6/p/12213107.html