【Codeforces 512D】Fox And Travelling

mrsrz 1月 24, 2020

拓扑排序，树形 DP。

题目大意：

给定一张 $n$ 个点 $m$ 条边的无向图。现在要遍历一些。一个点能被遍历，当且仅当与它相连的点中，至多一个点未被遍历。

现在对于所有 $k\in[1,n]$，求遍历 $k$ 个点，有多少不同的方案。

两个方案不同，当且仅当两个方案遍历的点存在不同，或遍历的顺序不同。

题解：

在环上的点显然是不可能遍历到的。被两个环夹在中间的点也不可能遍历到。我们可以用拓扑排序找到能遍历到的点和不能遍历到的点。而能遍历到的点，形成若干棵树。

考虑两种情况：

树上存在一个结点，和不能被遍历到的点相连。
树上不存在一个结点，和不能遍历到的点相连。

对于情况 $1$，这个结点只能是最后被遍历到的结点，我们令这个结点为根进行 dp。

对于情况 $2$，所有结点都可能是最后遍历到的，我们对所有点，都将其当根进行一次 dp。

具体地，令 $f[i][j]$ 表示以 $i$ 为根的子树中，遍历 $j$ 个点的方案数。

$f[i][j]=\sum_k f[son][j-k]\cdot f[i][j]\cdot\binom{j}{k}$

对于情况 $1$，这整棵树的 dp 值就是根的 dp 值。

对于情况 $2$，这整棵树的 dp 值是所有结点为根的 dp 值之和。但是对于任意一种选了 $j$ （$j\lt n$）个点的方案，在没选的 $n-j$ 个点作为根的时候都算了一遍，因此还要除以 $n-j$。

然后把每棵树的 dp 值再合并即可。合并的转移和上面一样。

由于是树上背包问题，所以时间复杂度可以优化至 $O(n^3)$。

Code：

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int md=1e9+9,N=105;
int fac[N],iv[N],iiv[N],n,m,deg[N],root[N],sz[N],size[N];
bool inc[N],flag[N];
int s[N],dp[N][N],g[N][N];
vector<int>G[N];
inline int C(int n,int m){return(LL)fac[n]*iv[m]%md*iv[n-m]%md;}
inline void upd(int&a){a+=a>>31&md;}
inline void merge(int*a,int*b,int*c,int lim){
    static int A[N];
    for(int i=0;i<=lim;++i){
        A[i]=0;
        for(int j=0;j<=i;++j)
        A[i]=(A[i]+(LL)b[j]*c[i-j]%md*C(i,j))%md;
    }
    for(int i=0;i<=lim;++i)a[i]=A[i];
    for(int i=lim+1;i<=n;++i)a[i]=0;
}
void topo(){
    queue<int>q;
    for(int i=1;i<=n;++i)if(deg[i]<=1)q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inc[u]=0;
        for(int to:G[u])
        if(--deg[to]<2&&inc[to])q.push(to);
    }
}
inline bool getflag(int u){
    bool&fg=flag[u];
    for(int to:G[u])
    if(inc[to])return fg=1;
    return 0;
}
void DfS(int now,int rt){
    root[now]=rt,sz[now]=1,flag[now]=flag[rt];
    for(int to:G[now])
    if(!inc[to]&&!root[to]){
        DfS(to,rt);
        sz[now]+=sz[to];
    }
}
void dFs(int now,int rt,int pre){
    sz[now]=1;
    for(int to:G[now])
    if(!inc[to]&&root[to]==rt&&to!=pre){
        dFs(to,rt,now);
        sz[now]+=sz[to];
    }
}
void dfs(int now,int pre){
    memset(dp[now],0,sizeof*dp);
    dp[now][0]=1;
    int lim=0;
    for(int to:G[now])if(to!=pre&&root[to]==root[now]){
        dfs(to,now);
        lim+=sz[to];
        merge(dp[now],dp[now],dp[to],lim);
    }
    dp[now][sz[now]]=dp[now][sz[now]-1];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=*fac=iiv[1]=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
    for(int i=2;i<=n;++i)iiv[i]=(md-md/i)*(LL)iiv[md%i]%md;
    for(int i=*iv=1;i<=n;++i)iv[i]=(LL)iv[i-1]*iiv[i]%md;
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        ++deg[u],++deg[v];
        G[u].push_back(v),G[v].push_back(u);
    }
    memset(inc,1,sizeof inc);
    topo();
    *s=1;
    for(int i=1;i<=n;++i)
    if(!inc[i]&&!root[i]&&getflag(i)){
        DfS(i,i);
        dfs(i,0);
        merge(s,s,dp[i],n);
    }
    for(int i=1;i<=n;++i)
    if(!inc[i]&&!flag[i]){
        if(!root[i])DfS(i,i),size[i]=sz[i];else dFs(i,root[i],0);
        dfs(i,0);
        for(int j=0;j<=size[root[i]];++j)
        upd(g[root[i]][j]+=dp[i][j]-md);
    }
    for(int i=1;i<=n;++i)
    if(!inc[i]&&!flag[i]&&root[i]==i){
        int*F=g[i];
        for(int j=0;j<size[i];++j)
        F[j]=(LL)F[j]*iiv[size[i]-j]%md;
        merge(s,s,F,n);
    }
    for(int i=0;i<=n;++i)printf("%d\n",s[i]);
    return 0;
}