[自选题 #107] An unavoidable detour for home
2017-12-22 15:582017-12-22 15:58
直接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]);
}