CF_#418(Div. 2)_E

我们按到点1的最短路径长度分层,因为满足$l_{i} \leq l_{i + 1}$,那么每一层的数一定是连续的。因为最短路径唯一,所以除1外的每个点都有且仅有一条边指向上一层,其它边要么指向同一层其它点,要么指向下一层。
然后我们可以构造$DP$状态$f[i][j][k][l]$表示处理到第$i$个点,上一层有$j$条边尚未连接,这一层有$k$个点还有1条边位连接和有$l$个点还有2条边未连接。转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//created by missever
#include<bits/stdc++.h>
#define MAX 1000000007
using namespace std;
typedef long long LL;
const int inv2 = 500000004;
int f[55][55][55][55];
int d[55],inv[55];
void add(int &x,int y) {
x += y;
if(x >= MAX) x -= MAX;
}
int mul(int x,int y) {
LL z = 1LL * x * y;
return z - z / MAX * MAX;
}
int main() {
int n,i,j,k,l;
scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d",&d[i]);
inv[0] = 1;
for(i = 1; i <= n; i++) inv[i] = mul(inv[i - 1],inv2);
if(d[1] == 2) f[2][d[1]][0][0] = inv2;
else f[2][d[1]][0][0] = mul(333333336,inv2);
for(i = 2; i <= n; i++) {
for(j = 0; j < i; j++) {
for(k = 0; k + j < i; k++) {
if(f[i][0][j][k]) add(f[i][j + k * 2][0][0],mul(f[i][0][j][k],inv[k]));
}
}
for(j = 1; j <= n - i + 1; j++) {
for(k = 0; k < i; k++) {
for(l = 0; l + k < i; l++) {
if(f[i][j][k][l]) {
int x = mul(f[i][j][k][l],j);
if(d[i] == 2) {
add(f[i + 1][j - 1][k + 1][l],x);
if(k) add(f[i + 1][j - 1][k - 1][l],mul(x,k));
if(l) add(f[i + 1][j - 1][k + 1][l - 1],mul(x,l));
} else {
add(f[i + 1][j - 1][k][l + 1],x);
add(f[i + 1][j - 1][k][l],mul(x,k));
if(l) add(f[i + 1][j - 1][k + 2][l - 1],mul(x,l));
if(k >= 2) add(f[i + 1][j - 1][k - 2][l],mul(mul(x,inv2),mul(k,k - 1)));
if(l >= 2) add(f[i + 1][j - 1][k + 2][l - 2],mul(mul(x,inv2),mul(l,l - 1)));
if(k && l) add(f[i + 1][j - 1][k][l - 1],mul(x,mul(k,l)));
}
}
}
}
}
}
printf("%d\n",f[n + 1][0][0][0]);
return 0;
}