牛客挑战赛 88 官方题解

A Solution

by Anemones

题意要求对于所有相同的 $A_i$ 都要使得它下面的 $B_i$ 全部相同，我们发现若一些相同的 $A_i$ 对应的 $B_i$ 有不同，则只能保留一个 $B_i$ ，我们肯定要保留那个出现最多的 $B_i$ ，而剩下的 $B_j$ 对应的 $A_j$ 显然需要改变，由于可以改成 $1\sim n$ 的任意数，我们给它单独变成一个独立的种类（也就是从未出现过的数）就行。

B Solution

by Safari_Mo

去掉相同的行。

如果一行的 $0$ 把另外一行全部包含，则删除这一行。

找出剩下的行的 $0$ 的个数的最大值即可。

正确性证明：

令 $f_i = \min_{j=1}^m \max(a_{i,j},s_j)$ 。

设第 $i$ 行把第 $j$ 行完全包含，如果 $f(i) = 1$ 则 $f(j) = 1$ 。

这时不可能翻转一位使得 $f(i) = 0$ ， $f(j) = 1$ 。

此时根据 $n = 1$ 的结论（答案为 $0$ 的个数）不难得出答案的上界，也可以取到上界, 复杂度 $O(n^2m)$ 或 $O(\dfrac{n^2m}{w})$ .

C Solution

by I_like_magic

题面大致意思：序列 $a$ 是单调不降的，并且要求对任意的 $i$ ，进行至少两次 $i\gets a_i$ 操作后得到 $i'$ ，满足 $a_{i'} = a_i$ 。

很显然，如果 $a_{a_i} \neq a_i$ ，那么，当 $i \gets a_i$ 时，得到的新的 $a_i$ 一定不等于原先的 $a_i$ ，而当 $a_i$ 变小或变大时，由于 $a$ 的单调性， $i\gets a_i$ 操作只会让 $a_i$ 更加远离原先的 $a_i$ （或不变），永远不会等于原先的 $a_i$ 。

但是，如果 $a_{a_i} = a_i$ ，那么无论经过多少次 $i\gets a_i$ ，新的 $a_i$ 都会等于原先的 $a_i$ 。

所以，我们只需要统计 $a$ 满足单调性，同时 $a_{a_i} = a_i$ 的序列个数就行了。

我们考虑到，如果 $a_x = y$ ，那么 $a_y = y$ ，由于单调性， $x$ 到 $y$ 的 $a_i$ 值都会等于 $y$ 。

所以，满足条件的序列 $a$ ，一定可以被划分为若干个区间，且每个区间 $[l, r]$ 的 $a_i$ 相等，且 $a_i\in[l, r]$ 。

然后就可以开始递推了。

我们先不考虑题目给的几条限制。

记 $f_i$ 表示序列长度为 $i$ 的答案数。

先假定 $f_0 = 1$ 。

接下来是计算每个 $f_i$ 。

对于一个长度为 $i$ 的序列，我们可以假设最末端的 $k$ 个 $a_i$ 都被划分到了一个区间，而这个区间的 $a_i$ 有 $k$ 种取值，所以这种情况答案数为 $f_{i - k} \times k$ 。

所以得到 $f_i = \sum\limits_{k = 1}^{i}f_{i - k}\times k$ 。

记 $s_i = \sum\limits_{k = 1} ^ if_i$ ，那么 $f_i = \sum\limits_{k = 1}^{i - 1}s_i$ 。

显然是可以每一步 $O(1)$ 处理好 $\sum\limits_{k = 1}^{i - 1}s_i$ ，从而实现 $O(n)$ 的总复杂度的。

现在我们加入了若干条限制。

我们可以发现，限制相当于是告诉我们，对于任意的 $i \in [\min\{x, y\}, \max\{x, y\}]$ ，将 $a_i$ 直接确定为 $y$ 。

读入限制时，判断一下有没有冲突，有冲突直接输出 $0$ 。

然后，修改一下递推。

先正常递推，然后遇到了已经被确定的区间 $[l, r]$ ，直接跳到区间结尾 $r$ ，考虑 $f_r$ 如何计算。这个确定的区间可以和前面没确定的连上，并且连上的部分的值已经确定，所以方案数就是连上若干个，加上剩下部分的方案数，即为 $\sum\limits_{k = 0}^{l - 1}f_k$ ，注意如果前面存在已经被确定的区间 $[l', r']$ ，那么方案数应是 $\sum\limits_{k = r'}^{l - 1}f_k$ 。

考虑计算完 $f_r$ ，后面怎么推，显然， $f_i$ 的贡献有两种情况，第一种，从 $r$ 到 $i$ 一整个区间都连上了，答案显然是 $f_r$ ，另一种情况是 $a_r\neq a_i$ ，这个贡献就是 $\sum\limits_{k = r}^{i - 1}f_k\times(i - k)$ ，与前面无限制的情况同理，处理方法相同。

所以，这一部分的 $f_i = f_r + \sum\limits_{k = r}^{i - 1}f_k\times(i - k)$ 。

D Solution

by cjh20090318

令 $n=\vert S \vert, m = \vert T \vert$ 。

通常地，我们将概率转化为合法方案数除以总方案数。

每个字符只有选或不选两种情况，所以总方案数即为 $2^{k(r-l+1)}$ 。

对于每一个特定字符 $x$ ，对其构造一个 $(m+1) \times (m+1)$ 矩阵（矩阵从 $0$ 开始，字符串从 $1$ 开始）：

$A_{x,i,j} = \begin{cases} 1 & T_j=x \land i \in [p_j,j]\\ 0 & \text{otherwise} \end{cases}$

答案即为：

$\sum\limits_{j=0}^m\left( \prod\limits_{i=l}^r A_{S_i} \right) ^k_{0,j}$

首先对于最后求总方案数的快速幂，可以利用费马小定理优化，令 $p = 998244353$ 。

$\begin{aligned} \dfrac {1}{2^{k(r-l+1)}} \bmod p &= \left( 2^{k(r-l+1)} \right)^{p-2} \bmod p\\ &= 2^{k(r-l+1)(p-2)} \bmod p\\ &= 2^{k(r-l+1)(p-2) \bmod (p-1)} \bmod p\\ \end{aligned}$

时间复杂度的瓶颈在于矩阵乘法，考虑改如何优化其效率。

因为矩阵构造的特殊性，可以发现对于所有的 $i > j$ 都必定为 $0$ ，对于矩阵对角线上的元素恒为 $1$ ，只有一半的矩阵需要进行矩阵乘法。

根据矩阵乘法的定义， $C_{i,j} = \sum\limits_{k=0}^m A_{i,k}B_{k,j}$ ，由上述性质，只需要对非零的位置做矩阵乘法，即 $i \le k \le j$ ，特化的矩阵乘法式子即 $C_{i,j} = \sum\limits_{k=i}^j A_{i,k}B_{k,j}$ 。

理性分析其矩阵乘法次数， $\sum\limits_{i=0}^m\sum\limits_{j=i+1}^m (j-i+1) = \frac1 6 m(m+1)(m+5)$ ，这里略去不作证明。

时间复杂度 $O\left(\dfrac {Qm^3 \log k}{w}\right)$ ，其中 $w$ 为矩阵乘法优化的常数，约等于 $5$ 。

在 $m$ 较小时可以近似认为是 $O(Qm^2 \log k)$ 。

E Solution

by Anemones

首先根据期望的线性性展开原式：

$E\left[\sum_{i=1}^{n} (x_i - y_i)^2\right] = \sum_{i=1}^{n} \left( E[x_i^2] + E[y_i^2] - 2E[x_i y_i] \right)$

由于 $x_n = y_1 = \max \{c_1, \dots, c_n\}$ ，可以证明恒有 $\sum\limits_{i=1}^n(x_i-y_i)^2 = \sum\limits_{i=1}^{n-1} (x_i-y_{i+1})^2$ 。且序列 $c$ 具有独立性，当考察 $x_k$ 与 $y_{k+1}$ 时，两者分别由互不相交的随机变量集合 $\{c_1, \dots, c_k\}$ 与 $\{c_{k+1}, \dots, c_n\}$ 决定。因此 $x_k$ 与 $y_{k+1}$ 相互独立，满足 $E[x_k y_{k+1}] = E[x_k]E[y_{k+1}]$ 。

于是我们只需要分别计算出所有前缀最大值的一阶矩 $E[x_k]$ 和二阶矩 $E[x_k^2]$ ，后缀部分同理可得。

在离散概率空间内，对于取值范围在 $[1, V]$ 的随机变量 $X$ ，其矩的计算可转化为累积分布函数（CDF）的求和：

$E[X] = \sum_{t=1}^V P(X \ge t) = \sum_{t=1}^V (1 - P(X \le t-1))$

$E[X^2] = \sum_{t=1}^V (2t - 1) P(X \ge t) = \sum_{t=1}^V (2t - 1) (1 - P(X \le t-1))$

令 $F_k(t) = P(x_k \le t) = \prod_{j=1}^k P(c_j \le t)$ 。由于 $c_j$ 在 $[a_j, b_j]$ 内均匀分布，其单变量 CDF 为：

$P(c_j \le t) = \begin{cases} 0 & t < a_j \\ \frac{t - a_j + 1}{b_j - a_j + 1} & a_j \le t \le b_j \\ 1 & t > b_j \end{cases}$

显然， $P(c_j \le t)$ 在由所有 $\{a_j\}$ 和 $\{b_j+1\}$ 构成的 $O(n)$ 个离散区间内是关于 $t$ 的一次式。因此， $F_k(t)$ 在每个离散区间内是一个最高 $k$ 次的多项式。

我们考虑离散化数轴，对每个区间维护多项式系数。每引入一个新的 $c_k$ ，若区间在 $[a_k, b_k]$ 内，多项式执行一次 $O(n)$ 的乘法更新：

$F_k(t) = F_{k-1}(t) \times \left( \frac{1}{len} t + \frac{1-a_k}{len} \right)$

区间内的矩贡献则利用伯努利数预处理的自然数幂和公式 $S_d(n) = \sum_{i=1}^n i^d$ 进行 $O(n)$ 求解。

最后，通过前缀和后缀的矩合并答案：

$\sum_{k=1}^{n-1} \left( E[x_k^2] + E[y_{k+1}^2] - 2E[x_k]E[y_{k+1}] \right)$

不难证明这个式子和原式等价。

F Solution

by Wa1ChA

设 $a,b,c,d$ 为排列 $P$ 中的四个下标（不重），满足 $a<b<c<d$ 。我们对他们的值 $P_a,P_b,P_c,P_d$ 的大小关系进行讨论。

$P_a<P_b<P_c<P_d$ 。

显然有 $|P_d-P_a|+|P_c-P_b| = |P_c-P_a|+|P_d-P_b|$ ，读者自证不难。
$\max(P_a,P_d)<\min(P_b,P_c)$ （ $\min(P_a,P_d)>\max(P_b,P_c)$ 同理）。

不等式左侧为 $|P_d-P_a|+|P_b-P_c|$ ，右侧为 $|P_c-P_a|+|P_d-P_b|=P_c-P_a+P_b-P_d$ 。

右式减左式得： $P_b$ 或 $P_c$ 中一个数的两倍，减去 $P_a$ 或 $P_d$ 中一个数的两倍。由 $\max(P_a,P_d)<\min(P_b,P_c)$ 易得差值 $>0$ ，故左式恒小于右式。
$P_a<P_c<P_b<P_d$ （ $P_c<P_a<P_d<P_b$ 同理）。

不等式左侧为 $|P_d-P_a|+|P_c-P_b| = P_d-P_a+P_b-P_c$ ，右侧为 $|P_c-P_a|+|P_d-P_b| = P_c-P_a+P_d-P_b$ 。

因为有 $P_b-P_c>P_c-P_b$ ，所以左式恒大于右式。

综上，三种情况成立条件无交。

本题定义存在情况 $2$ 或 $3$ 为合法排列。考虑容斥，答案即为：排列总数 - 无情况 $2$ 的排列数 - 无情况 $3$ 的排列数 + 只有情况 $1$ 的排列数。

排列总数

$=n!$ 。时间复杂度 $\mathcal{O}(n)$ ，快速阶乘可以做到 $\mathcal{O}(\sqrt n\log n)$ 。

无情况 $2$ 的排列数

约定 $(P_a,P_b,P_c,P_d)$ 表示当 $a<b<c<d$ 时的一个合法四元组。

结论：无情况 $2$ 的排列中， $1$ 所在的下标集合为 ${1,2,3,n-2,n-1,n}$ 。

考虑反证法。若 $1$ 的下标不在上述集合中，不失一般性地，我们讨论 $2$ 的下标（约定 $x,y\in [3,n]\cap\mathbf{Z}$ ）：

若 $2$ 的下标为 $1$ 或 $n$ ：存在 $(1,x,y,2)$ 满足情况 $2$ 。
否则，一定存在 $(x,1,2,y)$ 满足情况 $2$ 。

分类讨论 $1$ 的下标：

下标为 $1$ ：规模为 $n$ 。
下标为 $2$ ：容易证明 $2$ 的下标一定为 $1$ 。此时可以把 $1,2$ 两个数看作一个数，原问题规模减小为 $n-1$ 。
下标为 $3$ ：容易证明 $2$ 的下标一定为 $1$ ， $3$ 的下标一定为 $2$ 。此时可以把 $1,2,3$ 三个数看作一个数，原问题规模减小为 $n-2$ 。

容易发现， $n,n-1,n-2$ 三个数字的关系也是满足上述结论和分讨的。

考虑如何刻画这个序列。

我们从小到大向排列里面加入数字。令已经被填入数字的位置状态为 $\texttt{1}$ ，未被填入数字的位置状态为 $\texttt{0}$ 。则根据上述三种讨论，把上述三种初始状态单独拉出，产生初始形如 $\texttt{10000...00}$ 的序列 $S$ 。

在加入任意个数字后，这个序列无情况 $2$ 当且仅当：

$\forall (a,b,c,d)\in ([1,n]\cap Z)^4,a<b<c<d,(S_a=1\wedge S_b=0\wedge S_c=0\wedge S_d=1)\vee(S_a=0\wedge S_b=1\wedge S_c=1\wedge S_d=0)=0$

假设当前 $S_i$ 被填为 $\texttt{1}$ 。那么我们接下来仅可以把 $S_{i+1}$ 或 $S_{i+2}$ 填为 $\texttt{1}$ 。

若把 $S_{i+1}$ 填为 $\texttt{1}$ ，则无影响。
若把 $S_{i+2}$ 填为 $\texttt{1}$ ，再下一次必须要先把 $S_{i+1}$ 填为 $\texttt{1}$ 。否则在 $S_j(j>i+2)$ 填为 $\texttt{1}$ 时，违反上述条件。
显然不能将 $S_j(j>i+2)$ 填为 $\texttt{1}$ 。

这个非常好 dp。令 $f_i$ 表示 $1\sim i$ 的合法排列总数，有 $f_i\gets f_{i-1} + f_{i-2}$ 。

读者仔细思考会发现，这个 dp 在序列末尾存在边界问题。但笔者提及过 $n,n-1,n-2$ 三个数字的关系满足由 $1$ 推导的结论和分讨。这三个数显然是最后放入的，把序列视作缺失末尾部分，直接 dp 就是对的。

暴力求出 $f_i$ 在 $i$ 较小时的边界，答案即为 $f_{n-4}$ 。

时间复杂度 $\mathcal{O}(n)$ ，使用矩阵快速幂优化可以达到 $\mathcal{O}(k^3\log n)$ 。其中 $k$ 为矩阵大小，本题中 $k = 2$ 。

无情况 $3$ 的排列数

类似上文，我们刻画这样的序列。

我们从小到大向排列里面加入数字。令已经被填入数字的位置状态为 $\texttt{1}$ ，未被填入数字的位置状态为 $\texttt{0}$ 。

在加入任意个数字后，这个序列无情况 $2$ 当且仅当：

$\forall (a,b,c,d)\in ([1,n]\cap \mathbf{Z})^4,a<b<c<d,(S_a=1\wedge S_b=0\wedge S_c=1\wedge S_d=0)\vee(S_a=0\wedge S_b=1\wedge S_c=0\wedge S_d=1)=0$

当序列全为 $\texttt{0}$ 时，我们可以任选一个位置放入。

若选择位置下标为 $1$ 或 $n$ ，则每次只能在 $\texttt{0}$ 串开头和末尾把一个 $\texttt{0}$ 变为 $\texttt{1}$ 。
否则，每次只能把与 $\texttt{1}$ 串相邻的 $\texttt{0}$ 变为 $\texttt{1}$ 。当有一侧的 $\texttt{0}$ 被清空后，转化为了上一种情况。