2023“钉耙编程”中国大学生算法设计超级联赛（4）

1001. Number Table

1002. Simple Tree Problem

1003. Simple Set Problem

题意：从 $k$ 个可重集中各选出 $1$ 个数，求选出来的 $k$ 个数形成的数列的最大值与最小值的差的最小值

考虑枚举数列的最小值，那么只需要其它序列比这个值大就可以了，只要单调枚举最小值的话其他位置的值的个数也是线性的，最终枚举的个数就是 $k$ 个集合大小的总和，复杂度 $O\left(\sum\limits_t\sum\limits_{i=1}^k c_i\right)$，可以通过

1004. Data Generation

1005. Teyvat

1006. PSO

题意：给出 $n$ 个点，求 $n$ 个点随机连成一个菊花图，任意两点之间距离的期望值

签到题，答案就是 $\frac 2n1+\frac{n-2}n2=\frac{2n-4}n$，直接输出即可

1007. Guess

题意：求 $e^{\sum\limits_{d \vert n} \mu(\frac nd)\ln d} {\rm\ mod\ } 998244353$

数学题，推公式即可，具体如下： $$\begin{align} &e^{\sum\limits_{d \vert n} \mu(\frac nd)\ln d}\ =&\prod\limits_{d \vert n} e^{\mu(\frac nd)\ln d}\ =&\prod\limits_{d \vert n} d^{\mu(\frac nd)}\ =&\begin{cases}1 &,n=1\p &,n=p^k\1 &,n=\prod\limits_{i=1}^k p_i^{c_i}\end{cases} \end{align}$$

质因数分解之后求解即可，由于 $n$ 是 $1e18$ 级别的，所以要用到 Pollard-Rho，复杂度 $O(n^\frac 14)$，可以通过

1008. String and GCD

题意：给定字符串 $S$，求 $\prod\limits_{i=1}^n\left(1+\sum\limits_{j=1}^{i-1} [S[1:j]=S[i-j+1:i]]gcd(i,j)\right) {\rm\ mod\ } 988244353$

首先看到 $S[1:j]=S[i-j+1:i]$ 可以很快想到 KMP，将 KMP 的 fail 树建出来就可以发现原问题转化为了求 $\prod\limits_{i=1}^n\left(1+\sum\limits_{j \in fa(i)} gcd(i,j)\right)$，其中 $fa(i)$ 表示 $i$ 的所有祖先节点构成的集合

对于 gcd，我们可以将其反演为 $\sum\limits_{d \vert i,d \vert j}\varphi(d)$，这样就可以把原问题变成 $i$ 的每个约数在祖先的约数构成的可重集中出现的次数，这个问题可以用一个 $O(n)$ 的桶解决。由于所有的约数是 $1 \sim n$ 的约数，所以约数总个数是 $O(n\ln n)$ 级别的，因此求解的总时间复杂度就是 $O(n\ln n)，可以通过

1009. WO MEI K

1010. Kong Ming Qi

题意：求一种孔明棋平局的棋盘

构造题，解法有很多，这里给出我的一种解法：

xoxoxo... xoxoxo... oxoxox... oxoxox... xoxoxo... xoxoxo... ......... ......... .........

类似左上角那样向右、向下延伸即可

1011. Circuit

题意：给出一个带权有向图，求图中的最小环大小与个数

求最小环立马想到 Floyd，但直接跑 Floyd 的话没法对最小环的个数去重，因此需要对 Floyd 进行魔改。

考虑 Floyd 的 dp 定义：在最外层循环到 $k$ 时，$dp_{i,j}$ 表示 $i,j$ 除自身外只经过 $[1,k]$ 的节点的最短路。对于每个最小环，只在编号最大的节点统计其贡献。通过 dp 的定义容易发现当外层循环到 $k$ 时，$dp_{i,i}$ 表示的正是经过节点最大编号为 $k$ 最小环，所以只需要在循环到 $k$ 时统计 $dp_{k,k}$ 的贡献即可，最终复杂度 $O(n^3)$，可以通过

1012. a-b Problem

题意：一个 $1 \sim n$ 的数列，Alice 选数 $i$ 的收益是 $A_i$，Bob 选数 $i$ 的收益是 $B_i$，Alice 和 Bob 轮流取数，双方都想让自己的分数 $-$ 对方的分数最大化，求两人在采取最优策略的情况下两人的分差

首先考虑对于 Alice 而言选 $i$ 比选 $j$ 更优意味着什么，然后就可以得到一个不等式：$A_i-B_j>A_j-B_i$ ，移项后可以得到 $A_i+B_i>A_j+B_j$，对于 Bob 可以得到相同的不等式，所以两人的选择本质上就是把数列按 $A_i+B_i$ 从大到小排序之后依次取第一个数得到的结果，排序后直接做即可，复杂度 $O(n\log n)$，可以通过