An unavoidable detour for home
首先明确的一点是从前往后dp， 因为有dis[ i + 1 ] >= dis[ i ] 这个条件存在。
然后我先就考虑将顶点一个一个填进去， 但是发现需要开六七个50乘起来的数组才能维护。
我发现有一个条件还没有利用起来， 就是每个点到 1 的最短路唯一， 我们考虑将到 1 距离一样的点
一起考虑去更新dp。
dp[ o ][ i ][ j ] 表示处理到完了o， 还有 i 个顶点需要 1 的度数， 还有 j 个顶点需要 2 的度数。
对于dp[ o ][ i ][ j ] 需要i + 2 * j 个当前这个段连接才能转移。
way1[ i ][ j ] 表示有 i 个顶点需要 1 的度数， 有 j 个顶点需要 2 的度数， 填满这样的段的方案数。
way2[ l ][ r ][ i ][ j ] 表示考虑l - r作为一个整体的一段， 每个都向之前一段连条边，
段内相互连边之后有 i 个顶点需要 1 的度数， 有 j 个顶点需要 2 的度数的方案数。
然后就可以转移啦。 有点恶心就是了。
#include<bits/stdc++.h> #define LL long long #define LD long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ALL(x) (x).begin(), (x).end() #define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = 51; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;} template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;} template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;} template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} int n, d[N]; int way1[N][N]; int way2[N][N][N][N]; int dp[N][N][N]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &d[i]); for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { int ret = 1, tot = i + 2 * j, num1 = i, num2 = j; while(num2--) ret = 1LL * tot * (tot - 1) / 2 * ret % mod, tot -= 2; while(num1--) ret = 1LL * ret * tot % mod, tot--; way1[i][j] = ret; } } for(int l = 1; l <= n; l++) { for(int r = l; r <= n; r++) { int len = r - l + 1; for(int i = l; i <= r; i++) { for(int j = 0; j <= len; j++) { for(int k = 0; j + k <= len; k++) { dp[i][j][k] = 0; } } } if(d[l] == 2) dp[l][1][0] = 1; else dp[l][0][1] = 1; for(int o = l; o < r; o++) { for(int i = 0; i <= len; i++) { for(int j = 0; i + j <= len; j++) { if(!dp[o][i][j]) continue; if(d[o + 1] == 2) { add(dp[o + 1][i + 1][j], dp[o][i][j]); if(i) add(dp[o + 1][i - 1][j], 1LL * dp[o][i][j] * i % mod); if(j) add(dp[o + 1][i + 1][j - 1], 1LL * dp[o][i][j] * j % mod); } else { add(dp[o + 1][i][j + 1], dp[o][i][j]); if(i) add(dp[o + 1][i][j], 1LL * dp[o][i][j] * i % mod); if(j) add(dp[o + 1][i + 2][j - 1], 1LL * dp[o][i][j] * j % mod); if(i >= 2) add(dp[o + 1][i - 2][j], 1LL * dp[o][i][j] * (i * (i - 1) / 2) % mod); if(j >= 2) add(dp[o + 1][i + 2][j - 2], 1LL * dp[o][i][j] * (j * (j - 1) / 2) % mod); if(i && j) add(dp[o + 1][i][j - 1], 1LL * dp[o][i][j] * (i * j) % mod); } } } } for(int i = 0; i <= len; i++) { for(int j = 0; i + j <= len; j++) { way2[l][r][i][j] = dp[r][i][j]; } } } } memset(dp, 0, sizeof(dp)); if(d[1] == 2) { for(int i = 0; i <= 2; i++) { for(int j = 0; i + j <= 2; j++) { add(dp[3][i][j], way2[2][3][i][j]); } } } else { for(int i = 0; i <= 3; i++) { for(int j = 0; i + j <= 3; j++) { add(dp[4][i][j], way2[2][4][i][j]); } } } for(int o = 3; o < n; o++) { for(int i = 0; i <= o; i++) { for(int j = 0; i + j <= o; j++) { if(!dp[o][i][j]) continue; if(!i && !j) continue; int len = i + 2 * j, l = o + 1, r = o + len; if(o > n) continue; for(int u = 0; u <= len; u++) { for(int v = 0; u + v <= len; v++) { add(dp[r][u][v], 1LL * way2[l][r][u][v] * way1[i][j] % mod * dp[o][i][j] % mod); } } } } } printf("%d ", dp[n][0][0]); return 0; } /* */