A

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

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

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

B

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

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

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

证明

我们找到一个中位数 $\geq k$ 的区间,如果这个区间没有包含所有的 $k$,那么可以任意调节长度然后对整体操作;如果包含了所有的 $k$,肯定能找到一个位置把它分成两段,某一段和为 $0$。然后直接操作即可。

如果没有这样的区间,$\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$。

举个栗子

假设排列是 $[3,5,4,6,2,1]$,那么应该划分成$[3|5,4|,6,2,1]$,对应的序列就是 $[3,3,1,2,2,3]$。

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

相当于每有一个 <,填的数字就会 $+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

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

Last modification:August 28th, 2020 at 09:15 pm
如果觉得我的文章对你有用,请随意赞赏