题解 CF512D 【Fox And Travelling】
cosmicAC
2020-06-05 15:49:42
这道题$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$点被钦定成不能选了的情况。
----
代码如下：
```cpp
#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;
}
```