AGC005 做题小记

比赛链接:AGC005

(刷新以获取数学公式)

C. Tree Restoring

题意

给出树上每个节点到其它节点的最远距离，问是否可能。

$n ≤ 100$。

题解

离一个点最远的节点是直径两端点之一。

先把直径上的点切出来。剩余的点判断一下是不是在 $\lceil \frac{d}{2} \rceil +1$和 $d + 1$之间即可。

My Submission

D. ~K Perm Counting

题意

计数$n$个数全排列个数，使得$abs(a_i - i) ≠ K$

$2 ≤ N ≤ 2000， 1 ≤ K ≤ N − 1$。

题解

不妨先考虑 $K = 1$ 怎么做。

记恰有 $i$ 个位置不合法的方案数为 $f_i$, $g_i$为有不少于$i$个位置不合法，但是恰有 $j$ 个位置不合法的情况会被算 $\dbinom{j}{i}$ 次的方案数。

于是有 $g_i = \sum_{j = i}^{n} \dbinom{j}{i} f_j$

二项式反演得 $f_i = \sum_{j = i}^{n} (-1)^{j - i} g_j$

我们要计算的就是 $f_1$

考虑 $g$ 如何计算。 $g_i$ 实际上是钦定 $i$ 个位置不合法，其余位置随便放的方案数。

$dp_{i, j, a, b}$ 表示前 $i$ 个数， 已经钦点了 $j$ 个位置不合法， $i$ 和 $i + 1$ 有没有被用于钦定。

转移有三种情况:不钦定；钦定$i+1$的位置放$i+2$；钦定$i+1$的位置放$i$。注意如果是不钦定，我们不用理会$i+1$这个位置放了什么数。因为如果我们最终钦定了$j$个数，我们认为剩下$n-j$个数可以随意放置。

于是我们得到 $g_i = (n - i)! dp_{n, j, 0/1, 0}$

当 $K ≠ 1$的时候，我们对序列做一点处理：把所有模 $K$ 相同的数放在一起。除了有些位置放$i+1$是合法的，其余的情况和$K=1$相同。

My Submission

E. Sugigma: The Showdown

题意

给定 $n$ 个节点， $n-1$条红边和$n-1$条蓝边。红边和蓝边分别组成一棵树。A从点X出发，只能走红边；B从点Y出发，只能走蓝边。两人轮流走，可以不走，当两人走到同一点时游戏结束。A先走且要最大化游戏步数；B后走且要最小化游戏步数。输出游戏结束时进行的步数。如果不会结束输出-$1$。

$2 ≤ N ≤ 200000$。

题解

这题的关键在于：游戏是否结束取决于A是否能走到一条红边$(u, v)$的端点，且$u, v$在蓝树上的距离不小于$3$。

如果能走到，A可以在这两条边来回走，B永远抓不到它。

如果不能走到，能使用的红边连接蓝树上距离不超过$2$的点。A无法离开B所在的子树。这时A会跑到一个能跑到且离Y最远的点等死。

My Submission

F. Many Easy Problems

题意

给定 $n$ 个点的树，对于每个$k$，对于每种选择$k$点的方案，求出包含这$k$个点最小导出连通子图点数之和。

$2 ≤ N ≤ 200000$。

题解

考虑每个点对$ans_k$的贡献。

不妨设根为$u$，选出$k$个点后，点$u$在子图中，当且仅当$k$个点的LCA为$u$。

如果$u$孩子的子树大小分别为$size_1, size_2, .. size_m$，那么$u$对$ans_k$的贡献是$\dbinom{n}{k} - \sum_{i=1}^{m}\dbinom{size_i}{k}$

记以$1, 2, .. , n$为根时，$size = i$的子树个数和为$cnt_i$，那么

$$ans_k = n\dbinom{n}{k} - \sum_{i = 1}^{n} cnt_i\dbinom{i}{k}\\ =n\dbinom{n}{k}-\frac{1}{k!}\sum_{i = 1}^{n}cnt_i*i!*\frac{1}{(i-k)!}$$

这样就可以NTT优化了。

My Submission