如题。可以点击进入用户主页，或者是在用户博客首页点击“关于我”来查看。

可以在博客系统中创建新博客，随后在勋章管理中的自定义页面中展示。

潍坊一中机房残党，不定期维护 WyOJ

目前主要兴趣：云计算与虚拟化、深度学习、Linux 内核、计算机网络与路由、音乐

以往的部分兴趣：计算机组成、操作系统、x86 和 RISC-V、UNIX 与 UNIX 网络编程、计算机图形学

GNU 忠实信徒。GPLv3 忠实用户。

以往完成与未完成的项目：

• WyOJ
• vcc 与 vccd
• evx、xnix 与 cunix
• spearl 与 tripl

如题！

大家可以注意到的是，WyOJ 已经有了一个崭新且漂亮的博客系统。

同时，我把关注列表里的大部分人的博客搬运到了 OJ 上。

众所周知，由于洛谷的特殊情况，洛谷博客现在不太方便。

推荐大家以后使用 WyOJ 的博客系统！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-31 23:37:49

多项式基本中的基本就是著名的 FFT。这个东西一个简单的（也是我现在只会的）用途是做多项式的乘法。

如果能做到两个过程 —— 即给定 $n$ 次多项式，求其在 $n$ 个不同点上的取值；给定 $n$ 个点表示某多项式的某些取值，还原出这个多项式 —— 我们就能快速进行多项式乘法：因为只需要把第一个过程得到的 $n$ 个点上的取值乘起来，然后还原，就好了。

DFT 就是解决这个东西的。我还分不清它和 FFT 的区别，暂且就这么叫着。

首先考虑怎么做第一步。

给定了多项式 $f(x) = \sum\limits_{i=0}^n a_ix$，要求其在 $n$ 个固定点上的取值。

设 $f_0(x)$ 表示这个多项式的偶数项取出来后得到的多项式（次数减半），$f_1(x)$ 表示相应的次数为奇数的。那么 $f(x) = f_0(x^2) + xf_1(x^2)$。这样分治下去，好像很对，但是啥用也没有，因为我们只是知道这两个子多项式在 $n/2$ 个点上的取值，无法解决现在的问题。

考虑：$f(-x) = f_0(x^2) - xf_1(x^2)$。很有启发性啊！这样，递归到 $f_0$ 和 $f_1$ 后，就可以 $O(n)$ 得到 $n$ 个点的取值了。

但是，相反数只有一对，肯定不能按来按去一直用。这个时候考虑把视角放到复数。设 $\omega_n^k = \exp (2\pi k\text{i} / n)$，那么有 $(\omega_n^k)^2 = \omega_{n/2}^k$。这个构造性确实很强，因为递归到子问题时，底标恰好也减半。同时，有 $\omega_n^{k+n/2} = -\omega_n^k$，因此恰好可以把它代入到原式里头。

得到：$f(\omega_n^k) = f_0(\omega_{n/2}^k) + \omega_n^k f_1(\omega_{n/2}^k)$

与：$f(\omega_n^{k+n/2}) = f_0(\omega_{n/2}^k) - \omega_n^k f_1(\omega_{n/2}^k)$。

就可以了。复杂度是线性单对数。

然后是第二步，怎么还原回去呢？经过我还没看的代数推导，只需要把 $f_1$ 前面的系数指数变成负的，最后把所有东西除以一个 $n$，就好了。

待补充：递归转迭代，IFFT 的证明，还有 NTT。

补充：递归转迭代，观察一下就好了。NTT，把 $\omega$ 的定义换一下就好了。IFFT 的证明，还要补。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-08 22:33:12

我们应该怎么维护这些集合？

如果简单的维护每个集合包含哪些数，能快速询问对称差吗？好像很难。

可不可以，考虑在值域上维护？

在值域上维护，用什么数据结构呢？维护什么信息呢？

我们设 $q_{ij}$ 表示第 $i$ 个集合中 $j$ 是否存在，为 $0$ 或 $1$。

那么，$w$ 不在 $x$ 与 $y$ 集合的对称差中，当且仅当 $q_{xw} = q_{yw}$。

相等。想起来什么东西了吗？

哈希。

发现，我们并不需要知道对称差中全部的元素。

因为我们只需要知道最大的，同时，我们又在值域上操作，所以……

想到用什么数据结构了吗？

如提示中所言。

我们用一颗值域线段树来维护一个集合，并在线段树上维护区间的哈希值。

操作一：加入一个数。也就是线段树单点修改某点为一。

操作二：查询对称差的最大值。

我们并不需要知道对称差里头的所有数。

我们想知道的是最大的 $w$，满足 $q_{xw} \ne q_{yw}$。

由于我们维护了区间的哈希值，那么这个问题可以用线段树二分解决。

只需要在每个节点，判断两棵树的右儿子是否相等。相等就往左儿子走，否则往右儿子走，直到走到叶子。

于是本题做完了。时空复杂度都是 $O(n\log V)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 18:56:06

这个循环右移相当不常规吧，所以也很难用常规的状态去描述它。一般的状态没法描述循环右移导致的改变。

我们考虑类似 $f_{ij}$ 的状态，表示匹配到 $s$ 前 $i$ 个字符，$t$ 的前 $j$ 个，所需要的最少的操作数量。

首先有朴素的转移 $f_{i-1j-1} + 1$，当 $s_i = t_j$。

然后，我们可以不让 $i$ 和 $j$ 匹配，而是把 $i$ 塞到前头和某个位置匹配，即 $f_{i-1j} + 1$。

同时，对应着“往前塞”的转移，我们可以也必须有一个“往后放”的转移。不这样的化，往前塞的转移是转移不到 $f_{00}$ 的。这条转移是 $f_{ij} = f_{ij-1}$。

我们想一想这个为啥是正确的。也就是：每一个往前塞的转移，是否都对应前面一个往后放的转移。

这是必须的。因为我们只能从 $(0, 0)$ 出发转移，且只有第一种转移是 $x, y$ 同时加一的；往前塞的转移，会让 $y$ 相对 $x$ 往前移动一步，往后放的转移会让 $y$ 相对 $x$ 往后走一步。如果不是两两对应，还能是什么呢？

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 19:41:38

本来不想打 ABC，unr 看了题，很快啊，一眼序列分治！刚好这几天写了一车序列分治板子，于是就整活写了。

题意是：对于所有子区间，求它的区间和模 $P$ 的加和。只对区间和取模，答案不取模。

首先有简单性质：对于两个小于 $P$ 的数，加起来也小于 $2P$。换句话说，把两个模后的数加起来，再取模，最多就减少一个 $P$。

考虑序列分治，那么区间和由在中点左边的后缀和和中点右边的前缀和组成。不妨把所有在中点右边的前缀和存起来，放到 vector 里并排序，然后枚举左端点确定后缀和。

由于刚才提到的性质，那么后缀和和前缀和凑成的区间和，要么已经小于 $P$，不再需要取模，要么最多只需要取模一次，也就是减掉一个 $P$。我们二分出第一个需要减去 $P$ 的位置，其左边的直接加起来，右边的加起来，然后减去右边的数量个 $P$。

复杂度 $O(n\log^2n)$。

p.s. 序列分治写起来比树状数组顺手，因此抢了个自己榜上首 A。整活成功。

submission

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

SD-S00524

这位选手，开场 9min，T1 便过了。很好啊！非常好的开局。

快看！这位选手，把 T2 秒了！我去，他大样例挂了！我去，他上厕所了！我去，他上完厕所，冷静思考的结果是写了一个分数类！我去，他写完了分数类，开始调式子了！我去，他大样例过了！我去，怎么已经五点了！我去，不着急，200pts 稳稳一等了。我们接着看 T3。

T3 20pts，很一眼啊！先上个厕所。T3，50pts，很简单啊！先吃个士力架，好吃！我去，大样例调出来过了！我靠，怎么拍挂了！我靠，初值错了！我草，拍过了！拍过了！两千组！这玩意儿好像很好优化，但是不管了！没什么时间了！快写 T4！

T4，先吃个士力架。诶我草真好吃。这是什么鬼题，我去，他怎么连 12pts 暴搜都不会？？我去，他把性质 A 切了！我草，怎么已经六点十五了？？？不急，检查一下。嗯，很没问题啊！继续吃士力架，好吃。

出场！哎呀我去，258，虽然不高，这不是稳稳的一等吗！蓝勾勾有了！

奥，T2 没 #include <vector>，爆零了！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-06 20:38:49

candies

较小值和较大值，可以看成独立。因为两个极值相等后，就再也不会变化了。那么，我们考虑二分出这 $K$ 次操作能让较小的数全增至 $L$，较大的数减至 $R$。$L\le R$ 时，答案即 $R - L$；否则，只有整个序列的总和是 $n$ 的倍数时极差为零，否则为一。

复杂度 $O(n\log V)$

rcomb

先考虑 $80$ 分的部分分。设 $f(n, i)$ 表示还剩 $n$ 张试卷，第 $i$ 张试卷的期望贡献次数。

那么有转移

$$ \begin{aligned} & f(n, 1) = \frac 1 {n-1} + f(n-1,1) \ & f(n, n) = \frac 1 {n-1} + f(n - 1, n - 1) \ & f(n, i) = \frac 2 {n-1} + \frac{i-1}{n-1} f(n-1,i-1) + \frac{n-i}{n-1} f(n-1,i) \end{aligned} $$

这个复杂度是平方的，能通过 $80$ 分。

对于这个部分分，还有一种思考方向，是设 $f(i, j)$ 表示合并完 $[i, j]$ 区间的期望代价。那么 $$f(i, j) = \sum\limits_{k=i}^j a_k + \frac{1}{j-i} \sum\limits_{k=i}^{j-1} f(i, k) + f(k + 1, j)$$

利用前缀和优化，也可以做到平方。

对于 $100$ 分的数据，考虑拆贡献。每个数到答案的贡献，是上面这个式子转移中的第一个 $\sum$。我们需要知道每个数被包含在了长度为多少的区间。

第 $k$ 个数对答案的贡献，可以考虑它往左边合并的概率。当左边有 $k - 1$ 个数时，有 $k - 1$ 种合并的可能，合并到它的概率是 $\dfrac 1 {k-1}$。右边同理，合并到它的概率是 $\dfrac 1 {n-k}$。当左右操作了一轮后，合并到它的概率增加到 $\dfrac 1 {k-2}$。我们对这个求和，就可以了。

最终的复杂度是 $O(n)$。

game

考虑一个暴力。不妨令 $x_1$ 属于 $A$，我们枚举它和哪个 $y$ 对应，就知道 $A$ 的命令。然后去掉所有可以满足 $A$ 命令的人，看看剩下的人是不是合法。这个可以做到 $O(nV)$。

然后利用 bitset 压位优化。复杂度 $O(\dfrac {nV} w)$

p.s. 这玩意儿假了

tree

我们发现用传统的 dfn 序似乎很难做这个东西。因此考虑相对不常用的欧拉序。

欧拉序上一段区间，是树上的一段路径。同时，两个端点的 LCA，就是这段路径上深度最小的点。在此题里，我们可以维护每个点到根的路径长度。那么由于边权非负，LCA 就是到根最近的那个点。

然后，操作一可以转化为子树的修改，因为修改这条边会让子树内到根的路径加上边权增量。

操作二就是查询 $u \in [s_x, e_x]$ 和 $v \in [s_y, e_y]$ 的 $dis_u + dis_v - 2dis_{c}$ 的最大值，其中 $c$ 是 $u, v$ 的 LCA。由刚才的讨论，我们知道 $c$ 就是 $u, v$ 欧拉序区间内的 $\rgmin dis$。

然后考虑操作三。注意到一个性质，即我们只会取两个端点之一。可以考虑如果不取到端点，调整到其中一个端点，路径长度不减。因此，我们就转化为子树到某个点的最远距离。这和操作二可以用相同的方法。

这个东西看起来还是有点吓人。令 $l, m, r$ 分别代表 $dis_u, dis_c, dis_v$，那么我们用线段树维护区间内 $l, m, r, l + m, m + r, l + m + r$ 的最值。这个是经典的。

然后我们考虑 $[s_x, e_x]$ 和 $[s_y, e_y]$ 的交集情况，讨论 $m$ 在左边还是右边即可。复杂度 $O(n\log n)$。

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

我们设 $f(x, y, S)$ 表示当前在 $(x, y)$，包含了的宝藏是 $S$，最少的移动步数。那么答案是 $\max val_S - f(x, y, S)$。

考虑转移。前两维的转移是简单的。由于转移顺序不确定，可以最短路。后面的 $S$ 怎么动态维护？

计算几何中的射线法，可以用来判断某个点是否在某个多边形中。具体的方法是：从这个点做一条直线，看其经过这个多边形的多少条边。如果经过奇数条即是在内，否则在外。我们可以沿用相同的方法，每次转移时从每个宝藏平行向右做一条直线，看是否和新扩展出的点交。若交了，则其在 $S$ 中取异或。

这样用最短路转移即可。