【题解】CF814E An unavoidable detour for home
题意：
给出 $n$ 个点，和每个点的度数 $d_i$，要求计数无向图满足：
- $1$ 到 $i$ 的最短路有且仅有一条。
- 设 $l_i$ 是 $1$ 到 $i$ 的最短路，则 $\forall i\in[1,n),l_i\le l_{i+1}$。
$3\le n\le 50,2\le d_i\le 3$。
首先由于 $l_i\le l_{i+1}$，容易意识到，对于 $l$ 相同的节点，他们的编号一定构成一个区间。容易发现，第 $2$ 层的节点编号一定是 $[2,d_1+1]$。
当我们划分了区间之后，第 $i$ 层可以向第 $i+1$ 层连边，第 $i$ 层内部可以连边，其他的边都是不合法的了。
现在考虑第 $i$ 层的连边情况，设从第 $i-1$ 层连下来了 $m$ 条边，这说明第 $i$ 层恰好有 $m$ 个节点。设其中 $2$ 度点有 $x$ 个，$3$ 度点有 $y$ 个，他们分别和上层连一条边，所以实际上是 $1$ 度点 $x$ 个，$2$ 度点 $y$ 个。
设该层内部有 $z$ 条边，那么给下层引出的边有 $x+2y-2z$ 条，他们可以任意排列，共 $(x+2y-2z)!$ 种方案。
再考虑层内部的 $z$ 条边，把 $2$ 度点看做两个点，则选出 $z$ 个不相交无序二元组的方案数是：
$$ \dfrac{(x+2y)!}{(x+2y-2z)!\times 2^z\times z!} $$
即首先选出 $2z$ 个数，相邻两两一对。除去每一对内部的顺序，除去 $z$ 个对之间的顺序。
但由于将 $2$ 度点看做了两个点，所以可能出现重边、自环的情况。考虑容斥，钦定出现了 $p$ 条重边，$q$ 个自环，那么从 $y$ 个 $2$ 度点中选出他们的方案数是：
$$ \dfrac{y!\times 2^p}{(y-2p-q)!\times p!\times q!\times 2^p} $$
即：
$$ \dfrac{y!}{(y-2p-q)!\times p!\times q!} $$
上面要乘一个 $2^p$ 是因为一组重边有两种连接方式，比如 $(1,2),(1',2')$ 和 $(1,2'),(1',2)$。由于在容斥，所以前面还有一个 $(-1)^{p+q}$ 的容斥系数。
设 $s=2p+q$，则已经选出了 $s$ 条边，$2s$ 个点。那么剩下的 $x+2y-2s$ 个点中，还需要选出 $z-s$ 条边，方案就是：
$$ \dfrac{(x+2y-2s)!}{(x+2y-2z)!\times 2^{z-s}\times (z-s)!} $$
因此在 $x$ 个 $1$ 度点，$y$ 个 $2$ 度点中，内部连 $z$ 条边，同时往下一层引出 $x+2y-2z$ 条边的贡献就是：
$$ \sum_{s=2p+q,s\le\min(y,z)} \frac{(-1)^{p+q}y!}{(y-s)! p! q!}\times \dfrac{(x+2y-2s)!}{(x+2y-2z)!2^{z-s} (z-s)!}\times (x+2y-2z)!\times \frac{1}{2^y} $$
最后一个要乘 $\dfrac{1}{2^y}$ 是因为 $y$ 个 $2$ 度点被认为是两个点，需要取消顺序。
设：
$$ v_s=\sum_{2p+q=s} \dfrac{(-1)^{p+q}}{p!\times q!} $$
那么上式可以化简为：
$$ \sum_{0\le s\le \min(y,z)} \dfrac{y!(x+2y-2s)!v_s}{(y-s)!2^y}\times \dfrac{1}{(z-s)!2^{z-s}} $$
于是就可以设 $\text{dp}_{i,j}$ 表示已经考虑了前 $i$ 个点，最后一层向下一层引出了 $j$ 条边，那么新的一层的节点就是 $i+1,i+2\cdots i+j$，设其中有 $x$ 个 $2$ 度点，$y$ 个 $3$ 度点。
那么可以通过枚举 $z$，再枚举 $s$，从 $\text{dp}_{i,j}$ 转移到 $\text{dp}_{i+j,x+2y-2z}$。这样就是 $\mathcal{O}(n^4)$ 的了。
考虑分部进行转移，我们发现 $z=s+(z-s)$，令 $d=z-s$，则可以先枚举 $s$，再枚举一次 $d$：
$$ \text{dp}_{i,j}\stackrel{s}{\longrightarrow} g_{i+j,x+2y-2s}\stackrel{d=z-s}{\longrightarrow} \text{dp}_{i+j,x+2y-2z} $$
于是就可以做到时间复杂度 $\mathcal{O}(n^3)$，空间复杂度 $\mathcal{O}(n^2)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 110;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, iv2 = (mod + 1) >> 1;
int d[MAXN], v[MAXN], dp[MAXN][MAXN], g[MAXN][MAXN];
int ip2[MAXN], fac[MAXN], ifac[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
int qpow(int x, int b) {
int res = 1;
for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
return res;
}
void init() {
fac[0] = ifac[0] = ip2[0] = 1;
for(int i = 1; i < MAXN; ++i) {
fac[i] = fac[i - 1] * i % mod;
ip2[i] = ip2[i - 1] * iv2 % mod;
}
ifac[MAXN - 1] = inv(fac[MAXN - 1]);
for(int i = MAXN - 2; i; --i) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n); init();
for(int i = 1; i <= n; ++i) read(d[i]);
for(int s = 0; s <= n; ++s)
for(int p = 0, q; (p << 1) <= s; ++p) {
q = s - (p << 1);
(v[s] += ifac[p] * ifac[q] % mod * (((p + q) & 1) ? mod - 1 : 1)) %= mod;
}
dp[1][d[1]] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= (i << 1); ++j) {
if(!g[i][j]) continue;
for(int d = 0; (d << 1) <= j; ++d)
(dp[i][j - (d << 1)] += g[i][j] * ip2[d] % mod * ifac[d]) %= mod;
}
for(int j = 1, x, y; j <= n - i; ++j) {
if(!dp[i][j]) continue;
x = 0, y = 0;
for(int k = i + 1; k <= i + j; ++k) d[k] == 2 ? x++ : y++;
for(int s = 0, coe; s <= y; ++s) {
coe = fac[y] * fac[x + (y << 1) - (s << 1)] % mod * v[s] % mod * ifac[y - s] % mod * ip2[y] % mod;
(g[i + j][x + (y << 1) - (s << 1)] += dp[i][j] * coe) %= mod;
}
}
}
printf("%lld\n", dp[n][0]);
return 0;
}