丁真258

发布于 2024-08-30 22:16 山东

+ 关注

牛客挑战赛 76 官方题解

A.

不难发现，当且仅当数组中只由一个数组成时，才满足题目要求。所以输出 $m\bmod p$ 即可。

B.

对于一个长度大于 $1$ 的子串 $T$ ，设 $T$ 出现的位置是 $[l,r]$ ，如果存在一个不连续的子序列等于 $T$ ，那么以下两条有至少一条成立：

存在 $i<l$ 使得 $S_i=S_l$ ；
存在 $i>r$ 使得 $S_i=S_r$ 。

并且我们发现这个条件也排除了 $T$ 作为子串出现多次的情况，所以只需要找到所有字母第一次出现位置的集合 $A$ ，以及所有字母最后一次出现位置的集合 $B$ ，答案就是 $|A|+\sum_{x\in A}\sum_{y\in B} [x<y]$ 。

C.

把 $0$ 看作左括号， $1$ 看作右括号，如果 $s$ 不是合法括号序列，答案就一定是 $0$ 。

把括号树建出来，每一次操作会删掉一个叶子以及它的父亲，如果它的父亲有多于一个儿子，答案也是 $0$ 。

所以我们可以每次把一个叶子和它的父亲合并起来，然后在新树上建一个点，表示同时删掉这个叶子和它的父亲。在这棵新树上，能做的操作就是每次删去一个叶子。所以问题变成了树的拓扑序计数，根据经典结论，答案是 $n!\left(\prod_{u=1}^n \mathrm{size}_u\right)^{-1}$ 。

D.

首先，如果预先将 $a$ 数组排序，那么操作后 $a$ 仍然是有序的。

考虑用数据结构维护 $a$ 中奇偶性相同的连续段。对于一次操作，先在数据结构上求出需要操作的下标区间 $[L,R]$ ，然后枚举 $[L,R]$ 中的所有连续段，进行操作。因为操作后 $[L,R]$ 会变成一个连续段，所以均摊时间复杂度是对的。

维护连续段可以用 std::map，维护 $a$ 数组可以用线段树。时间复杂度 $O(n+q\log n)$ 。std 直接在线段树上做连续段均摊，会好写一些。

E.

我们给 $d(u,v)$ 赋予一个组合意义：从 $u,v$ 间路径上选择一条边的方案数。

所以可以直接做树上 DP，设 $f_{u,i,j}$ 表示：考虑 $u$ 子树内的所有点，总共有 $i+j$ 个点还没有配对，其中 $i$ 个点没有选择边， $j$ 个点选择了边，的方案数。

对于 $u$ 的一个儿子 $v$ ，考虑如何合并 $f_u$ 和 $f_v$ ：枚举 $k_1,k_2$ 表示：总共新增了 $k_1+k_2$ 对点，其中 $k_1$ 对选择的边在 $u$ 这边， $k_2$ 对选择的边在 $v$ 这边。

根据树上背包的时间复杂度分析，这样做的时间复杂度是 $O(n^6)$ 。

F.

考虑这个限制：

对任意 $(x,y)\in T$ ，存在 $(x',y')\in T$ ，满足 $|x-x'|=1$ 或 $|y-y'|=1$ 。

对它容斥，钦定有 $i$ 个位置 $(x,y)\in T$ 满足：

不存在 $(x',y')\in T$ 使得 $x'=x-1$ 或 $x'=x+1$ ；
不存在 $(x',y')\in T$ 使得 $y'=y-1$ 或 $y'=y+1$ 。

注意到容斥后两维是独立的，我们可以对两维分别算出钦定 $i$ 个位置不合法的方案数，然后乘上一些系数将它们组合起来。

设 $f(n,k,i)$ 表示在长为 $n$ 的序列中选择 $k$ 个位置，且钦定其中 $i$ 个被选择的位置 $x$ 满足 $x-1$ 和 $x+1$ 都没被选择的方案数，那么答案为：

$\sum_{i=0}^k (-1)^i\cdot f(n,k,i)\cdot f(m,k,i)\cdot (k-i)!\cdot i!,$

其中两个阶乘的意义是，那些钦定不合法的 $i$ 个位置可以任意配对，剩下 $(k-i)$ 个位置可以任意配对。

于是只需要考虑如何快速对于每个 $0\le i\le k$ ，算出 $f(n,k,i)$ 。注意到固定所有钦定不合法的位置以后，假如有 $s$ 个空位满足与它相邻的位置都没被钦定，那么这样一种方案对 $f(n,k,i)$ 的贡献是 $\binom{s}{k-i}$ 。

于是转而对于每对 $i,s$ ，计算有多少种钦定的方式。设 $i$ 个变量 $x_1,x_2,\dots,x_i$ ，其中 $x_j$ 表示从小到大第 $j$ 个被钦定的位置到上一个被钦定位置的距离，如果 $j=1$ 则表示它到开头的距离。有：

$x_1\ge 1$ ；
$x_2,x_3,\dots,x_i\ge 2$ ；
$\sum_{j=1}^i x_j\le n$ ；
空位个数为 $\max(0,x_1-2)+\sum_{j=2}^i \max(0,x_j-3)+\max(0,n-\sum_{j=1}^i x_j-1)$ 。

添加变量 $x_{i+1}$ ，做一些转化：

$x_1,x_2,\dots,x_{i+1}\ge 2$ ；
$\sum_{j=1}^{i+1} x_j=n+3$ ；
空位个数为 $\sum_{j=1}^{i+1} \max(0,x_j-3)=n-3i+\sum_{j=1}^{i+1} [x_j=2]$ 。

固定 $j$ 个 $x_i=2$ ，设 $x=n-3i+j$ ，则有 $x$ 个空位的方案数是：

$\binom{i+1}{j} \binom{x+i-j}{x}.$

为了方便，设 $g(n,k,i)=f(n,k+i,i)$ 。则

$\begin{aligned} g(n,k,i) &=\sum_{j} \binom{n-3i+j}{k} \binom{i+1}{j} \binom{n-2i}{n-3i+j}\\ &=\binom{n-2i}{k} \sum_{j} \binom{i+1}{j} \binom{n-2i-k}{n-3i+j-k}\\ &=\binom{n-2i}{k}\binom{n-i+1-k}{i}. \end{aligned}$

于是我们可以 $O(1)$ 计算一个 $f(n,k,i)$ ，原式可以在 $O(k)$ 时间复杂度内计算。总时间复杂度 $O(n+m+\sum k_i)$ 。

G.

考虑每个质数 $p\in [1,n]$ ，只需要算出来有多少个 $i\in [k,n]$ 使得 $p\mid \binom{i}{k}$ ，设这个数是 $c_p$ ，答案就是

$\left(\prod_{i=k}^n \binom{i}{k}\right)\cdot \prod_{p\in \mathrm{Prime}} \left(1-\frac{1}{p}\right)^{c_p}.$

前面的组合数之积是好算的，所以只需要快速算出所有 $c_p$ 即可。

先考虑一个 $c_p$ 怎么算。根据 Kummer 定理， $p$ 在 $\binom{i}{k}$ 中的幂次，就是在 $p$ 进制下把 $i-k$ 和 $k$ 加起来的过程中，产生进位的次数。所以我们不妨算 $p\nmid\binom{i}{k}$ 的情况，也就是，在 $p$ 进制下 $i-k$ 和 $k$ 的每一位加起来都要小于 $p$ 。

记 $B=\max(\sqrt{n},k)$ 。对于 $p\le B$ 的情况，这样的 $i$ 的数量可以用数位 DP 算。这部分的时间复杂度是 $O\left(\sum_{p\in \mathrm{Prime},p\le B}\log_p n\right)=O(B)$ 。

对于 $p>B$ 的情况， $i-k$ 在 $p$ 进制下至多只有两位，而 $k$ 在 $p$ 进制下只有一位。不妨将 $i-k$ 代换成 $j$ ，我们要算有多少个 $j\in [0,n-k]$ 满足 $(j\bmod p)+k<p$ 。这样的 $j$ 的个数显然是两部分加起来：

$(p-k)\lfloor\frac{n-k}{p}\rfloor$ ；
$\min((n-k)\bmod p+1,p-k)$ 。

第一部分是好算的，直接整除分块即可；考虑第二部分中，什么时候 $(n-k)\bmod p\ge p-k$ 。推一下发现是 $n\ge p(1+\lfloor\frac{n-k}{p}\rfloor)$ ，设 $a=\lfloor\frac{n-k}{p}\rfloor$ ，也就（大约）是 $\frac{n-k}{a}\le p\le \frac{n}{1+a}$ ，也就是说，这种特殊的 $p$ 的取值范围的大小只有 $O(\frac{k}{a})$ ，对所有 $a$ 求和，总的大小只有 $O(k\log k)$ 。对于这些 $p$ 暴力算，剩下的 $p$ 仍然能整除分块。