[Codeforces 814E] An unavoidable detour for home DP+BFS树+组合数学

题目链接 liu_cheng_ao大爷写的民间题解

注意：以下内容打大部分都是对liu_cheng_ao大爷题解的转述(但是可能复杂度并没有那么优秀),

因为博主太菜，并没有什么自己思考的能力(智力-=2)

题解：因为每条边的权值相等，所以考虑bfs的过程，

所以考察一张符合条件的图的bfs树的性质。

(根据题意，我们把capital设为bfs树的树根)

1. 显然，因为是bfs，

有边连接的两个点的深度差不超过1，

否则bfs中根到某个节点的距离就不是最短路了；

2. 有了1这个很强的性质后，因为根到每个节点的最短路唯一，

所以bfs树上，相邻节点之间只能有1条边，

根据1,2两点，我们可以发现，

在bfs树上，非树边只能存在于深度相同的节点之间。

又因为1到n这n个点到capital的距离递增，所以bfs树上，每一层的编号都是连续的一段。

这样，就可以进行递推转移dp了：

设f[i][j]表示考虑前i个位置，与第i个位置深度相同的点有j个，

与i位置深度相同的点只考虑连接到父亲的边，深度小于第i个位置的所有点度数均已经满足的方案数。

则可以通过枚举上一层的节点个数进行转移：

dp of dp：f[i][j]=sigma(f[i-j][k]*g[j][c1][c2]).

其中，c1是上一层的度数为2的节点数，c2是上一层的度数为3的节点数，

g[i][j][k]表示这一层有i个节点，上一层有j个度数为2的节点，k个度数为3的节点，

假设上一层中的节点都有连向父亲的边的情况下，使得上一层中(j+k)个点的度数均满足条件的方案数。

g数组中，所有(j+k)个点两两不同。

g数组的转移： i=j=k=0情况下，g[i][j][k]=1.

i=j=0,k>0情况下，g[i][j][k]=sigma(l=3..k,g[i][j][k-l]*C(k-1,l-1)*N(l))

解释：考虑标号最大的点所在的环，

因为每个点度数为2，形成若干个环，

枚举的l是标号最大的点所在的环的点数，

而N(l)是l个点形成的环的个数(点与点两两不同)，

N(l)=(l-1)!/2，即为项链数。

i=0,j>0情况下，g[i][j][k]=(j-1)*g[i][j-2][k]+k*g[i][j][k-1]，

解释：考虑标号最大的度数为1的点所连向的边，

此时，这个点可以向另一个度数为1的点进行连边，方案数为(j-1)*g[i][j-2][k].

这个点也可以向一个度数为2的点进行连边，方案数为k*g[i][j][k-1]，

因为这么做使得度数为1的点的个数不变，度数为2的点的个数+1.

i,j,k>0情况下，g[i][j][k]=j*g[i-1][j-1][k]+k*g[i-1][j+1][k-1].

解释：考虑标号最大的儿子所连向的边，

连向度数为2的点和连向度数为3的点分别讨论，

若连向度数为2的点，这个点在本层内就无法再连了，

若连向度数为3的点，这个点能连接到的边的条数从2变成了1，

所以转移显然。

O(n^3)预处理出g数组后即可O(n^3)求出f数组得到最终答案。

注意：f数组中每个点考虑时都认为其非根节点，所以根节点的情况提前处理一下，从第2层开始dp，

而对于叶子节点，统计答案时可以将其看做有0个儿子的非叶子节点进行转移。

(转移到dep[叶子节点]+1层时，叶子节点的度数限制就得到了满足)

Code:

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007ll
using namespace std;
/* g数组的计算: i!=0----->根据儿子连向的父亲计算,
                j!=0----->根据最后一个入度为2的点的连接方式计算
				k!=0----->根据最后一个点所在环的大小计算
				i=j=k=0----->g[i][j][k]=1.
   f数组的计算: f[d[1]+1][d[1]]=1
                f[i][j]=sigma(f[i-j][k]*g[j][c1][c2]).
   ans=sigma(f[n][i]*g[0][c1][c2]).
*/ 
ll c[51][51],p[51];
ll g[51][51][51];
ll f[51][51];
int a[51],n;
inline void get_c()
{int i,j;
for (i=0;i<=n;i++)
{c[i][0]=1ll;c[i][i]=1ll;
for (j=1;j<i;j++)
{c[i][j]=c[i-1][j]+c[i-1][j-1];
if (c[i][j]>=mod) {c[i][j]-=mod;}
}
}
p[3]=1;
for (i=4;i<=n;i++)
{p[i]=(p[i-1]*((ll)(i-1)))%mod;}
}
inline void get_g()
{int i,j,k;
for (j=0;j<=n;j++)
{for (k=0;k<=n;k++)
{if (j==0&k==0) 
{g[0][j][k]=1;continue;}
if (j>0)
{if (j-2>=0)
{g[0][j][k]+=((ll)(j-1))*g[0][j-2][k];
g[0][j][k]%=mod;
}
if (k-1>=0)
{g[0][j][k]+=((ll)(k))*g[0][j][k-1];
g[0][j][k]%=mod;
}
}
else
{for (i=3;i<=k;i++)
{g[0][j][k]+=((g[0][j][k-i]*c[k-1][i-1])%mod)*p[i];
g[0][j][k]%=mod;
}
}
}
}
for (i=1;i<=n;i++)
{for (j=0;j<=n;j++)
{for (k=0;k<=n;k++)
{if (j-1>=0)
{g[i][j][k]+=((ll)(j))*g[i-1][j-1][k];
g[i][j][k]%=mod;
}
if (k-1>=0)
{g[i][j][k]+=((ll)(k))*g[i-1][j+1][k-1];
g[i][j][k]%=mod;
}
}
}
}
}
inline void get_f()
{int i,j,k;
f[a[1]+1][a[1]]=1;
for (i=a[1]+2;i<=n;i++)
{for (j=1;j+a[1]+1<=i;j++)
{int c1=0,c2=0;
for (k=1;k+j<=i;k++)
{if (a[i-j-k+1]==2) {c1++;}
else {c2++;}
f[i][j]+=f[i-j][k]*g[j][c1][c2];
f[i][j]%=mod;
}
}
}
}
int main (){
	int i;
	scanf ("%d",&n);
	for (i=1;i<=n;i++)
	{scanf ("%d",&a[i]);}
	get_c();
	get_g();
	get_f();
	ll ans=0;
	int c1=0,c2=0;
	for (i=1;i<=n;i++)
	{if (a[n-i+1]==2) {c1++;}
	else {c2++;}
	ans+=f[n][i]*g[0][c1][c2];
	ans%=mod;
	}
	printf ("%lld\n",ans);
	return 0;
}