归乡迷途
有一张 (n) 个节点组成的无向图，点从 (1) 至 (n) 编号，图中没有重边和自环。我们不知道它的确切形态，但是它满足以下条件：
-
由任一节点至节点 (1) 的最短路径（经过边数最少的路径）存在且唯一；
-
令 (ell_i) 表示由节点 (i) 至节点 (1) 的最短路径上边的数目，那么对于所有 (2 leq i leq n)，有 (ell_i geq ell_{i-1}) 成立；
-
节点 (i) 的度数给定，为 (d_i)，并且所有 (d_i) 均等于 (2) 或 (3)。
请计算满足条件的不同的图的数目，输出其除以 (10^9 + 7) 的余数。两张无向图不同当且仅当存在点对 ((u, v) (1 leq u < v leq n)) 使得其中一张图中 ((u, v)) 间有边而另一张图中没有。
(3 leq n leq 300,2 leq d_i leq 3)
题解
https://jklover.hs-blog.cf/2020/07/18/Loj-6094-归乡迷途/#more
bfs 树 + dp 计数问题.
限制可以简单归纳为,图的 bfs 树中,每个点的父亲编号小于自己,且非树边只在同一深度的点间出现.
对 bfs 树进行 dp, 每一层加入的数都一定是编号连续的一段,并且只需要记录上一层的信息就可以转移.
设 (f(i,j)) 表示考虑了前 (i) 个点,最深的一层有 (j) 个点,前 (i-j) 个点度数已经满足限制,最后 (j) 个点只考虑向父亲连边.
设 (g(i,j,k)) 表示上一层有 (j) 个点度数要求为 (2) , (k) 个点度数要求为 (3) ,这层有 (i) 个点时的拼接以及上一层内部连边.
枚举上一层有 (k) 个点,有 (f(i,j)=sum_{kle i-j}f(i-j,k)cdot g(j,c_2,c_3)) , (c_2,c_3) 表示 (k) 个点中要求度数为 (2,3) 的点,由于它们都各自向父亲连了一条边,实际上还需要连的边数是 (1,2) .
考虑如何计算转移系数 (g(i,j,k)) .
-
当 (i>0) 时,考虑该层第一个点的父亲是哪个点,有
[g(i,j,k)=jcdot g(i-1,j-1,k)+kcdot g(i-1,j+1,k-1) ] -
当 (i=0) 时,此时需要在上一层内互相连边,使得它们满足度数限制,此时再分 (j>0) 和 (j=0) 讨论.
-
当 (i=0,j>0) 时,枚举第一个还要连 (1) 条边的点连的哪个点,有
[g(0,j,k)=(j-1)cdot g(0,j-2,k)+kcdot g(0,j,k-1) ] -
当 (i=j=0) 时, (k) 个点都要连 (2) 条边,一定是若干个互不相交的,大小 (>2) 的环,这里犯不着 (exp) ,暴力预处理即可.
-
最后答案就是 (sum f(n,i)cdot g(0,c_2,c_3)) ,时间复杂度 (O(n^3)) .
注意根节点没有向父亲连的边,儿子方向上的度数不会 (-1) ,需要特判一下,即先将前两层的 (f) 单独算出来.
CO int N=310;
int d[N],fac[N],ifac[N];
int dp[N],g[N][N][N],f[N][N];
IN int C(int n,int m){
return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main(){
int n=read<int>();
for(int i=1;i<=n;++i) read(d[i]);
fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
ifac[n]=fpow(fac[n],mod-2);
for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
dp[0]=1;
for(int i=3;i<=n;++i)for(int j=3;j<=i;++j)
inc(dp[i],mul(dp[i-j],mul(C(i-1,j-1),mul(fac[j-1],i2))));
for(int i=0;i<=n;++i)
for(int j=0;i+j<=n;++j)for(int k=0;i+j+k<=n;++k){
if(i==0){
if(j==0) g[i][j][k]=dp[k];
else{
if(j>=2) inc(g[i][j][k],mul(j-1,g[i][j-2][k]));
if(k>=1) inc(g[i][j][k],mul(k,g[i][j][k-1]));
}
}
else{
if(j>=1) inc(g[i][j][k],mul(j,g[i-1][j-1][k]));
if(k>=1) inc(g[i][j][k],mul(k,g[i-1][j+1][k-1]));
}
}
f[1+d[1]][d[1]]=1;
for(int i=d[1]+2;i<=n;++i)for(int j=1;j<=i-(1+d[1]);++j){
int c2=0,c3=0;
for(int k=1;j+k<=i-1;++k){
d[i-j-k+1]==2?++c2:++c3;
inc(f[i][j],mul(f[i-j][k],g[j][c2][c3]));
}
}
int ans=0,c2=0,c3=0;
for(int i=1;i<=n-1;++i){
d[n-i+1]==2?++c2:++c3;
inc(ans,mul(f[n][i],g[0][c2][c3]));
}
printf("%d
",ans);
return 0;
}