lyoj 211 「雅礼集训 2017 Day8」共

##题目描述
俗话说，跳蚤国王下江南，火车司机出秦川，共价大爷游长沙。
但是这道题可能跟上面几句话没什么关系。 共价爷想构造一棵 $N$ 个点的有根树，其中 $1$ 号点是根。
显然的，对于一棵有根树，我们可以定义每个点的深度为，这个点到根的路径上点的个数（包括端点），也就是说， $1$ 号点深度为 $1$ 。
共价爷希望，深度为奇数的点的个数，刚好为 $K$  个。
他想知道有多少棵不同的满足条件的有根树，你只需要输出答案对  $P$ 取模的结果。

我们认为两棵树不同，当且仅当存在一对点 $(i, j)$ ，满足 $i$ 和 $j$ 在一棵树中有边相连，而在另一棵树中没有边相连。
##输入格式
一行三个整数，依次为 $N$ 、 $K$ 、 $P$。
##输出格式
一个正整数，表示答案。
##样例
###样例输入
4 2 998244353
###样例输出
12
##数据范围与提示
对于 $5\%$ 的数据，是样例；
对于 $20\%$ 的数据， $N \leq 20$；
对于 $40\%$ 的数据， $N \leq 100$；
对于 $70\%$ 的数据， $N \leq 1000$， $P$ 为 $1000000007$ 或 $998244353$ 且均匀分布；
对于 $90\%$ 的数据， $N \leq 50000$；
对于 $100\%$ 的数据， $1 < K < N$， $N \leq 500000$ ，当 $N > 1000$ 时， $P$ 均为 $998244353$ 。

---
 
##题解

$$ ans = {{n-1}\choose{k-1}} * {n-k}^{k-1} * k^{n-k-1}  $$

$1$号点标号必须为1，${{n-1}\choose{k-1}}$为给其他$k-1$个奇数深度的点的标号分配方案。

然后考虑有$k$个奇数点，$n-k$个偶数点，树上的边只能在两者之间，所以合法的生成树的方案数为这两块间互相连$k*(n-k)$条边的图的生成树个数。

于是考虑使用矩阵树定理，但是这题复杂度要求比较高，只能手（da）动（biao）消（zhao）矩（gui）阵（lv）了。

手动消除这个有规律的矩阵是一个相当愉♂悦的过程

矩阵大概长这样
(斜着的$n-k$有$k-1$行)
(斜着的$k$有$n-k$行)

$$\begin{bmatrix}
n-k &0&0&0 &-1&-1 & -1 \\
0 & n-k &0&0&-1&-1 & -1 \\
0 & 0&n-k&0&-1&-1 & -1 \\
0& 0 & 0&n-k&-1&-1 & -1 \\
-1&-1&-1&-1&k&0&0\\
-1&-1&-1&-1&0&k&0\\
-1&-1&-1&-1&0&0&k\\
\end{bmatrix}$$

使用最后一行消除第$k$到第$n-2$行左边的$-1$

变成

$$\begin{bmatrix}
n-k &0&0&0 &-1&-1 & -1 \\
0 & n-k &0&0&-1&-1 & -1 \\
0 & 0&n-k&0&-1&-1 & -1 \\
0& 0 & 0&n-k&-1&-1 & -1 \\
0&0&0&0&k&0&-k\\
0&0&0&0&0&k&-k\\
-1&-1&-1&-1&0&0&k\\
\end{bmatrix}$$

然后手动把行列式算出来就好了

能不能用prufer序列更快的推导呢？

wuvin

导航

最近发表

友情链接