"蔚来杯"2022牛客暑期多校训练营3 ¶

排名	当场过题数	至今过题数	总题数
53/1519	5	10	10

B¶

upsolved by TYB

题意¶

需要把$n$个人派遣到$k$个城市，每个城市需要的人数是固定的。把不同的人派遣到不同城市，代价都是不同的，求最小代价。

$n\le10^5,k\le10$

题解¶

一眼费用流，但肯定过不去，那就模拟费用流。

考虑每次费用流的路径，形如$st\rightarrow a\rightarrow b\rightarrow ed$（字母表示城市），其实就是一个人去了$a$城市，一个原来在$a$城市的人到了$b$城市。所以表示$n$个人的点没有必要建出来，只需要保留$k$个表示城市的点和源汇点。然后用$k^2$个堆维护城市间的边，每次把最小的一条边拿出来跑SPFA即可。

复杂度$\mathcal{O}(nSPFA+nk^2\log)$，但两个都跑得不满，所以可以通过。

C¶

solved by JLK

题意¶

给$n$个0-4组成的数字串，任意排列，求最小的结果数字串。

$1 \le n \le 2\times 10^6,\sum |s_i| \le 2\times 10^7$

题解¶

可以使用基于比较的贪心法，$i$串在答案中在$j$前面的条件是$s_i+s_j \le s_j+s_i$。

据说用stable_sort就是$O(\sum |s_i| \log n)$的，不太懂。

考虑优化，其实可以在Trie上走，对于两个串$a,b$，如果他们没有前缀关系，那么直接比较字典序，即Trie上的dfs序即可。如果它们是前缀关系，可以利用exkmp来求lcp然后判断大小关系，需要一定分类讨论。这样直接sort是$O(n\log n+\sum |s_i|)$

还有一个去掉log的做法。按dfs序插入串，插入的时候实时维护一个当前的顺序链表。每次插入相当于要考虑和所有前缀的大小关系（大小关系即为前后关系）。

设排在$b$前面的集合是$A$，后面的集合是$B$。可以证明所有$B$中的元素在链表里是相邻的，且都排在末尾。即$B$的所有元素中间没有别的串。

证明：假设有一个别的串$x\notin B$，和$B_1\in B$，满足$B_1 \lt x$。如果$x$是$b$的前缀，那么$x\notin B$，则$x \in A$，$x \lt b$。如果$x$不是$b$的前缀，由于我们是按字典序插入，显然有$x \lt b$。那么$x \lt b$，而$B_i \gt b$，和$B_1 \lt x$矛盾。

所以只需要$O(|b|)$比较出和所有前缀的大小关系，就可以知道$B$集合的所有元素，找一个最前的插入即可。总复杂度为$O(n+\sum|s_i|)$。

D¶

upsolved by JLK

题意¶

$n$个点以$1$为根的树，一开始所有边都是双向，随机选$K$条边变成指向根的单向边。

给定起点$s$，随机游走，求到达$1$的期望步数。

$1\le n \le 10^6,0 \le K \le n-1$

题解¶

一个重要结论：从一个点出发随机游走，走到父亲的期望步数为$2\times siz-1$（$siz$为子树大小）。

所以在$K=0$的情况下，直接把$s$到根的路径上每条边的期望加起来即可。

对于$K \gt 0$，把一些边变成单向边，就是父亲无法到达它的儿子了。对子树内所有点没有影响，而对于子树外的边，可以看做是子树里的点减少了，相当于没有这个子树，期望也会减少。

考虑计算一条单向边$a$对双向边$b$的贡献，那么$b$和$a,b$之间的边都是双向的，只有$a$是单向的，其他边随意。单向边对期望的贡献是$-2\times siz$再乘上这种情况的概率，即$\frac{C_{n-1-d}^{K-1}}{C_{n-1}^K}$。（$d$为距离）

需要计算$s$到根路径上所有边被贡献的期望。发现上式概率只和距离有关，而每条边能够贡献的距离是一个区间，可以简单差分一下计算。也就是计算出每个距离的贡献之和，然后再根据距离来算概率，将答案减去期望。

$O(n)$

E¶

upsolved by JLK

题意¶

$n$个点等间距排成一个环，环上还有$m$个点连出去等长的弦，每个弦链接$a_i$和$a_i+L$。

现在要在环和弦上面放两根不相交的电线$1\rightarrow n,2\rightarrow n-1$，电线必须沿着编号从小到大的方向走，可以在任何交点转弯。求方案数。

$4 \le n \le 10^6,0 \le m \le 10^4,1 \le L \le \frac n2$

题解¶

观察一下这个图，实际上由于规定了顺序，转移是一个DAG。

很明显可以应用LGV引理，设$f(i,j)$表示$i\rightarrow j$的方案，则答案转化为$f(1,n)\times f(2,n-1)-f(1,n-1)\times f(2,n)$。

考虑怎么求出$f$。在DAG上，我们转移的时候实际上只关心拓扑序。这个图上的转移就是一个点转移到当前弦的下一个交点。

有一个性质，固定一个弦，另一个弦移动，那么相交的点和另一个弦的起始位置正相关。也就是说，另一个弦起始位置越大，它们的交点的拓扑序就越后面。

因此如果我们按照编号从小到大枚举弦来转移，那么前面的弦实际上只有目前的最后一个交点有用（dp只会转移到相邻交点）。

$dp_i$记录从起点到达从$i$点开始的弦的最后一个交点的方案数。

首先是每个点的起始方案，要么从环上直接转移，要么从$i-L$的弦转移过来。

然后考虑相交，从小到大枚举相交的所有弦来转移，这样枚举的时候实际上已经保证了转移的拓扑序。如果当前枚举到$j$，那么目前$i$和$j$的最后一个交点都可以转移到$i,j$的交点，也就是同时更新$dp_i,dp_j$为$dp_i+dp_j$。

从$1$和$2$分别开始做一遍dp即可得到答案。注意直接连$1\rightarrow n$的劣弧也是合法的，因为也是按编号从小到大的方向。

$O(n+m^2)$

F¶

solved by JLK

题意¶

$n$个点$m$条边的无向图，$q$次询问，每次询问对于$x,y$，是否存在一个$x$到$y$的包含$n$个点的路径（排列），使得任意前缀联通、任意后缀联通。

$2 \le n \le 10^5,0 \le m \le 2\times 10^5,1 \le q \le 10^5$

题解¶

结论是：按点双缩点（类似圆方树）之后，只有一个点双，或者点双构成一条链而且询问两点在两端且不是割点才是YES。

对于证明，首先考虑每个割点，必须度数为2且询问的两个点必须在其两侧。否则一定会出现一个点占据割点，另一个点占据割点另外一侧的点，而到达另一侧必须经过割点，所以这种情况是NO。

那么就是要对每个割点都满足这个条件，割点只能构成一条链。也就是点双构成一条链。

跑一遍Tarjan然后判断一下即可。

$O(n+m+q)$

G¶

upsolved by YZW

题意¶

板题。

题解¶

求凸包的 Minkowsky 和。

H¶

solved by TYB

题意¶

签到。

题解¶

略。

I¶

upsolved by Serval

题意¶

Given is two integers $n, k$. Calculate the expected value of $x^k$ modulo $862118861$, where $x$ is the number of fixed points of a random $n$-element permutation.

$1\leq n\leq 10^{18}$, $0\leq k\leq n + 5\times 10^3$

题解¶

Let the random variable $x$ be the number of fixed points of a random $n$-element permutation. By the definition, the expectation of $x^k$ is $$ E(x^k) = {1\over n!} \sum_{i=0}^n {n\choose i} i^k\,!(n-i) = \sum_{i=0}^n {i^k\over i!(n-i)!}\,!(n-i) $$ where $!n$ is the $n$-th derangement number, which is equal to $$ !n = n!\sum_{i=0}^n {(-1)^i\over i!} = n! [z^n] {e^{-z}\over 1-z} $$ Recall that the Stirling number of the second kind ${n\brace k}$ is the number of ways to partition a set of $n$ elements into $k$ non-empty subsets. Using the Stirling numbers of the second kind to expand $i^k$ gives $$ \begin{aligned} E(x^k) &= \sum_{i=0}^n {1\over i!} \sum_{c=0}^{k} {k\brace c} i^{\underline{c}} [z^{n-i}] {e^{-z}\over 1-z} \\ &= \sum_{c=0}^k {k\brace c} \sum_{i=0}^n {1\over (i-c)!} [z^{n-i}] {e^{-z}\over 1-z} \\ &= \sum_{c=0}^k {k\brace c} \sum_{i=0}^n [z^i] (z^c e^z) [z^{n-i}] {e^{-z}\over 1-z} \\ &= \sum_{c=0}^k {k\brace c} [z^n] {z^c\over 1-z} \\ &= \sum_{c=0}^k {k\brace c} [c\leq n] \\ &= \sum_{c=0}^n {k\brace c} \end{aligned} $$ Recall that the Bell number $B_n$ is the number of all the possible partitions of a set of $n$ elements. When enumerating the number of subsets as $k$, it is obvious that $$ B_n = \sum_{k=0}^n {n\brace k} $$ We only need to concentrate on speeding up the calculation of $$ E(x^k) = B_k - \sum_{i=n+1}^k {k\brace i} $$ Using the following identity called Touchard's congruence $$ B_{n+p} \equiv B_n + B_{n + 1} \pmod p $$ held for any prime $p$, $B_k$ can be calculated in $\mathcal{O}(p^2\log k)$ time by calculating $x^k \bmod (x^p-x-1)$.

For ${n\brace n-x}$ part, considering that ${n\brace n-x}$ is the number of ways to partition $n$ elements into $n-x$ non-empty subsets, obviously there are no less than $n-2x$ subsets with exactly one element. Since $x\leq 5\times 10^3$, it is possible to pre-calculate the number of ways to partition $i$ elements into $j$ subsets with no less than $2$ elements, denoted by $f_{i,j}$, for all $i\leq 10^4$ and $j\leq i/2$. For the $i$-th element, it can either be partitioned into a new subset with another element, or be inserted into an existed subset. Thus, $f_{i,j}$ obey the recurrence relation $$ f_{i,j} = (i-1) f_{i-2,j-1} + j f_{i-1,j} $$ with initial conditions $f_{0,0}=1$ and $f_{i,0}=0$ for all $i > 0$. Summing up the number of partitions that contains $k$ subsets with no less than $2$ elements over all possible $k$ gives $$ {n\brace n-x} = \sum_{k=0}^x {n\choose x+k} f_{x+k,k} $$ The formula above allows us to calculate a single ${n\brace n-x}$ using Lucas's theorem in $\mathcal{O}(x\log p)$ time with pre-calculation in $\mathcal{O}(x^2)$ time. In this way, the problem can be solved in total $\mathcal{O}(p^2\log k + (k-n)^2\log p)$ time.

This approach of calculating ${n\brace n-x}$ seems to be more straightforward than using the Eulerian numbers of the second order. Great thanks to Toxel!

J¶

solved by JLK

题意¶

签到，略

题解¶

BFS即可。

记录¶

🐍感冒摸了，基本是两个人在打。

JLK过A(0:12)。看到一车人过C，但是没什么想法。

TYB开始写H，JLK看其他题。

TYB过H(1:12)。

JLK写J，WA一次后AC(1:29)。

然后一起讨论F，JLK猜了个结论开始写，但没考虑清楚，WA两次后AC(3:06)。

TYB写C的二分哈希做法，发现很慢。JLK尝试卡常，交了一发TLE。

一起看D，没什么想法，TYB推了个式子但假了。

JLK交了一发C的暴力，居然过了(4:41)。

继续写D，最后还是没搞出来。

总结¶

JLK：点双和边双区别还是比较大的，可以看两个三元环交于一点的情况。

TYB：SAM感觉还不太熟练，多加练习；如果一个题过了一车但你不会，考虑一下直接交个暴力。

Dirt¶

C(-1)

F(-2)：结论错了，应该看点双不是边双。还有一次是加了个corner case直接交了。

J(-1)：转向判断有问题。

"蔚来杯"2022牛客暑期多校训练营3¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

"蔚来杯"2022牛客暑期多校训练营3 ¶