传送门

直接DP,设$f_{i,j_1,j_2,k_1,k_2}$表示“当前处理了包含在$\{1,\cdots,i\}$内的边,有$j_1$个点满足$l_x=l_i-1$且有一条边连向后面的点,有$j_2$个点满足$l_x=l_i-1$且有两条边连向后面的点,有$k_1$个点满足$l_x=l_i$且有一条边连向后面的点,有$k_2$个点满足$l_x=l_i$且有两条边连向后面的点”的方案数。枚举第$i+1$个点的连边情况即可,情况比较复杂。注意$d_1$可能为3,要把$l_x=1$的点单独拿出来处理一下。

#include <bits/stdc++.h>
#define MAXN 52
#define LL long long

const LL P=1000000007;

int n;
int d[MAXN];
LL f[2][MAXN][MAXN][MAXN][MAXN];
LL g2[MAXN];

inline void update(LL &x,LL y){ x=(x+y)%P; }

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",d+i);
    for(int i=1;i<=n;i++) g2[i]=i*(i-1)/2;
    if(d[2]==2) f[0][0][0][1][0]=1;
    else f[0][0][0][0][1]=1;
    for(int i=3;i<=n;i++){
        int now=i&1,last=(i&1)^1;
        for(int t1=0;t1<=i;t1++)
            for(int t2=0;t1+t2<=i;t2++)
                for(int t3=0;t1+t2+t3<=i;t3++)
                    for(int t4=0;t1+t2+t3+t4<=i;t4++)
                        f[now][t1][t2][t3][t4]=0;
        if(i<=d[1]+1){
            for(int t1=0;t1<i;t1++)
                for(int t2=0;t1+t2<i;t2++)
                    for(int t3=0;t1+t2+t3<i;t3++)
                        for(int t4=0;t1+t2+t3+t4<i;t4++)
                            if(f[last][t1][t2][t3][t4]){
                                LL lastv=f[last][t1][t2][t3][t4];
                                if(d[i]==2){
                                    update(f[now][t1][t2][t3+1][t4],lastv);
                                    if(t3) update(f[now][t1][t2][t3-1][t4],lastv*t3);
                                    if(t4) update(f[now][t1][t2][t3+1][t4-1],lastv*t4);
                                }else{
                                    update(f[now][t1][t2][t3][t4+1],lastv);
                                    update(f[now][t1][t2][t3][t4],lastv*t3);
                                    if(t4) update(f[now][t1][t2][t3+2][t4-1],lastv*t4);
                                    if(t3>=2) update(f[now][t1][t2][t3-2][t4],lastv*g2[t3]);
                                    if(t4>=2) update(f[now][t1][t2][t3+2][t4-2],lastv*g2[t4]);
                                    if(t3&&t4) update(f[now][t1][t2][t3][t4-1],lastv*t3*t4);
                                }
                            }
        }else{
            for(int t1=0;t1<i;t1++)
                for(int t2=0;t1+t2<i;t2++)
                    for(int t3=0;t1+t2+t3<i;t3++)
                        for(int t4=0;t1+t2+t3+t4<i;t4++)
                            if(f[last][t1][t2][t3][t4]){
                                LL lastv=f[last][t1][t2][t3][t4];
                                if(d[i]==2){
                                    if(t1){
                                        update(f[now][t1-1][t2][t3+1][t4],lastv*t1);
                                        if(t3) update(f[now][t1-1][t2][t3-1][t4],lastv*t3*t1);
                                        if(t4) update(f[now][t1-1][t2][t3+1][t4-1],lastv*t4*t1);
                                    }
                                    if(t2){
                                        update(f[now][t1+1][t2-1][t3+1][t4],lastv*t2);
                                        if(t3) update(f[now][t1+1][t2-1][t3-1][t4],lastv*t3*t2);
                                        if(t4) update(f[now][t1+1][t2-1][t3+1][t4-1],lastv*t4*t2);
                                    }
                                    if(!t1 && !t2){
                                        if(t3) update(f[now][t3-1][t4][1][0],lastv*t3);
                                        if(t4) update(f[now][t3+1][t4-1][1][0],lastv*t4);
                                    }
                                }else{
                                    if(t1){
                                        update(f[now][t1-1][t2][t3][t4+1],lastv*t1);
                                        update(f[now][t1-1][t2][t3][t4],lastv*t3*t1);
                                        if(t4) update(f[now][t1-1][t2][t3+2][t4-1],lastv*t4*t1);
                                        if(t3>=2) update(f[now][t1-1][t2][t3-2][t4],lastv*g2[t3]*t1);
                                        if(t4>=2) update(f[now][t1-1][t2][t3+2][t4-2],lastv*g2[t4]*t1);
                                        if(t3&&t4) update(f[now][t1-1][t2][t3][t4-1],lastv*t3*t4*t1);
                                    }
                                    if(t2){
                                        update(f[now][t1+1][t2-1][t3][t4+1],lastv*t2);
                                        update(f[now][t1+1][t2-1][t3][t4],lastv*t3*t2);
                                        if(t4) update(f[now][t1+1][t2-1][t3+2][t4-1],lastv*t4*t2);
                                        if(t3>=2) update(f[now][t1+1][t2-1][t3-2][t4],lastv*g2[t3]*t2);
                                        if(t4>=2) update(f[now][t1+1][t2-1][t3+2][t4-2],lastv*g2[t4]*t2);
                                        if(t3&&t4) update(f[now][t1+1][t2-1][t3][t4-1],lastv*t3*t4*t2);
                                    }
                                    if(!t1 && !t2){
                                        if(t3) update(f[now][t3-1][t4][0][1],lastv*t3);
                                        if(t4) update(f[now][t3+1][t4-1][0][1],lastv*t4);
                                    }
                                }
                            }
        }
    }
    printf("%lld\n",f[n&1][0][0][0][0]);
}