不错的 DP 题目。
首先容易发现，满足条件的序列一定是 单调 或者 单峰或单谷 的。并且我们都能够通过 两种不同操作 使其合法。
进一步地我们发现，假如所有编号大的点向编号小的点连边，确定了根之后。根的若干棵子树，边只会是外向或内向。而对于必胜状态的树，有 $n(n-1)$ 中方案可以选，设可行的树的方案为 $ans$，那么最后答案为 $2n(n-1)ans$。外向树和内向树方案数显然是一样的，哦我们下面不妨以内向树进行考虑。
于是考虑 DP，设 $f(i,j)$ 表示有考虑有 $i$ 个点组成的子树，根节点度数为 $j$。因为子节点之间是无序的，所以直接钦定当前最新的为次小，系数为 $\binom{i-2}{k-1}$。那么转移比较显然：
再考虑合并答案，即将 一棵内向树 和 一棵外向树拼接起来，不过他们公用一个根节点。并且注意到，若两棵树根的入度为 $1$，不同的树拼接起来，中间可能会产生一条链，这些链上的点都可以作为根节点，且只能算一种情况。但是注意到必然会存在度数大于 $1$ 的点，我们直接在这些点作为根节点的时候统计答案就可以了。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=200+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,d,mod;
ll C[N][N],f[N][N],sum[N];
inline void init(int n)
{
for(int i=0;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;
}
}
int main()
{
read(n,d,mod);
if(n==1)return puts("1"),0;
init(n);
f[0][0]=f[1][0]=1;
sum[0]=sum[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=min(i-1,d);j++)
for(int k=1;k<i;k++)
f[i][j]=(f[i][j]+1ll*C[i-2][k-1]*f[i-k][j-1]%mod*sum[k])%mod;
for(int j=1;j<=d-1;j++)sum[i]=(sum[i]+f[i][j])%mod;
}
ll ans=0;
for(int i=0;i<n;i++)
for(int d1=0;d1<=d;d1++)
for(int d2=0;d1+d2<=d;d2++)
{
if(d2==1)continue;
ans=(ans+f[i+1][d1]*f[n-i][d2])%mod;
}
ans=2ll*n*(n-1)%mod*ans%mod;
printf("%lld\n",ans);
return 0;
}
|