AGC005

A

模拟。

B

从小到大枚举。

C \((\texttt{Easy} \ 2 / 0)\)

考虑找出最大的 \(a_i\) 作为直径，然后在上面挂点。

设 \(m = \max a_i\)，我们由此可以得出有解的充要条件：

• 能找出 \(m + 1\) 个点构成直径。
• 剩下的点 \(i\) 需要满足 \(a_i > \left\lceil\frac{m}{2}\right\rceil\)。

时间复杂度 \(\mathcal{O}(n)\)。

D \((\texttt{Easy} \ 3 / 0)\)

刚开始想到一个雷哥 \(n\) 元生成函数做法，但是到后面发现其实根本不用，容斥一下就可以了。

具体地，设 \(g_i\) 表示钦定 \(i\) 个位置满足 \(|p_i - i| = k\) 的方案数，那么答案可以用 \(\sum_i (-1) ^ i g_i\) 表示。

考虑 \(g_i\) 怎么求。发现如果钦定 \(|p_i - i| = k\) 的话，模 \(2k\) 不同余的数之间是不会影响的。考虑所有模 \(2k\) 同余的数，它们的选择等价于在一条链上选若干对不重复的相邻的点，而在一条 \(n\) 个点的链上选 \(m\) 对不重复的相邻的点的方案数为 \(\binom{n - m}{m}\)，所以可以直接背包合并。

暴力是 \(\mathcal{O}(n^2)\) 的，使用多项式科技可以优化至 \(\mathcal{O}(n \log n)\)。

E \((\texttt{Medium} \ 4 / 1)\)

一个显然的事实是，如果先手能走到一条红边，其两个端点在蓝树中的距离不小于 \(3\)，并且后手下一步抓不到他，那么游戏就不可能结束了。

将后手起点 \(y\) 设为蓝树的根，那么如果不存在上述情况，因为先手走一步是在蓝树上走至多 \(2\) 步，所以先手会一直在蓝树上后手的子树内。

再次观察，可以注意到一个引理：

引理：设 \(dr_u\) 为红树中 \(\text{dist}(x, u)\)、\(db_u\) 为蓝树中 \(\text{dist}(y, u)\)，则 \(2dr_u\) 时刻游戏未结束且先手在 \(u\) 节点是可能的当且仅当对于红树中 \(x \to u\) 路径上的任意点 \(v\) 都有 \(dr_v < db_v\)。

这下就简单了，我们可以方便地判断一个点是否是安全可达的。如果存在两端点在蓝树中距离 \(\ge 3\) 的红边端点是可达的，那么答案就是 \(-1\)。否则枚举在哪里死的，对于所有的可达点 \(u\)，把 \(2db_u\) 取 \(\max\) 即可得到答案。

时间复杂度 \(\mathcal{O}(n)\)。

F \((\texttt{Easy} \ 3 / 2)\)

史上最水的 F 题。

容斥。首先把点的贡献转化为边的贡献，一条边不在包含一个点集的最小连通块内等价于这个点集中所有点都在这条边的一侧。假设一条边把树分为了大小为 \(m\) 和 \(n - m\) 的两部分，那么它没有产生贡献的大小为 \(i\) 的点集就有 \(\binom{m}{i} + \binom{n - m}{i}\) 个。

所以这个问题就变成了给定 \(a_1, \cdots, a_n\)，对于 \(i = 1, 2, \cdots, n\) 求 \(f_i = \sum_j a_j \binom{j}{i} = \sum_j \frac{a_jj!}{i!(j - i)!}\)，差值卷积即可。

本题的模数虽然是 \(\rm NTT\) 模数，但是其原根为 \(5\)。