A

因为 $\gcd$ 是指数取 min，$\text{lcm}$ 是指数取 max，所以我们对于每一个质数分开考虑。

设第 $i$ 个数唯一分解后在这个质数上的指数是 $e_i$，设次小值是 $cmx$，答案贡献 $p^{cmx}$。

具体实现的时候质因数分解一下即可。

B

首先序列里一定要有 $k$ 这个值。

如果 $k$ 两边有一个 $\geq k$ 的数，就可以把这两个数都变成 $k$，然后每次选择这两个数和周围的一个数就可以合并起来了。

所以等价于我们能选出一个中位数 $\geq k$ 的区间。

C

这个和那个真正的的生命游戏不一样！！迷惑了我半天

我们发现如果一个数周围至少有一个和它相同的数，那么这两个数就会一起持续变颜色。

所以我们只需要求出来所有点从什么时候开始周期变颜色就好了。

可以把一开始就变色的点都扔进 queue 里，每个点向周围连边，跑一个边权为 1 的 bfs。

D

以下题目设 $m=\sum_{i=1}^n a_i$

期望题肯定先拆开看看啊。但是我想不到怎么设。

设 $E_i$ 表示到 $i$ 个点结束的答案的和（所有情况的概率乘时间的和），$E'_i$ 表示强制到 $i$ 点结束的期望时间，$P_i$ 表示在 $i$ 点结束的概率，$C$ 表示饼干从 $i$ 全部转移到 $j$ 的期望时间（显然都相等）。

观察可以发现 $\sum_{i=1}^n P_i = 1,ans = \sum_{i=1}^n E_i$。

首先可以得到

$$ E_x = E'_x-\sum_{i=1}^n [x \neq i] (E_i+P_iC) $$

就是枚举第一个到达的点是哪里，然后走过来（$E_i+P_iC$ 的理解只需要把 $E_i$ 拆成所有情况的概率乘时间的和就行了）。

移项可得

$$ \sum_{i=1}^n E_i = E'_x-C\sum_{i=1}^n [x \neq i]P_i $$

两边对 $x$ 从 $1$ 到 $n$ 求和，可以得

$$ ans = \frac{\sum_{i=1}^n E'_x-(n-1)C}{n} $$

所以目标就是求 $E'_x$ 和 $C$。

发现这两个东西之和目标的人有多少个饼干有关，设 $f_x$ 表示目标人有 $x$ 块饼干，到有全部饼干的期望时间。考虑这一步的饼干选出情况可以得到：

$$ f_i = \begin{cases} 1+\frac{m-i}{m}(\frac{1}{n-1}f_{i+1}+\frac{n-2}{n-1}f_i)+\frac{i}{m}f_{i-1} & 0 < i < m\\ 1+\frac{n-2}{n-1}f_1+\frac{1}{n-1}f_0& i=0\\ 0&i=m \end{cases} $$

这样直接高斯消元理论上就行了，但是实际上会遇到系数是模数倍数的情况然后就会被叉死。

所以我们考虑能否改成一个线性递推：发现这个式子 $f$ 的系数和为 $1$，对于这样的式子我们考虑把 $f_i$ 表示成前缀和（后缀和）能消掉一个方向的所有东西就好了。

为了方便我们设 $g_i = f_{i}-f_{i+1},f_{m+1}=0$，容易得到 $f_{i} = \sum_{j=i}^m g_i$。

所以我们把 $0 < i < m$ 的式子拿出来看看：

$$ \begin{aligned} \sum_{j=i}^m g_j = 1+\frac{n-i}{m}(\frac{1}{n-1}\sum_{j=i+1}^mg_j+\frac{n-2}{n-1}\sum_{j=i}^m g_j)+\frac{i}{m}\sum_{j=i-1}^m g_j\\ \end{aligned} $$

注意到 $\frac{m-i}{m}(\frac{1}{n-1}+\frac{n-2}{n-1})+\frac{i}{m} = 1$，式子可以简化为

$$ \begin{aligned} g_i = 1+\frac{n-i}{m}\times \frac{n-2}{n-1}g_i+\frac{i}{m}(g_i+g_{i+1})\\ \frac{m-i}{m(n-1)}g_i = 1+\frac{i}{m}g_{i-1}\\ g_i = \frac{m(n-1)}{m-i}+\frac{i(n-1)}{m-i}g_{i-1} \end{aligned} $$

然后只需要求出 $g_0$ 就可以递推了。

我们发现：

$$ \begin{aligned} g_0 = f_0-f_{1}\\ f_0 = 1+\frac{n-2}{n-1}f_0+\frac{1}{n-1}f_1\\ \end{aligned} $$

联立可以求出 $g_0 = n-1$。

递推即可。不会出现高斯消元系数是模数倍数最后除 $0$ 直接 RE 那么鬼畜的情况了。

E

这种看帽子的问题很有意思，我不会做，于是写一下题解思路吧。

首先我们先把标号倒过来，假设 $n$ 在最前面。定义 $t_i$ 表示第 $i$ 个人的离开时间，$c_i$ 表示颜色。

先考虑直到颜色如何求时间。

我们设从前往后第一个黑色是 $x$，讨论两种情况：

1. $x=1$，$1$ 看到前面都是白色+知道有黑色就在第一轮跑路了，剩下的人就在第二轮跑路了，$t_1=1,t_i=2(i\geq 2)$
2. $x \geq 2$，$1$ 不能确定所以不跑路，所以大家都知道了 $\geq 2$ 的人有黑色，就相当于变成了 $2\ldots n$ 的子问题。直到 $x$ 轮，$x$ 就可以跑路了，剩下的 $x+1\ldots n$ 在 $x+1$ 轮跑路并且变成了 $1\ldots x-1$ 的子问题，$t_x=1$,$t_i=2(i > x)$。

于是我们可以方便求出 $t$ 的值，对于每一个位置 $i$：

• $c_i=1$，则 $t_i = \sum_{j > i,c_j=1}j$，此时记 $b_i=i$
• $c_i=0$，设 $k$ 是它后面第一个黑色，则 $t_i = t_k+1$，记 $b_i=k$。

发现二情况可能没人，所以我们在 $0$ 位置加一个 $t_0=\sum_{c_j=1}j$ 的不参加游戏的人即可。这样就都是良定义的。

所以我们求出来 $b_i$ 后就可以用 $t_i = t_{b_i}+(1-c_i)$ 求时间了。

现在考虑如何做原问题：

首先观察一下，对于 $i \geq j$，如果 $c_i = c_j = 1$，一定有 $t_i \leq t_j$。又对于 $i > j$，有 $b_i \geq b_j$，所以

$$ \forall i > j,t_i-t_j = t_{b_i}+(1-c_i)-t_{b_j}-(1-c_j) = t_{b_i}-t_{b_j}+(c_j-c_i) \leq c_j-c_i \leq 1 $$

分类讨论可以得到：

$$ \left\{\begin{array}{l}t_{i}-t_{j}=1, \text { if } c_{j}=1 \text { and } \forall i \geq k>j, c_{k}=0 \\ t_{i}-t_{j}=0, \text { if } \exists i>k>j, c_{k}=1, c_{1}=c_{2}=\cdots=c_{k-1}=c_{k+1}=\cdots=c_{n}=0 \text { or } \forall i \geq k \geq j, c_{k}=0 \\ t_{i}-t_{j}<0, \text { otherwise }\end{array}\right. $$

于是如果我们把区间分成满足 $i>j,t_i-t_j \geq 0$ 的合并，一定形成了若干不交区间，如果 $l_i \neq 1$ 就会满足：

• $c_{l+1}=c_{l+1}=\ldots=c_r=0$
• $b_l = b_{l+1}=\ldots=b_r$，记其为 $B[l,r]$

显然 $B$ 越大越好（后面可分配空间越多）于是我们可以对这个东西 dp：设 $f_{i,0/1}$ 表示处理好了 $i\ldots m$，当前这一段的 $c_{l_i} = 0/1$ 的最大的 $B$。

从 $f_{i+1,j}$ 转移到 $f_{i,j'}$ 只需要枚举所有可能的 $f_{i,j'}$，判断一下：

$$ t_{f_{i,j'}} = \sum_{k \geq f_{i,j'},c_k=1}k = \sum_{k \geq f_{i+1,j},c_k=1}k + \sum_{f_{i+1,j} > k \geq f_{i,j'},c_k=1}k = t_{f_{i+1},j}+f_{i,j'}+\sum_{r_i < j < f_{i+1,j},c_j=1}k $$

相当于判断从 $[L,R]$ 中选出若干数，和是否能 $=x$。

可以二分选了多少数，能得到区间 $[L+(L+1)+\ldots+(L+num-1),(R-num+1)+(R-num+2)+\ldots+R]$，判断一下就好了。

对于 $l_i=1$ 的时候不满足上述性质，但是 $[l_1,r_1]$ 至多有一个 $i$ 满足 $c_i=1$，可以枚举 $1$ 的位置转移。

代码就先咕咕咕咕了。

F1

首先这个限制条件这么诡异，我们肯定是要转化一下的（然而我思考的时候直接对着做人就没了）

首先打表发现长度为 $n$ 的好的序列是 $n!$ 个，让我们联想到和排列联系在一起。

对于一个排列：我们将其划分成若干段极长连续下降的段，对于第 $i$ 段里的一个数 $x$，令 $a_x=i$。

用这种构造方法不难证明它们之间建立了双射（只需要倒着再构造一次证另一个方向的结论就好了）

相当于每有一个 <，填的数字就会 $+1$。

我们先引入一个欧拉数的概念：$\left<^n_k \right>$，表示长度为 $n$ 的所有排列中，恰有 $k$ 个 $<$ 的排列个数。

显然可以 dp 每次枚举插入位置得到：

$$ \left<^n_k\right> = (k+1)\left<^{n-1}_{k}\right>+(n-k)\left<^{n-1}_{k-1}\right> $$

那么我们在算 $x$ 的出现次数时，我们枚举每一个位置 $p$ 的贡献：显然是 $\left<^p_{x-1}\right>\binom n p (n-p)!$。

组合意义就是首先前面的要划分成 $x$ 段（也就是 $x-1$ 个$<$，它是第 $x$ 段），然后选出一段值域赋给它，后面的没有限制随便排，就算完了这一个位置作为答案的次数了。

F2

你觉得我会二元拉格朗日反演？