子
树
问
题
子树问题
子树问题
正
解
部
分
\color{red}{正解部分}
正解部分
设
F
[
i
,
j
]
F[i, j]
F[i,j] 表示
i
i
i 个节点, 深度不超过
j
j
j 的构成树的方案数, 枚举根节点编号 次大 子树大小转移,
F
[
i
,
j
]
=
∑
k
=
1
i
F
[
k
,
j
−
1
]
×
F
[
i
−
k
,
j
]
×
(
i
−
2
k
−
1
)
F[i, j] = \sum\limits_{k=1}^{i} F[k, j-1] \times F[i-k, j] \times \begin{pmatrix} i-2 \\ k-1 \end{pmatrix}
F[i,j]=k=1∑iF[k,j−1]×F[i−k,j]×(i−2k−1)
实
现
部
分
\color{red}{实现部分}
实现部分
#include<bits/stdc++.h>
#define reg register
int read(){
char c
;
int s
= 0, flag
= 1;
while((c
=getchar()) && !isdigit(c
))
if(c
== '-'){ flag
= -1, c
= getchar(); break ; }
while(isdigit(c
)) s
= s
*10 + c
-'0', c
= getchar();
return s
* flag
;
}
const int maxn
= 505;
const int mod
= 998244353;
int N
;
int K
;
int C
[maxn
][maxn
];
int F
[maxn
][maxn
];
bool vis
[maxn
];
int main(){
freopen("a.in", "r", stdin);
N
= read(), K
= read();
C
[0][0] = 1;
for(reg
int i
= 1; i
<= N
; i
++){
C
[i
][0] = 1;
for(reg
int j
= 1; j
<= i
; j
++) C
[i
][j
] = (C
[i
-1][j
-1] + C
[i
-1][j
]) % mod
;
}
for(reg
int i
= 1; i
<= K
; i
++) vis
[read()] = 1;
for(reg
int i
= 1; i
<= N
; i
++) F
[1][i
] = 1;
if(!vis
[N
])
for(reg
int i
= 2; i
<= N
; i
++)
for(reg
int j
= 1; j
<= N
; j
++)
for(reg
int k
= 1; k
<= i
; k
++){
if(vis
[k
]) continue ;
int add
= 1ll*F
[k
][j
-1]*F
[i
-k
][j
]%mod
*C
[i
-2][k
-1]%mod
;
F
[i
][j
] = (F
[i
][j
] + add
) % mod
;
}
int L
= read(), R
= read();
for(reg
int i
= L
; i
<= R
; i
++) printf("%d\n", (F
[N
][i
] - F
[N
][i
-1] + mod
) % mod
);
return 0;
}
