当前位置：首页 > news >正文

20251117~20251123NOIP模拟赛

news 2026/6/16 11:04:03

20251117NOIP模拟赛

A：

题目大意：

有 \(n\) 个点，每个点有 \(a_{i}\) 个孔，你现在要在这 \(n\) 个点中连 \(n - 1\) 条边，使得他们联通。
每条边连接两个孔，每个孔最多连接 \(1\) 条边，两种连接方案相同，当且仅当每条边连接的两个空不同。
问不同的方案数，模数给定。
\(n \le 10^6, a_{i} \le 10^9\)

解题思路：

看到生成树计数，往 prufer 序列上想。
但这个题对于第 \(i\) 个点来说，如果它的度数为 \(d_{i}\)，那么内部的方案有 \(\frac{a_{i}!}{(a_{i} - d_{i})!}\)。
那么对于一个度数为 \(d_{i}\) 的节点 \(i\)，它在 prufer 序列中出现了 \(d_{i} - 1\) 次，对于 prufer 的方案数相当于 \(\binom{n - 2}{d_{1} - 1,d_{2}-1 \dots d_{n} - 1}\)
那么我们现在就有了式子：

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} \frac{a_{i}!}{(a_{i} - d_{i})!} \binom{n - 2}{d_{1} - 1,d_{2}-1 \dots d_{n} - 1} \]

先将后面的组合数拆开：

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} \frac{a_{i}!}{(a_{i} - d_{i})! \times (d_{i} - 1)!} \times (n - 2)! \]

然后我们发现中间的数和标准的组合数有 \(O(1)\) 的偏差，所以考虑变一下，变成一个组合数。

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} a_{i} \frac{(a_{i} - 1)!}{(a_{i} - d_{i})! \times (d_{i} - 1)!} \times (n - 2)! \]

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} a_{i} \binom{a_{i} - 1}{d_{i} - 1} \times (n - 2)! \]

因为我们知道了 \(d_{i} - 1\) 之和为 \(n - 2\)，然后我们后面的式子还是连乘的形式，所以考虑范德蒙德卷积的扩展形式。

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} a_{i} \binom{\sum_{i = 1}^{n} a_{i} - n}{n - 2} \times (n - 2)! \]

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} a_{i} \frac{(\sum_{i = 1}^{n} a_{i} - n)!}{(n - 2)! \times (\sum_{i = 1}^{n} a_{i} - n - n + 2)!} \times (n - 2)! \]

\[\sum_{\sum_{d_{i} - 1} = n - 2,d_{i} > 0} \prod_{i = 1}^{n} a_{i} \frac{(\sum_{i = 1}^{n} a_{i} - n)!}{(\sum_{i = 1}^{n} a_{i} - n - n + 2)!} \]

那么这个式子就能 \(O(n)\) 算了。

没想到的点：

不熟悉 prufer 序列，不知道 prufer 的原理，对生成树计数不敏感。
不熟悉范德蒙德卷积，稍微扩展一下就不会了，看到和固定，求组合数乘积也要敏感。

T3:

题目大意：

有两天，第一天有 \(n\) 个人，第 \(i\) 个人在 \(s_{i}\) 时刻进入同一个房间，在 \(t_{i}\) 时刻离开，如果两个人在同时在房间里，那么他们会互相加对方的好友。
第二天每个人会把自己的明信片挂到网站上，每个人可以看到/转发好友自己发的/转发的明信片，问每两个人都看到对方的明信片最小的转发次数。
\(n \le 2 \times 10^5\)

解题思路：

这种题，它并不特别关心标号，所以我们可以先排序，所以我们先按 \(l\) 从小到大排序。
由于注意到人与人之间的明信片互不影响，所以将每个人单独考虑，即让其他人都看到这个人明信片的最小转发次数。

而对于第 \(i\) 个人来说，\(1 \sim i - 1\) 不会被 \(i + 1 \sim n\) 影响，所以我们可以直接设 \(f_{i}\) 表示前 \(i\) 个，由 \(i\) 转发，最少需要多少个转发。
转移就是枚举上一个转发得位置，BIT 优化。
那么设 \(g_{i}\) 表示 \(i\) 转发，让 \(i \sim n\) 都收到最少多少转发。
同理，也是 BIT。