令 $q=\Theta(n)$。 考虑连通块数量等于点数减去边数。 点数是好算的。对于边数，将 $(n-1)$ 个二元组 $(a_i,a_{i+1})$ 视为点，实际上就是求 2-side 矩形点数。如果你和我一样糖糖的，直接使用树套树（时空均为 $\Theta(n\log ^2 n)$）或者 CDQ 分治（$\The…

直接大力代数推导。 $$ \begin{aligned} &[x^ay^bz^c] \left(x+x^{-1}+y+y^{-1}+z+z^{-1}\right)^n \\ =&[x^ay^bz^c] \left((x+y)(1+1/xy)+(z+z^{-1})\right)^n \\ =& [x^ay^bz^c] \…

$v$ 的值的个数只有 $1$ 怎么做？ 如果只有一个大小为 $a$ 的矩形，那么矩形内部的值域为 $[1,v]$，而且必须至少有一个 $v$，那么就是 $v^{a}-(v-1)^a$。 如果有两个大小为 $a,b$ 的矩形，如果无交的话方案数显然为 $v^{a+b}-(v-1)^av^b-v^a(v-1)^b+(v-…

看上去相当违反信息论，怎么办。 建出 Cartesian 树，区间最值的位置显然等于 $\operatorname{lca}(l,r)$。 发现建 Cartesian 树的过程中我们只关心每个节点入栈前，栈顶被 pop 了多少次，于是用 $\texttt{0}$ 表示 pop，$\texttt{1}$ 表示 push…

在讨论《关于题目配置》回复：

@[bulijoijoidibuliduo](luogu://user/169574) @[Graygoo](luogu://user/535714) SPJ 修好了，感谢反馈。

拆位是平凡的。接下来只需要考虑 $01$ 序列上的问题。 显然 $c_i=a_i\oplus b_i$ 这个序列的循环节长度为 $\operatorname{lcm}(n,m)$。对于长度为 $\operatorname{lcm}(n,m)$ 的整段是不难拆贡献后计算的，接下来只需要考虑长度 $\lt \operato…

和 Madoka 酱 duel 到的题。然后是线性的只用到哈希的做法。 首先判掉平凡的无解情况。 然后，考虑将字符串分为如下的三段： $$\operatorname{reverse}(t)=[1,i],[j,n],[j-1,i+1]$$ $$s=[1,i],[i+1,j-1],[j,n]$$ 枚举一下 $i$。我们要找…

## A 无脑的做法是 $\Theta(n|\Sigma|)$ 枚举 $\Theta(n)$ check，总复杂度 $\Theta(n^2|\Sigma|)$。 ## B 关键的性质是：原图中连通块数量 $\le 1$。 然后找到一个合法的形状判定一下即可。 ## C C>D。 考虑初始时全部设置成左括号。这样可能需要…

在讨论《关于本题分值》回复：

@[lhy2303](luogu://user/203093) 收到，下次传题的时候统一改

在讨论《样例有误》回复：

@[xbqlht21](luogu://user/457794) fixed

还是数据结构低手。 分别考虑每种颜色，不妨设颜色 $x$ 出现了 $c$ 次，那么可以刻画出 $\Theta(ck)$ 个区间：区间集 $S_{x,i}$ 表示 $\forall [l,r]\in S_{x,i}$，都有 $\operatorname{cnt}_x(l,r)=i$。把所有 $S_{x,i}$ 并起来得到…

## A 不妨设 $|s|\lt |t|$。 首先答案上界显然为 $|s|+|t|$。如果它们有长度为 $i$ 的公共前缀，则答案可以减少 $i-1$。时间复杂度 $\Theta(\min(|s|,|t|)^2)$。 ## B 打表发现，$C^*(n,m)=2^{[n\neq m]\cdot m}$。快速幂即可。 时间…

## A 考虑到一定有解，令 $x=\lceil K/\sqrt 2\rceil$，构造 $(x,0),(0,x)$ 和 $(0,0),(x,x)$ 即可。 ## B 显然有可二分性，考虑二分 $k$； 令 $f(i,0/1)=0/1$ 为当前考虑到 $1\sim i$，且是否多涂了一个是否合法。 然后直接转移即可。时…

### A 按题意模拟，加到不能再加为止，最后输出差值即可。时间复杂度 $\Theta(n\log n)$。 ### B 出现次数 $=1$ 的颜色收益为 $2$。双方都会去抢这样的颜色，可以按题意模拟。 最后，剩下若干出现次数 $\gt 1$ 的颜色。这样的颜色对双方的贡献都是 $1$（可以通过模仿操作之类的方式实现…

场切了。 考虑“不合法不优”。随便钦定一个点作为最大值计入答案。如果它实际上并不是最大的，那么一定不优，会在取 $\max$ 的时候被排除掉。对最小值同理。 那么不难设计一个 $\Theta(n^2\cdot 3^k)$ 的 DP：令 $f(i,j,s)$ 为当前考虑 $1\sim i$，选了 $j$ 个点，其中我们计…

在讨论《请求撤下题解》回复：

@[I_am_Accepted](/user/101868) 题解已经全部被撤了（）

在讨论《关于本题数据》回复：

@[Union_of_Britain](/user/342076) 现在应该好了。

在讨论《如何更好地运用 QOJ 进行学习》回复：

@[DengDuck](/user/501947) 贴贴。感觉 LOJ UOJ 都是不错的。

在讨论《非OI数学题求教》回复：

@[TankYu](/user/408071) 考虑套用 $k=1$ 时发散的证明过程即可类似地证明出收敛。

在讨论《请求撤下题解》回复：

@[BrotherCall](/user/376265) @[N_z_](/user/320087)

[link](https://www.luogu.com.cn/article/rcdgxt1n)。格式有误+怀疑抄袭。

在讨论《翻译有误》回复：

@[MatrixGroup](/user/483824) 矩阵群姐姐贴贴ww