考虑这个旋转操作，本质上就是把一个字符往左移动一些位。

如果两个字符串每个字符的数量相等，那么如果从左到右逐一归位必然可以构造出一组解，当然如果数量不同那肯定没法归位。

然后不难发现本质上就是一个匹配问题，我们固定一些 $S$ 中的位置，这些位置必须满足在 $T$ 中的相对顺序和在 $S$ 中一样，只归位剩下的，不难发现必然也是一组解。

相当于我们现在要找一个类似 LCS 的东西。但是会发现它和 LCS 是有差别的直接拿 LCS 不太对。因为当有一个 $S$ 中的位置和 $T$ 中的一个位置 $c$ 不匹配的时候，我们必须保证 $S$ 中这个位置后面必须有一个 $c$ ，然后把 $c$ 挪上来和这个 $T$ 的位置匹配。也就是说，如果 $S$ 中的 $c$ 的个数小于当前 $T$ 中的个数，那么我们不能在这里让 $S$ 中的这个位置失配。

我们考虑生成一棵生成树的过程，本质上相当于是选择一些生成树拼起来，而两个生成树拼起来的代价就是把拼接点的权值乘上点的个数积。

于是可以考虑一个 $dp$ ，设 $dp[S][u]$ 表示一个点集 $S$ 组成的根为 $u$ 的树可以得到的最小权值。

Interesting Drug

考虑选择物品的过程，选择物品就会删掉这个东西，所以相当于是一个扩展区间的过程。

第一步选择 $i$ ，也就是说最开始区间是 $(i,i)$ ，每轮可以扩展到 $(i-1,i)$ 和 $(i,i+1)$ 。

把这个看成一个二维平面上行走的过程，那么我们可以把这个过程倒过来，也就是初始在 $(1,n)$ ，走到 $(i,i)$ 能得到的最大权值。

第二次学了，上次的文章在这里：生成函数与组合计数

先粘一下以防以后忘了：

这次会以 $F(z),x$ 作为形式幂级数，也就是说后文的 $x,x_0,\dots$ 都是形式幂级数。

前置芝士：泰勒展开，在上次的文章中可以看到。

根据 LP对偶（我不会的东西）有这么个结论：

最大费用循环流等价于：

$\min \sum_{(u, v) \in E} c(u, v) \max \left(w(u, v)+h_{u}-h_{v}, 0\right)$

其中 $h_u$ 是给每个点任意定的一个权值，$c(u,v)$ 为一条边的容量，$w(u,v)$ 为一条边的费用。可以带入最大流和最小割验证。

昨天写了忘发了。。

考虑容斥，设 $f(i)$ 表示钦定了 $i$ 个数只出现了 $\le 1$ 次时的方案数量，那么答案显然等于

$ans = \sum_{i=0}^n (-1)^i f(i)$

考虑我们钦定的 $i$ 个数，显然可以直接假定为 $1\sim i$ ，最后再乘个 $\binom n i$ 的系数即可。

先考虑除开前 $i$ 个的数，这些数是没有限制的，他们可以组成集合的方案数量是 $2^{2^{n-i}}$ 种，因为任何一个这 $n-i$ 个数的子集都可以作为某一种集合出现或者不出现。

再考虑前 $i$ 个数的加入。假设前 $i$ 个数出现在 $j$ 个集合里（因为每个数出现次数不超过 $1$ 所以前 $i$ 个数出现的集合个数 $j$ 也不会超过 $i$ ），考虑枚举这个 $j$ 。

现在我们已经确定了前 $i$ 个数会被分配到 $j$ 个集合里面，其中有些数可能直接被丢掉。然后有两种方法数这个：

Day 0

Day 0 居然放假。。在家里打了下各种多项式板子认真背了下 ppt 上的经典套路。。

据说要考多项式，字符串和计算几何？

考到计算几何就放弃吧（？）大概写了下凸包和半平面交。。反正几何算是知识盲区了。。不过按照前几年的惯例SC出几何多半全场都不可写吧（确信。。（mmp后来证明毒奶了）

背不到SA，写了下后缀平衡树（写不来SA要排序就上这个反正复杂度一样）SAM 写了一下还是忘不掉的，PAM 前两天也复习过了。

假装准备得很充分了。。晚上和 wkr 和 ywh 颓了会儿 arc 。。

由于是做题时写的思路所以可能很乱 /kk

首先考虑 $k = 1$ 的情况。我们希望对于每一个 $i$ 求出一个 $j$ 使得 $\gcd(i,j) = 1,\max |a_i - b_j|$ 。

比赛链接

A qiqi20021026 的 T1

这题出的真离谱。。

考虑 $O(qn)$ 怎么做。显然建 trie 树后直接在上面求子树内第一个串的个数和第二个串的个数的最小值贡献在答案里面就行了。

正解，直接上四维莫队。由于 $n$ 比较大，串长期望很小，可以看成移动 $O(1)$ ，然后复杂度 $O(nq^{\frac 3 4})$ （莫队复杂度）。

为什么能跑过去 我也不知道啊。。玄学 。题解写了最后一个指针的移动次数实际上不多。。

$n\le 10^4 , q\le 5\times 10^5$ 能出这个复杂度是真的离谱。

616模拟赛题目背景是 arcaea

B Tempestissimo

抽象一下，这题相当于有一个盒子里面有 $n$ 个球，其中 $m$ 个关键球，求期望抽出所有关键球的时间。

我们可以考虑倒过来，也就是求期望抽出第一个球的时间，最后由 $n$ 减去即可。

考虑这个东西本质上就是

$\sum_{i=1}^{n-m} P[这个球在第一个关键球之前被抽出]$

如果我们把关键球先加进去，每个球在哪两个关键球直接抽出本质上是相同的。由 $m$ 个关键球可以分成 $m+1$ 段，于是概率就是 $\frac{1}{m+1}$。答案就是

$n - \frac{n-m}{m+1}$

但是 $O(\log n)$ 求逆元必然爆炸，可以考虑 希望 的求逆元方式。我们先离线下来所有询问，假设我们得对 $a_1,a_2,\dots a_n$ 求逆元，我们可以求出这个序列乘起来的逆元，设为 $M$ ，如果需要 $a_i$ 的逆元，我们可以直接拿 $M$ 乘上一段前缀积和后缀积即可。

复杂度 $O(T)$。

---

但是这个题如果暴推组合数也是可以做的（而且还可以练习组合恒等式）。

比赛链接

A sequence

首先，和谐的数列可以仅由前两个数递推得到。然后可以证明，如果第一个数确定，答案关于第二个数凸，如果第二个数永远取最优，答案关于第一个数凸。所以可以直接三分套三分来做。但是这样是 $O(n\log^2 v)$ 的，很可能会被卡 T 。

考虑和谐的序列的循环节一定是 $6$ ，所以可以对于 $\bmod 6$ 的所有值分别整个 vector 再做个前缀和，查询可以直接从每个 vector 二分。复杂度 $O(n\log n + \log^3 v)$

当然，也可以暴力整凸包复杂度是 $O(n\log n)$ 的，可以见 zjk 的实现。

现在看了看以前的题感觉好妙啊。。多校的时候好像是找出原题直接做的。。

为了回答询问，可以贪心地做前缀的线性基。由于只有 append 操作，可以方便地维护这个。

对于 $1\sim i$ 的线性基，我们可以对每个位置记一个编号，表示能够选择这一位的最靠右的数编号是什么。

在插入一个数到线性基的时候，从高到低位考虑，如果这个数比这个位置上的数更靠右且这个数可以更新这一位，我们可以把这个数和线性基中这个数字交换一下，再更新编号，然后继续向低位更新。

考虑正确性，对于一个位置，它显然只会被比它的编号高的数更新到（否则这个数会和更新它的数交换，然后这个数去更新更低的位置）。而且由于我们是从高到低位贪的，最后查询答案也只需要从高到低位查询一下这个位置的编号是否不小于 $l$ 即可。

我们考虑把输入的矩阵看成邻接矩阵，于是相当于是给了个图。

然后考虑询问，1 的位置就相当于前后有边相连，0 的位置就相当于没有边。于是相当于通过 1 分成了很多个联通块，这些联通块之间不能有边，求可以满足这个条件的排列个数。

这个不好求，我们考虑求钦定了某些位置有边，剩下无限制的方案数量，最后做一次逆与卷积即可。因为设 $F[s]$ 表示钦定了 $s$ 集合的 $1$ 的位置有边，剩下无限制的方案数量，$f[s]$ 表示恰好只有 $s$ 的 $1$ 的位置有边的方案数量。我们显然有

$F[S] = \sum_{S\sube T} f[T]$

这个明显就是与卷积的 FWT，所以如果求出了 $F$ 只需要对其求 逆与 FWT 即可求出答案数组，做到 $O(1)$ 询问。

由于钦定了某些位置有边，相当于是把 $n$ 个点分成了很多个联通块，我们需要满足的是联通块内部是个链，联通块之间没有限制。于是我们可以枚举所有边的状态（一共 $2^{n-1}$ 种），每种状态中 $1$ 表示相邻两个点一定有边，否则表示没有限制。我们考虑拆成联通块大小是 $a_1,a_2,\dots a_x$ ，怎么去计算填排列的方案。相当于我们有 $1\sim n$ 的每个数，我们要把它们拆成很多份，每份内部都可以构成一条链。

我们考虑对每行没列 $\min-\max$ 容斥。

考虑某种状态（行列的状态）每个集合内部的元素（一行或者一列）出现了一个数的最大时间，也就是全部都有数的时间（类似 [HAOI2015]按位或）。由于式子

$\max(S) = \sum_{T\sube S} (-1)^{|T|+1} \min(T)$

也就是我们得算的实际上是每种状态（一些行与列）中的数第一次被选到的期望时间。

考虑对于每一个右端点 $r$ ，维护 $ans_i$ 表示 $\min |a_i-a_j|,j\in[i,r]$ 。

那么如果我们离线下来询问，我们要求的 $[l,r]$ 的答案就是一段后缀的最小值。但是为了保证复杂度，事实上我们维护的 $ans_i$ 只是保证了一段后缀的最小值就是 $[l,r]$ 的答案，而 $ans_i$ 是可能大于 $\min |a_i-a_j|,j\in[i,r]$ 。

现在考虑我们把 $r - 1$ 移动到了 $r$ ，并且已经维护好了右端点为 $r - 1$ 时的 $ans$ ，满足了 $[l,r]$ 的答案就是 $ans$ 的一段后缀最小值，考虑接下来如何修改。

首先，暴力修改的复杂度肯定有问题。但是可以发现，由于我们求答案是算后缀的最小值，事实上有些位置是没有必要修改的。

对于每个 $ans_i$ ，只会有 $O(\log a_i)$ 个位置让这个位置答案必须被修改。

必须 被修改？因为有些位置是可以不用被修改的。如下图：

如图，考虑 $a_i$ ，之前最优位置在 $a_j$ ，当前加入了 $r$ ，其中黑线表示 $\frac{a_i+a_j} 2$ 的位置。

考虑跑出 dfs 树。如果两个点在 dfs 树上路径本身长度就是奇数，可以直接走过去。

否则，相当于可以在这两点之间的路径上有两个点 $u,v$ ，可以通过在 $u$ 离开 dfs 树上的路径然后从 $v$ 回来继续走到另一个点的方式改变奇偶性。不难发现，这个条件等价于 $u,v$ 之间的路径存在于一个奇环上。同时我们还有一个结论，一个点双（因为这题要求点不相交）内部如果有一个奇环，那么点双内部任何两个点都处在一个奇环。

于是我们考虑给所有点双内有奇环的点打个标记，然后树上差分，询问的时候就询问一下两个点之间的路径上是否有点处于点双即可。

但是还是会出现一些会导致这个东西不太对的情况。

也就是说，进入一个点双了之后没办法通过不经过重复点跑出来。

考虑一次查询，比如查询 $[l,r]$ 区间。

首先找出区间内最小值的位置，设为 $pos$。

考虑把询问的区间的子区间分成三种：

1. 跨过了 $pos$
2. 左右端点都在 $[l,pos-1]$
3. 左右端点都在 $[pos+1,r]$

考虑分别处理。对于第一种，明显贡献是 $(pos-l+1)(r-pos+1)$ 。

下面设 $[l,r][L,R]$ 表示左端点在 $[l,r]$ 内，右端点在 $[L,R]$ 内的所有区间的最小值的和。

我们考虑怎么求 $[l,r][l,r]$ 的值。我们把这个拆成：

$[l,n][l,n] - [r + 1,n][r + 1,n] - [l,r][r + 1,n]$

也就是左右端点都在 $[l,n]$ 减去左右都在 $[r+1,n]$ 再减去左端点在 $[l,r]$ 右端点在 $[r+1,n]$ 的贡献。

一种用来求最短线性递推的奇妙算法。复杂度是 $O(n^2)$ 。

忘了怎么做建议看看这个博客，很清楚了。