本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-08 20:13:36

考虑到如果是整个区间怎么做。设 $f_i$ 表示以 $i$ 为结尾的合法子序列数量。那么

$$ f_i = 1 + \sum\limits_{j\lt i, a_j\mid a_i} f_j $$

考虑可以扫描线。固定左端点，从后往前，考虑 $i$ 作为左端点对于后面的贡献。那么，所有是 $a_i$ 的的倍数的 $\rg a_i\mid a_j$，都可以使得 $f_j$ 加上 $1$。同时，可以间接转移，也就是使得 $a_i\mid a_j\mid a_k$ 的 $f_k$ 上头加上 $f_j$。

我们这么样就做完了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-11 09:46:43

考虑到每个点最多至多被两个集合包含。

如果只被一个集合包含，那么这个集合的状态就确定了；

如果被两个集合包含，那么我们就知道了这两个集合的关系。然后用带权并查集维护连通块大小，动态维护就好了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-02 17:25:44

全用质数是可以的。这样，我们考虑将所用的质数作为点，将所有点之间直接连边，表示这两个点可以相邻。任意一条边不能走一次以上。这就是一个欧拉回路问题。

我们考虑需要取多少个点。如果有 $m$ 个点，那么每个点都和 $m - 1$ 个点有边，同时有自环。那么是 $m(m-1) / 2 + m$ 条边，也就是用 $m$ 条边能构造出的最长的路径长度。

但是考虑当 $2\mid m$ 时是不存在欧拉回路的。也就是，我们没法把这些边全都用上。所以我们把用不掉的删掉。删除一条边，最好能减少两个奇点，所以至少删掉 $m/2 - 1$ 条边。这样能保证这张图存在一条欧拉路径。不妨把偶数到奇数的边删掉。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 20:27:41

P2371 为例。

我们可以取一个数 $m \in A$，然后设 $f(k)$ 表示模 $m$ 为 $k$ 时整个式子最小值。

明显有 $x$ 可以转移到 $(x + a_i) \bmod m$，权是 $a_i$。由于有后效性，我们不能直接转移，考虑最短路就可以跑出来。

然后我们可以把 $[l, r]$ 差分成 $[1, r] \cap [1, l - 1]$ 来统计答案。考虑怎么统计 $[1, x]$ 的答案。如果 $f(i) \le x$，那么我们可以把 $f(i)$ 加上任意个 $x$。所以解的数量就是 $\dfrac{x - f(i) + 1}{x} + 1$。

然后统计就行了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-30 09:33:16

我们考虑到当序列中数互不相同时，交换任意两个数都会使逆序对的奇偶性变化。若 $a_i \lt a_j, i\lt j$ 交换，那么交换后逆序对数量加一；否则，逆序对数量会减一。

因此我们可以考虑把操作一和二转化为交换操作。

二操作其实可以转化为交换区间 $[l, r]$ 和 $[r + 1, k]$。

我们考虑一操作。

我们发现，$[l_1, r_2]$ 以外的部分，是不会受到影响的，因为只是这个区间之内的相对位置发生了改变。

具体来说，$[l_1, r_1]$，$[r_1 + 1, l_2 - 1]$ 和 $[l_2, r_2]$ 内部的逆序对也没有变化。

因此，实际上我们进行的操作就是把这几个区间之内的数按序交换。交换的总数是 $L_1L_2 + L_1L_3 + L_2L_3$，其中 $L$ 是每个区间的长度。

三四操作是显然的。

因此我们判断它的奇偶性，这个题就做完了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-31 20:15:28

还是非常有意思的组合题。

我们知道一条路径的长度是不大于 $\log n$ 的，也就是说这条路径上有最多 $\log n$ 个点。

由于这是一个伪二分查找，所以说每个点上的数与要找的 $x$ 的关系是确定的。不妨设 $L$ 表示小于 $x$ 的数的数，也即向右拐，$R$ 是向左拐的数量，以及 $E$ 是相等的数量，显然 $E$ 不大于一（这里直接搬了题解的符号）。

我们考虑确定的 $L$、$R$ 和 $E$ 对应多少个序列，也就是算一个固定的 $y$ 对答案的贡献。

考虑 $y \lt x$，因为 $y \gt x$ 的情况是对称的。（越来越像题解了）

首先 $y$ 有 $L$ 种选法，然后剩下的 $L - 1$ 个链上的位置有 $x - 2\choose L - 1$，并乘上排列；同样的，$R$ 的方案是 $n - x\choose R$，同样乘排列。剩下的位置任选，乘上排列是 $(n - L - R - E)!$。最终，一个 $y\lt x$ 对答案的贡献是

$$ yL {x - 2\choose L - 1} \bigg(L-1\bigg)! {n - x\choose R} R!\bigg(n - L - R - E\bigg)! $$

对于 $y\gt x$，贡献是

$$ yR {n-x-1\choose R-1}\bigg(R-1\bigg)!{x-1\choose L}L!\bigg(n - L - R - E\bigg)! $$

对于 $y = x$，贡献是

$$ xn{x-1\choose L}L!{n-x\choose R}R!(n-L-R-E-1)! $$

（好像是吧）。

确定了 $x$、$L$、$R$ 和 $E$，这串东西就可以 $O(1)$ 出。

$x$ 是询问给出的，我们现在的目的就是怎么快速得出后三者。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-01 21:24:40

首先发现这个过程很类似埃筛，每个数把它的所有倍数筛掉。

然后可以知道，有的数字是不能被其他数字筛掉的，比如任何质数都不可能被其他数筛掉。当然，这只是个充分不必要条件。

可以把这些不能被别的数筛掉的数，叫做唐数。

然后发现 $t(p)$ 本质上就是 $p$ 排列中最后面的那个唐数的位置。

我们可以考虑枚举这个最后的位置，然后来算贡献。

设 $w$ 表示唐数的数量，这可以用类似筛法的东西 $O(n\lg\lg n)$ 预处理出来。

枚举这个最后的位置 $x$：

它本身肯定要选一个唐数，方案数是 $w$；

后面一个唐数也不能选，也就是把剩下的 $n - w$ 个不同的数分配给 $n - w$ 个位置，所以方案数是 ${n-x\choose n-w} (n-w)!$；

前面是任意选的，方案数是 $(x - 1)!$

所以一个 $x$ 的贡献是

$$xw{n-x\choose n-w}(n-w)!(x-1)!$$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 14:26:58

很难不设状态 $f(i, j)$ 表示前 $i$ 个数，已经选的和是 $j$ 的最少代价，那么很难不注意到显然的转移

$$f(i, j) = \min\limits_{k=0}^j f(i - 1, j - k) + w(k)$$

其中，$w(k)$ 是比 $k$ 大的数的数量。很难不做到 $O(nm^2)$

然后考虑优化。

很难发现

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 16:03:14

要求一堆形如

$$x \equiv k_i\pmod {p_i}$$

的同余方程的解。

设 $P = \prod p$，则

$$x = \sum k_i \dfrac P {p_i} (\dfrac P {p_i})^{-1} \bmod P$$

其中这里的逆元是模 $p_i$ 意义下的。

考虑为什么。

不难发现，对于第 $i$ 个同余方程，对于 $i \ne j$ 都有 $P/p_j \equiv 0 \pmod {p_i}$，因为里头本来就有个 $p_i$。

于是式子就剩下了当前这一项。而 $P/p_i$ 乘上其模 $p_i$ 意义下的逆元本身就是一，于是就剩下了 $k_i$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 20:51:14

exCRT 的核心就是合并两个同余方程的解。

考虑

$$ \begin{cases} x \equiv w_i \pmod {p_i} \ x \equiv w_j \pmod {p_j} \end{cases} $$

那么有

$$x = p_ik_i + w_i = p_jk_j + w_j$$

这时候可以用扩欧解出来 $k_i$ 和 $k_j$，以此还原出 $x$，然后继续合并。