相关链接
题目传送门:http://codeforces.com/contest/814/problem/E
官方题解:http://codeforces.com/blog/entry/52449
神犇题解Ⅰ:https://loj.ac/article/37
神犇题解Ⅱ:http://kczno1.blog.uoj.ac/blog/2660
解题报告
我们考虑分层图的话
那每一层的一个点一定会与上一层的某个点相连,剩下的度数只能层内消化
又因为这题对祖先有严格的限制,所以每一层都是原序列中连续的一段
于是$O(n^5)$的暴力$DP$就可以写了
至于$O(n^3)$的$DP$,就是$DP$套$DP$
预处理出转移的$buf$,然后转移的时候直接乘就好了
但这个预处理的时候要讨论很多情况啊,反正我自己考场上是想不出来的_(:з」∠)_
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 52; const int MOD = 1000000007; const int REV2 = 500000004; int n, f[N][N], s2[N], s3[N], buf[N][N][N], C[N][N], prm[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int main() { n = read(); f[read() + 1][1] = 1; for (int i = 2; i <= n; i++) { s2[i] = s2[i - 1]; s3[i] = s3[i - 1]; if (read() == 2) { s2[i]++; } else { s3[i]++; } } C[0][0] = 1; for (int i = 1; i <= n; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } } prm[2] = 1; for (int i = 3; i <= n; i++) { prm[i] = REV2; for (int j = 2; j < i; j++) { prm[i] = (LL)prm[i] * j % MOD; } } for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k <= n; k++) { if (i == 0 && j == 0 && k == 0) { buf[i][j][k] = 1; } else if (i == 0 && j == 0) { for (int l = 2; l < k; l++) { (buf[i][j][k] += ((LL)buf[i][j][k - 1 - l] * C[k - 1][l] % MOD) * prm[l + 1] % MOD) %= MOD; } } else if (i == 0) { buf[i][j][k] = j > 1? (LL)(j - 1) * buf[i][j - 2][k] % MOD: 0; (buf[i][j][k] += k? (LL)k * buf[i][j][k - 1] % MOD: 0) %= MOD; } else { buf[i][j][k] = j? (LL)j * buf[i - 1][j - 1][k] % MOD: 0; (buf[i][j][k] += k? (LL)k * buf[i - 1][j + 1][k - 1] % MOD: 0) % MOD; } } } } for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (f[i][j]) { int t2 = s2[i] - s2[j]; int t3 = s3[i] - s3[j]; for (int k = i + 1; k <= n; k++) { f[k][i] = (f[k][i] + (LL)f[i][j] * buf[k - i][t2][t3]) % MOD; } } } } int ans = 0; for (int i = 1; i <= n; i++) { ans = (ans + (LL)f[n][i] * buf[0][s2[n] - s2[i]][s3[n] - s3[i]]) % MOD; } cout<<ans<<endl; return 0; }