原题：CF914H 答案乘 $2n(n+1)$ 即可。
我们考虑题目要求的限制相当于是每一条路径必须是单峰或者单调的。
于是对于一个合法的树我们一定可以找到一个点，使得这个点到所有点的路径一定是单调的。考虑如果不存在这个点，那么对于一个单调的路径的一个峰的位置，它不能作为这个点，所以它向下有个路径的编号是单峰的。画下图，无非这两种
明显这两种都不满足题意。。
考虑对于当前的根，如果它只有一个儿子是递增的，其他都是递减的，那么明显可以把根往这个方向移，这个根仍然合法。如果有两个儿子都是递增的，
明显不能向任何一个儿子移动根了。。移动一次就有一边是单峰函数，而不是单调了。
所以我们知道合法的根一定在一个链上。
于是考虑点减边容斥，考虑对于一个点算以它作为根（这里指这个根走向所有儿子的路径都是单调的）能得到的树的个数及一个边的两边作为根能够得到的树的个数。
现在我们只需要考虑对于一个根，求出以这个点为根，子树大小为 $i$ ，根的度数是 $j$ 的方案数量了。这个可以 dp 来做。我们枚举一个新子树加入，强行钦定这个子树的根是第二大（或者第二小）。
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
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 5006
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define int unsigned
typedef long long ll;
int n , d , P , op;
int A[MAXN];
int C[MAXN][MAXN] , dp[MAXN][MAXN] , S[MAXN];
void solve() {
cin >> n >> d >> P >> op;
if( op == 0 ) {
if( ( d == 1 && n > 2 ) || P == 1 ) puts("0");
else puts("1");
return;
}
C[0][0] = 1;
rep( i , 1 , n ) {
C[i][0] = 1;
rep( j , 1 , i ) C[i][j] = ( C[i - 1][j] + C[i - 1][j - 1] ) % P;
}
dp[1][0] = 1; S[1] = 1;
rep( i , 2 , n ) {
rep( k , 1 , i - 1 ) {
rep( j , 1 , i ) {
dp[i][j] = ( dp[i][j] + dp[i - k][j - 1] * 1ll * S[k] % P * C[i - 2][k - 1] ) % P;
}
}
rep( j , 0 , d - 1 ) S[i] = ( S[i] + dp[i][j] ) % P;
}
int as = 0;
rep( i , 1 , n ) rep( j , 0 , d ) rep( k , 0 , d ) if( j + k <= d ) as = ( as + dp[i][j] * 1ll * dp[n - i + 1][k] ) % P;
rep( i , 1 , n ) rep( j , 0 , d - 1 ) rep( k , 0 , d - 1 ) as = ( as + P - dp[i][j] * 1ll * dp[n - i][k] % P ) % P;
cout << as << endl;
}
signed main() {
solve();
}
|
