题解 CF512D 【Fox And Travelling】

· · 题解

这道题n=100还有三秒时限，所以大家纷纷使用O(n^3)算法通过了。下面我提供一种O(n^2)的算法。

首先，把输入的图求边双、缩点。如果一个边双有至少两个点，这个边双中的任何一个点就肯定不可能被遍历到（因为环里没有叶子）。所以，只需要考虑缩点之后的森林，其中有一些点不能选的情况下，遍历k个节点的方案数（因为现在可以选的点和原图的点是一一对应的）。

森林里的每棵树显然是独立的。由于可以自由组合，答案的EGF就是每棵树答案的EGF的卷积。所以我们只需要会求每一棵树的答案，就可以用O(n^2)的暴力卷积求出整个森林的答案。

考虑一棵树的答案是怎么求出来的。容易发现，最终被遍历到的点一定是这棵（无根）树的一些（两两不交的）子树。令G_t表示（无根）子树t答案的EGF，那么这棵树的EGF就等于

\sum_{S\textrm{是一些子树的集合}}\prod_{\textrm{子树}t\in S}G_t

乍一看挺对的？然而这个等式其实会重复计算一些方案。比如说第一个样例，序列[1,3,2]会在子树集合为\{\{1,2\},\{3\}\}时计算到，也会在子树集合为\{\{1\},\{2,3\}\}时计算到。

但是这个等式在绝大多数情况下都是对的。准确地说，如果没有选中全部的点，就不会造成重复的计算。所以分成两部分考虑：选中了这棵树中所有的点时对答案的贡献；没有全部选中时对答案的贡献。整棵树的答案就是把这两部分贡献加起来就行了。

选中了一棵树中全部的点的方案数

注意这里用的是“方案数”而不是EGF，因为点数已经被固定了。

考虑枚举最后一个遍历到的点。假设其为p。此时可以把p定为整棵树的根，题目的限制就变成了“遍历一个点之前，必须遍历其子树中所有的点”。可以发现这样统计是不重不漏的。

考虑dp。设F_i为以p为根时，i子树内的遍历方案数。由于各个子树之间是独立的，可以自由组合，并且i在其子树之内一定最后才被遍历，有一个简单的转移：

F_i=(siz_i-1)!\prod_{j\textrm{是}i\textrm{的儿子}}\frac{F_j}{siz_j!}

这里的siz_i是子树i的大小。当然，如果第i个点被钦定成不能选的了，就有F_i=0。

答案就是\sum{F_p}。单遍DP的复杂度是线性的，所以总复杂度O(n^2)。

存在至少一个点没有被选中时的EGF

随便选一个点rt做根。可以发现，此时最多只会有一个被“上下颠倒”了的子树。所以可以想到换根DP。

首先使用上一节的方法，求出以rt为根时的所有F_i。然后考虑i号点子树之内答案的EGF，把它记作G_i(x)。要不然是从每个子树选一个G组合起来，要不然就是单选一个F_i。所以转移是

G_i(x)=\frac{F_i}{siz_i!}x^{siz_i}+\prod_{j\textrm{是}i\textrm{的儿子}}G_j(x)

这里的卷积暴力实现即可。复杂度分析和树上背包是一模一样的，每一对点只会在它们的LCA处对复杂度产生贡献。所以是O(n^2)。

然后是换根的部分。我们通过一个DFS枚举每个点p，强制这个“上下颠倒”了的子树的根是p的父亲。此时不是p后代的点必须全部被选中。假设p子树之外的点全部选中时的方案数是Out_p，对整棵树EGF的贡献就是

\frac{Out_p}{(siz_{rt}-siz_p)!}x^{siz_{rt}-siz_p}(G_p(x)-\frac{F_p}{siz_p!}x^{siz_p})

从G_p(x)中扣除最后一项，是因为这里强制至少一个点不被选中了。容易发现每个点计算这个贡献的复杂度是O(n)的，所以总复杂度还是O(n^2)。

考虑Out_p从p转移到p的一个儿子i的过程，可以发现计算过程和F_p几乎是一模一样的：

Out_i=\frac{(siz_{rt}-siz_i+1)!}{(siz_{rt}-siz_p)!}Out_p\prod_{j\textrm{是}p\textrm{的儿子},j\ne i}\frac{F_j}{siz_j!}

这个暴力乘起来即可，复杂度是O(n^2)的。和F一样需要特判p点被钦定成不能选了的情况。

代码如下：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+9;
int n,m,_,dfn[2010],low[2010],tp,id[2010],cnt;
int siz[2010],Rt,vis[2010],sz[2010],sta[2010],ban[2010];
ll fac[2010],ifc[2010],f[2010],g[2010][2010],h[2010],ans[2010],_ans[2010],F[2010],o[2010];
basic_string<int> vv[2010],v[2010];
ll po(ll a,ll b=mod-2){ll r=1;for(;b;b/=2,a=a*a%mod)if(b&1)r=r*a%mod;return r;}
void tarjan(int p,int fa){
    dfn[p]=low[p]=++_;sta[++tp]=p;
    for(int i:vv[p])if(!dfn[i])
        tarjan(i,p),low[p]=min(low[p],low[i]);
    else if(i!=fa)low[p]=min(low[p],dfn[i]);
    if(low[p]==dfn[p]){
        ++cnt;int tot=0;
        while(tp){
            id[sta[tp]]=cnt;
            tot++;
            if(tot>1)ban[cnt]=1;
            if(sta[tp--]==p)break;
        }
    }
}
void dfs(int p,int fa=0){
    f[p]=siz[p]=1;vis[p]=1;
    for(int i:v[p])if(i!=fa){
        dfs(i,p);siz[p]+=siz[i];
        (f[p]*=f[i]*ifc[siz[i]]%mod)%=mod;
    }
    g[p][0]=1;int sz=1;
    for(int i:v[p])if(i!=fa){
        memset(h,0,sizeof h);
        for(int j=0;j<sz+siz[i];j++)
            for(int k=0;k<=siz[i] && k<=j;k++)
                (h[j]+=g[i][k]*g[p][j-k])%=mod;
        sz+=siz[i];
        for(int j=0;j<sz;j++)g[p][j]=h[j];
    }
    (f[p]*=fac[siz[p]-1])%=mod;
    if(ban[p])f[p]=0;
    g[p][siz[p]]=f[p]*ifc[siz[p]]%mod;
}
void dfs2(int p,int fa=0){
    F[p]=sz[p]=1;
    for(int i:v[p])if(i!=fa){
        dfs2(i,p);sz[p]+=sz[i];
        (F[p]*=F[i]*ifc[sz[i]]%mod)%=mod;
    }
    (F[p]*=fac[sz[p]-1])%=mod;
    if(ban[p])F[p]=0;
}
void dfs1(int p,int fa=0){
    ll op=o[p]*ifc[siz[Rt]-siz[p]]%mod;
    for(int i=0;i<siz[p];i++)
        (ans[i+siz[Rt]-siz[p]]+=g[p][i]*op)%=mod;
    dfs2(p);
    (ans[siz[Rt]]+=F[p]*ifc[siz[Rt]])%=mod;
    for(int i:v[p])if(i!=fa){
        o[i]=op;
        for(int j:v[p])if(j!=fa && i!=j)(o[i]*=f[j]*ifc[siz[j]]%mod)%=mod;
        (o[i]*=fac[siz[Rt]-siz[i]-1])%=mod;
        if(ban[p])o[i]=0;
        dfs1(i,p);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    ifc[0]=fac[0]=1;
    for(int i=1;i<=n;i++)ifc[i]=po(fac[i]=fac[i-1]*i%mod);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        vv[x]+=y,vv[y]+=x;
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tp=0,tarjan(i,0);
    for(int i=1;i<=n;i++)for(int j:vv[i])if(id[j]!=id[i] && !~v[id[j]].find(id[i]))
        v[id[j]]+=id[i],v[id[i]]+=id[j];
    _=1;_ans[0]=1;
    for(int i=1;i<=cnt;i++)if(!vis[i]){
        memset(ans,0,sizeof ans);
        dfs(i);Rt=i;o[Rt]=1;
        dfs1(Rt);
        memset(h,0,sizeof h);
        for(int i=0;i<_+siz[Rt];i++)
            for(int j=0;j<=siz[Rt] && j<=i;j++)
                (h[i]+=ans[j]*_ans[i-j])%=mod;
        _+=siz[Rt];
        memcpy(_ans,h,sizeof _ans);
    }
    for(int i=0;i<=n;i++)
        printf("%lld\n",(_ans[i]*fac[i]%mod+mod)%mod);
    return 0;
}