题目链接 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; }
