plan R 1 [随缘更新]

[★] CF704B Ant Man

[★] [JOI Open 2016] 摩天大楼

两个连续段 dp 裸题。

[★★★] 【MX-S6-T4】「KDOI-11」彩灯晚会（#1, #2）

这个 $cnt^2$ 直接套组合意义，变成了选两条链的方案数，如果两条点交点个数为 $c$，那么贡献为 $k^{n-2l+c+1}$。直接暴力 dp 可以做到 $\mathcal O(n^4l)$ 的，恰好不好算，转钦定再二项式反演一下。令 $f_{u,p,q,c}$ 表示当前钦定交点在 $u$，两条链的长度分别为 $p,q$，目前钦定了 $c$ 个点。每次转移枚举下一个点和两条链增加的长度，令 $h_{u,v,p}$ 表示从 $u$ 走到 $v$ 路径长度为 $p$ 的路径数量（预处理 $\mathcal O(n^3l)$，不是瓶颈），则有：

$$f_{u,p,q,c}\cdot h_{u,v,x}\cdot h_{u,v,y}\rightarrow f_{v,p+x,q+y,c+1}$$

时间复杂度 $\mathcal O(n^2l^5)$，观察到 $p,q$ 两位独立，可以分步转移，砍了一个 $l$。看似无法优化了，试着列出最后的统计式子，令 $F_i$ 表示钦定了 $i$ 个点重合的路径对数，$G_i$ 代表恰好有 $i$ 个点重合的路径对数，那么有：

$$G_i=\sum\limits_{j=i}^l(-1)^{j-i}\dbinom{j}{i}F_j\\ ans=\sum\limits_{i=0}^lk^{n-2l+i+1}G_i$$

难想到的发现反演的这个形式可以和下面的 $ans$ 凑在一起：

$$\begin {aligned} ans&=\sum\limits_{i=0}^lk^{n-2l+i+1}\sum\limits_{j=i}^l(-1)^{j-i}\dbinom{j}{i}F_j\\ &=k^{n-2l+1}\sum\limits_{j=0}^jF_j\sum\limits_{i=0}^j\dbinom{j}{i}(-1)^{j-i}k^i\\ &=k^{n-2l+1}\sum\limits_{j=0}^jF_j(k-1)^j \end {aligned}$$

于是把 $k-1$ 均摊到转移里面，就可以少记一维 $c$，时间复杂度 $\mathcal O(n^2l^3+n^3l)$。

[★]【MX-X6-T6】機械生命体（#3）

如果从低到高位建树，那么查询操作就可以直接跳。另一个相当于子树合并和子树加，前者直接类似线段树合并做均摊是对的，后者就是子树 +1 的拓展：每个点打上 $+tg$ 的标签，如果下放的 $tg$ 是奇数，那么交换左右儿子，并且分别放 $tg=\dfrac{v+1}{2},\dfrac{v-1}{2}$；否则直接放 $tg=\dfrac{v}{2}$。

注意合并子树的时候要 pushdown，因为能合并前提是作用在上面的标记一样，因为这个标记不具有可并性。

[★★★] [2021 集训队互测] 细菌（#4）

观察到每一维是独立的，所以求出三维的三个数组最后卷起来就好。现在每个子问题形如有一个 $[1,n]$ 的数轴，初始在 $x$，每次可以向左 / 向右移动一个单位，求在 $1\sim d$ 每个时刻可行的路径数，这里有一个显然的 $\mathcal O(nd)$ 做法。

同时发现向左向右可以刻画到网格图上行走，问题转化成了反射容斥（反射容斥和普通 dp 平衡是比较常见的，具体见模拟赛 2025.2.md 的一题），但是我们需要求的是 $d$ 条斜线上的点的每条的和，直接做显然不行。

突破点也是我们只关心每条斜线上的和而不是具体值。把反射容斥的和打开来，就如上图，变成了若干个小连续段带上一个容斥系数。之注意到两条反射线之间的点集合差的并不多，具体是一个 $\sum\limits_{i=l}^r\dbinom{u}{i}$，每次对 $l,r,u$ 进行 $0\sim 1$ 的修改，这个大家都会维护。总段数是 $\mathcal O(\dfrac{d^2}{n})$ 的，和上面做法平衡一下就是 $\mathcal O(n\sqrt n)$ 的。

[★] [集训队作业2018] 复读机

$d=1$ 为 $k^n$。$d=2$，每个复读机的 EGF 为 $\dfrac{e^x+e^{-x}}{2}$，把最终式子暴力二项式定理展开：

$$\begin{aligned} ans&=\left[\dfrac{x^n}{n!}\right]\left(\dfrac{e^x+e^{-x}}{2}\right)^k\\ &=\dfrac{1}{2^k}\left[\dfrac{x^n}{n!}\right]\sum\limits_{i=0}^k\dbinom{k}{i}e^{ix}e^{-(k-i)x}\\ &=\dfrac{1}{2^k}\sum\limits_{i=0}^k\dbinom{k}{i}(2i-k)^n\\ \end{aligned}$$

$d=3$ 对系数单位根反演一下就可以一样做了。

$$\begin{aligned} ans&=\left[\dfrac{x^n}{n!}\right]\left(\sum\limits_{i\ge 0}[3|i]\dfrac{x^i}{i!}\right)^k\\ &=\dfrac{1}{3^k}\left[\dfrac{x^n}{n!}\right]\left(\sum\limits_{j=0}^2e^{\omega^{j}_3x}\right)^k\\ &=\dfrac{1}{3^k}\sum\limits_{i=0}^k\sum\limits_{j=0}^{k-i}\dbinom{k}{i,j,k-i-j}(i+j\omega_n^1+(k-i-j)\omega_n^2)^n\\ \end{aligned}$$

因为 $3\mid\varphi(P)$，所以直接把 $\mathcal w_3$​ 值求出来就能算。

[★★] [2021 集训队互测] 愚蠢的在线法官（#5,#5ex1,#5ex2）

• sol1 [★★]

首先观察到一旦 $A$ 中存在相同元素，那么行列式为 $0$。但仍然不是很好算，先将 $A$ 中点按照 dfn 排序，容易发现行列式不会发生变化。

试着根据行列式定义把贡献拆开，相当于 $A$ 中点两两互相匹配。考虑对于一个子树 $sub_u$，若存在 $x,y\in sub_u$ 且 $p_x,p_y\in U\backslash sub_u\cup\{u\}$，那么因为交换之后逆序对奇偶性会发生改变，所以贡献为 $0$。于是每棵子树只会向外匹配一个点。令 $f_{u,0/1}$ 表示 $u$ 子树有没有向外匹配的点，每次转移可以把一个匹配连成链，或者连成环。

还有一个问题，我们是按顺序转移的，如果像上图一样匹配有交怎么办。但是同样可以分析，如果有交那么交换之后还是抵消的，所以不用计算。

---

• sol2 [★★★]

以下是出题人的方法，还是比较有趣的。

先引入一个 $\gcd$ 方阵行列式的东西：求 $A_{i,j}=\gcd(i,j)$ 的行列式。因为 $\gcd(x,y)=\max\limits_t[t\mid x][t\mid y]t$，同时又跟据 $\pmb 1*\varphi=\text{id}$，构造 $B_{i,j}=[j\mid i]\varphi(j)$，$C_{i,j}=[i\mid j]$，那么 $A=BC$。因为 $B,C$ 均为方阵，那么 $\det A=\det B\cdot \det C$，而 $B,C$ 均为三角矩阵，所以 $\det A=\prod\limits_{i=1}^n\varphi(i)$。

同理我们也可以套用到这题上，因为 LCA 和 $\gcd$ 非常相似，都可以用两条限制刻画，这里只要树上差分一下，并把 $B,C$ 的限制改成祖先关系限制就好了 。当给定的 $S$ 集合（原题是 $A$，以防重名这里改一下）刚好是 $n$ 的排列，那因为是方阵所以可以直接套上面的做法。如果 $|S|< n$，考虑 Cauchy-Binet 公式，$\det A=\sum\limits_{T\subseteq\{1,2,\cdots,n\}, |T|=|S|}\det A_T\cdot \det B_T$。相当于选一个点集，每个 $S$ 中的点匹配一个 $T$ 中的点（一一对应），且被匹配的是匹配的祖先，然后贡献是被匹配点的权值之和（带上 $\text{sgn}$）；最后还要乘上这种方案的数量（带上 $\text{sgn}$）.

太丑了，这里要想到如果每个 $S$ 中的点都贪心匹配最近祖先，有贡献当且仅当没有两个 $S$ 的点匹配了一个祖先（有的话说明可以交换，没有的话和任意一个更浅的祖先匹配都会导致有至少一个点无法匹配），而且 $B,C$ 的 $\text{sgn}$ 抵消了，所以这个可以直接统计，树形 dp。

---

• sol3 [★]

偷来的 unintended solution。

还是先排序，和上面类似进行树上差分一下，令新的权值为 $a'$，枚举每个 $u$，可以贡献到 $A$ 集合中所有在 $u$ 子树中的点。方阵加求行列式，诶呀那这可太熟了，二维差分之后广义串并联秒了（注意到 dfn 区间不交，所以是广义串并联图）。

---

• sol4 [★★★★]

还有一个树形结构上行列式合并的做法，也是挺牛的，思维难度有点高。

dfn 排序。然后每次相当于合并两个儿子子树的矩阵 $A,B$（令当前遍历节点的值为 $v$），类似于 $\det\begin{bmatrix}A&v\\v&B\end{bmatrix}$，这是不好求的，但是如果 $x=0$ 就是非常好求的，所以我们试图把这东西消掉。

先把整个矩阵全部 $-x$，得到 $\begin{bmatrix}A_v&0\\0&B_v\end{bmatrix}$（令 $A_v$ 表示将 $A$ 矩阵中的每个元素都 $-v$ 的矩阵），我们只要求出这个的 $\det$ 并和原来的 $\det$ 建立关系，就可以求出来。先展开这个矩阵的 $\det$：

$$\begin{aligned} &\sum\limits_{p}\text{sgn}(p)\sum\limits_{i=1}^n(A_{i,p_i}-v)\\ =&\sum\limits_{p}\text{sgn}(p)\sum\limits_{S\subseteq\{1,2,\cdots,n\}}(-t)^{|S|}\prod\limits_{i\in U\backslash S}A_{i,P-i}\\ \end{aligned}$$

注意到当 $|S|\ge 2$ 的时候，交换 $S$ 中任意两个点的 $p$ 都可以抵消，所以只要考虑 $|S|\le 1$ 的情况，那么令 $\det 'A=\sum\limits_{p}\text{sgn}(p)\sum\limits_{j=1}^n\prod\limits_{i=1}^n[i\not= j]A_{i,p_i}$， 就有 $\det A_v=\det A-v\det'A$，于是我们给 $\det A_v$ 和 $\det A$ 建立了联系。可以开始维护了，令 $f_u$ 表示 $u$ 子树的矩阵的 $\det$，$g_u$ 表示 $u$ 子树的矩阵的 $\det'$；考虑如果在合并 $x,y$ 两个节点到状态 $z$ 的情况（$x$ 子树矩阵为 $A$，$y$ 子树矩阵为 $B$）：

$$\def\mat#1#2#3#4{\begin{bmatrix}#1&#2\\#3&#4\end{bmatrix}} \begin{aligned} g_z=\det'\mat{A}{v}{v}{B}&=\det'\mat{A_v}{0}{0}{B_v}\\ &=\det A_v\det'B+\det'A\det B_v\\ &=g_y(f_x-vg_x)+g_x(f_y-vg_y)\\ \\ f_z=\det\mat{A}{v}{v}{B}&=\det\mat{A_v}{0}{0}{B_v}+v\det' \mat{A}{v}{v}{B}\\\ &=\det A_v\det B_v+vg_z\\ &=(f_x-vg_x)(f_y-vg_y)+vg_z \end{aligned}$$

以上化简用到了 $\det' A=\det' A_t$，这个容易初等行变换证明，于是可以直接合并了。不得不说这个合并的转移要非常好的利用推出来的所有式子才能化简的很简单，何况推出性质本身也是比较难的。

[★★] 『STA - R3』大豆

尝试直接写出暴力的式子：令 $F_k$ 表示原序列「大豆化」$k$ 次的新序列，那么有 $F_k(m)=F_{k-1}(m)-\sum\limits_{i=2}^mF_k(\dfrac{m}{i})$，直接递归显然是 $\mathcal O(m^{\frac{3}{4}})$，因为形式长得太像杜教筛了，所以考虑预处理 $\mathcal O(n^{\frac{2}{3}})$ 的答案。容易发现上面的东西可以 Dirichlet 前缀和，具体就是差分一下，然后就可以过了。注意精细卡常一下，具体就是尽量减少取模和除法次数。

[★] [YDRG#001] E. 来自璃月的生日礼物

和为 $n$，转化成 $n-1$ 个空插 $m-1$ 个板，编号对应的板 A 要在 B 前面。这个是个括号序列，不过可能 A，B 有重叠的板，但是这个不影响匹配关系，直接枚举重叠个数，剩下的卡特兰。

[★] [MtOI2018] 情侣？给我烧了！（加强版）

直接容斥是不好化简的（虽然题解里有人化出来了，但是我不管！），于是不容斥，直接求出恰好的方案，令 $D_n$ 代表 $n$ 对情侣错排的方案数，答案就是 $\dbinom{n}{k}^2k!2^kD_{n-k}$。可以通过恒等式 $\sum\limits_{k}\dbinom{n}{k}^2k!2^kD_{n-k}=(2n)!$ 导出一个 GF 的做法，但是都错排了，为什么不递推！

两种情况，第一种第 $n$ 对情侣的一个和前面一个人交换，系数为 $\dfrac{8n(n-1)}{2}$；否则选第 $n$ 和一对前面匹配的情侣构成一个新的错排环，系数为 $\dfrac{16n(n-1)\cdot (n-1)}{2}$​。

[★★] [WC2016] 论战捆竹竿（#6）

首先容易发现令 border 集合为 $B$，每次可以添加长度集合应该是 $B'=\{n-x\mid x\in B\}$。根据 border 理论，发现 $B'$ 可以被拆成 $\mathcal O(\log n)$ 个等差数列，于是尝试按照等差数列的顺序处理这个东西。

假如当前在处理 $a+\ell b(0\le \ell <m)$ 的等差数列，观察到其实这是个同余最短路的模型，但是这里有取值依赖两个变量，并不能分开处理。但是 $b$ 的可行个数是依赖 $a$ 的，所以用 $a$ 当模数就可以去掉一维。现在在 $\bmod a$ 意义下每个点只会有 $+d\bmod a$ 的边，容易发现形成了 $\gcd(a,b)$ 个连通块，每个单独处理。如果每个连通块按照每次 $+d$ 的顺序排列成一个环，每个点连出去的边就是后面 $m-1$ 个点。所以这个边的的更新一定不会跨过环最小值的点，把这些边断开就可以序列上单调队列转移了。

那么在每两个等差数列的之间怎么切换呢？这里如果从 $\bmod x$ 到 $\bmod y$，损失的信息只有 $f_i$ 能到达所有的 $kx+f_i$。所以先把 $f_i$ 更新到 $g_{f_i\bmod y}$ 上，然后再跑一遍只有 $+x$ 的同余最短路就好了，做法类似，把每个环提出来扫两遍就好。

[★★★] [CTSC2006] 歌唱王国（#18）

题解里有一个失配树上 dp 的做法，没仔细看，但是思路应该是自然一点的（？）但是还是复读一下第一篇题解的做法，比较牛。

假设有一个赌场，每一时刻都会有一个赌徒带着一块钱进赌场，同时赌场里的每个人都会押注下一个时刻添加的元素：假设目前一个人猜测下一个元素为 $a_i$，初始 $i=1$，如果猜对了，钱翻到原来的 $n$ 倍，否则输光，容易发现每个人的期望钱数是不变的，所以这是一个公平赌博。

如果在某一时刻突然匹配到了待匹配的字符串 $s$，令其为时刻 $i$，那么对于所有 $s$ 的 border 长度 $\ell\in B_s$，在时刻 $t-\ell+1$ 进场的赌徒最终拥有 $n^{\ell}$ 的钱，其余赌徒没有钱，所以终止状态赌场的总钱数就是 $\sum\limits_{\ell \in B_s}n^{\ell}$。同时因为每一时刻赌场总期望钱数增加一，所以上面的式子就是期望停止时间。

[★] [NOI2016] 优秀的拆分（#7）

AABB 的形式可以只统计 AA 的串数，然后在中间统计答案。直接做是 $\mathcal O(n^2)$ 的。具体想一下，枚举串长之后 $i$，如果每 $i$ 个标记一个杆子，那么 AA 一定会跨越两个杆子，可以直接哈希统计，现在就是调和级数的了。

[★] QOJ6624 String Problem

题目等价于前缀求最小表示法，把字符串值翻一下求个 Lyndon，稍微改一下循环节分配的细节就好了。

[★] CF1085G Beautiful Matrix

枚举第一个不同的元素，整行的直接错位排列，然后发现要求一个 $f_{i,j}$ 表示两个集合 $A,B$，其中 $|A\cap B|=i$ 且 $|A|=|B|=j$，然后把 $A,B$ 中的元素两两错位匹配的方案数，这个和错位排列一样递推就好了。

[★★] [ROI 2016 Day2] 二指禅（#4）

暴力考虑 $f_i$ 表示前 $i$ 个字符需要的最小代价，转移枚举每个串匹配 lcp / lcs，然后做一个 push 或者 pull 的转移。按照 $\sqrt L$ 根号分治，$\le \sqrt L$ 的串直接插到 Trie 里面暴力匹配；$>\sqrt L$ 的串直接枚举，Z-function 求出 lcp / lcs 之后发现是一个区查单修 $\mathcal O(n\sqrt n)-\mathcal O(n)$ 和单查区修 $\mathcal O(n)-\mathcal O(n\sqrt n)$ 的东西。这题特殊在于修改的只会是后面的值，所以可以直接把区间当成前缀操作，平衡一下就是 $\mathcal O(n\sqrt n)$ 的。

[★] CF464E The Classic Problem

[★] P8860 动态图连通性

两个都是主席树维护最短路，注意一下 pushdown 的时候还要新建点，不能直接 push 到原来的点上。

[★] [APIO2016] 烟火表演

呃呃，忘了咋做的了，粘一个以前写的总结。

---

首先考虑将每个节点的函数值包含其父边，方便处理。

然后令父边权值为 $w$，这个函数转移类似于 $f'(x)=\min\limits_{0\le t}f(x-t)+|w-t|$，定义域的限制使转移比较复杂，根据分讨之后发现凸函数的变化如下所示：本质就是先保留 $\mathcal R$ 的一个元素，之后并将 $\ell,r$ 加 $w$，使用左偏树即可。

[★] [CEOI 2019] Dynamic Diameter（#8）

把原树的欧拉序求出来，令 $L_u,R_u$ 表示 $u$ 在欧拉序 $D$ 中最大 / 最小的下标，那么有答案为 $\max\limits_{L_u\le R_v}\left(d_u+d_v-2\min\limits_{L_u\le i\le R_v}d_{D_i}\right)$，观察到里面的 $\min$ 和外面的 $L,R$ 是可以放缩掉的，就变成了维护式子 $\sum\limits_{u\le i\le v}d_u+d_v-2d_i$​，线段树维护。

[★] [AHOI2022] 钥匙

直接枚举每个钥匙匹配的宝箱，发现如果一条路径上按照栈的形式匹配，一对宝箱和钥匙能不能匹配是确定的。所以直接处理出每对路径，然后对询问做贡献，在 dfn 上对应的是两个区间，那二维数点一下就好了。这里对于每个颜色建虚树，然后以每个钥匙为根遍历会处理方便一点。

[★★] [ZJOI2019] 语言（#10）

有一个比较直接的 $\mathcal O(n\log^3n)$ 做法，可能是能过的，但换一种。考虑从什么角度去统计路径的数量，如果从 LCA 去统计的话并不方便，点分也可以做，但是并不是显然的。如果我固定了一个可行路径的端点，另一个可行端点的集合一定形成一个连通块。说明了其实可以用更优秀的方式来刻画一个可行端点的集合。

假如我们在统计 $u$ 为端点的路径数，那么令 $S=\{(x,y)\mid u \in \mathcal P(x,y)\}$，则 $S$ 构成的虚树大小就是所有可行的 $v$，这个可以 dfn 排序之后用一个众所周知的公式解决。现在需要的是往一个路径上的所有点的集合 $S$ 内加点，同时最后一起询问每个点集的虚树大小。离线且可合并的结构，直接上线段树合并可以做到 $\mathcal O(n\log n)$。

[★] [COCI 2012/2013 #6] BAKTERIJE

循环节，exgcd。

[★] 小 A 与两位神仙

首先 $P$ 必定有原根 $g$，令 $a = \text{ind}_gx, b = \text{ind}_gy$，那么等价于存在一个 $k$ 使得 $ka\equiv b\pmod{\varphi(P)}$，根据裴蜀定理可以得到方程有解当且仅当 $\gcd(a,\varphi(P))\mid b$，但是 $10^{18}$ 的离散对数并不好求。

又因为有 $\delta_Pa=\dfrac{\varphi(p)}{\gcd(\varphi(p), \text{ind}_ga)}$，所以题目条件等价于 $\delta_Py\mid \delta_Px$，形象一点就是在一个长 $\varphi(P)$ 的指数环上，$x$ 能到达的点个数必须是 $y$​ 的倍数，显然是充要的，这个可以 Pollard-Rho 之后暴力求阶。

[★] [WC2020] 猜数游戏

和上面那个结论相同，统计答案的时候分开讨论 $\gcd(a_i,P)>1$ 和 $\gcd(a_i,P)=1$ 的。前者考虑枚举每个数 $x$，如果 $x$ 能做贡献，最后集合中应该不存在 $y$ 使得 $\delta_Px\mid \delta_Py$，如果相同的数我们订一个顺序就好，这个可以用 Dirchlet 前缀和做到更优。后者因为暴力跳 $\log P$ 次就变成 $0$ 了，所以直接做。

[★★] CF1290E Cartesian Tree（#11，#12）

笛卡尔树上子树大小代表其管辖区间的大小，所以可以把区间左右端点拆出来单独算。现在只要解决往序列中插入一个数，求所有数的后继下标之和。仔细分析一下，我们需要区间取 $\min$，单点修改，区间加，吉司机 $\mathcal O(n\log^2 n)$。

[★] [HNOI2019] 序列

首先正常 $L_2$ 的链偏序保序回归有两种做法：直接整体二分+网络流，或者单调栈维护。这里肯定使用第二种，把询问离线下来，顺序扫描，变成了合并两个单调栈，两边都有单调性，二分套二分就是 $\mathcal O(n\log^2 n)$ 的。

[★★★] [2021 集训队互测] 抽奖机

拉一次杆等价于三进制异或卷积一次，于是可以先把原来的形式幂级数 FWT 一次，$k$ 次方，iFWT 回来。观察发现如果两个状态 $0,1,2$ 的个数都是相同的，那么系数也是相同的。所以改写一下：令 $f_{x,y}$ 表示有 $n-x-y$ 个 $0$，$x$ 个 $1$ 和 $y$ 个 $2$ 的系数，那么可以列出一个二元生成函数：

$$G_{a,b}(x,y)=(1+x+y)^{n-a-b}(1+\omega_3^1x+\omega_3^2y)^a(1+\omega_3^2x+\omega_3^1y)^b$$

那么原来的 $f_{a,b}$ 对新的 $f_{p,q}$ 的贡献就是 $\dfrac{\binom{n}{a,b}}{\binom{n}{x,y}}[x^py^q]G_{a,b}(x,y)$。前面组合的系数因为有 $\dbinom{n}{a,b}$ 个数，每个数要贡献一次，最后 $f$ 代表一个个体，所以要把 $\dbinom{n}{x,y}$ 除掉。这样暴力做是 $\mathcal O(n^5)$ 的，实际上因为递推式 $G_{a,b}(x,y)=\dfrac{1+\omega_3^2x+\omega_3^1y}{1+x+y}G_{a,b-1}(x,y)$ 可以把系数递推出来，多项式除法考虑把乘法的操作倒过来就好了，时间复杂度 $\mathcal O(n^4)$。

[★★] [Code+#7] 同余方程

首先因为 $\mu(p)\not=0$，所以可以 CRT 合并答案，每个质数分别做乘起来就好。容易发现答案式子是 $\sum\limits_{i=0}^{p-1}\left(\left(\dfrac{i}{p}\right)+1\right)\left(\left(\dfrac{x-i}{i}\right)+1\right)$。这个拆来了不好算的项只剩下了 $\sum\limits_{i=0}^{p-1}\left(\dfrac{i}{p}\right)\left(\dfrac{x-i}{p}\right)$，根据其本身的完全积性，并且除一个 $i^2$ 不影响其二次剩余性，现在变成了 $\sum\limits_{i=1}^{p-1}\left(\dfrac{\frac{x}{i}-1}{p}\right)$。如果 $x=0$，那么直接算；否则 $\dfrac{x}{i}$ 取遍了所有 $[1,p-1]$ 的数，又因为 $\sum\limits_{i=0}^{p-1}\left(\dfrac{i}{p}\right)=0$，这个式子就是 $\left(\dfrac{-1}{p}\right)$，时间复杂度 $\mathcal O(T\sqrt n)$。

[★] QOJ5116 Contests

把题目抽象成一张图，然后就能想到倍增了。注意倍增只能倍增路径，而不能倍增路径上的点数，而且我们不关心当前在数的哪一条链上，这样就可以砍掉一个 $m$ 做到 $\mathcal O(m^2(n+q)\log n)$。

[★] QOJ9727 Barkley III

按位维护是没有前途的，发现直接放到线段树我们需要多维护一个按位与的信息就能合并了。

[★] QOJ2833 Hamilton

构造入门题，我怎么不会。我怎么不会。我怎么不会。我怎么不会。我怎么不会。我怎么不会。我怎么不会。我怎么不会。我怎么不会。

考虑增量构造。每次往整个环里面插入一个数 $i$，如果整个环是同色环那么随便放。否则找到分界点 $y$ 和前驱后继 $x,z$。如果 $C_{x,y}=C_{y,i}$ 那么插在 $y,z$ 中间，否则插在 $x,y$ 中间。

[★] [POI 2013] MUL-Multidrink

因为固定了起点和终点，直接构造是很难的。先提出 $1\sim n$ 的链，最后路径一定是依次经过这条链上的所有子树。尝试直接对这些子树和这条链 dp，令 $f_{u,0/1/2}$ 表示 $u$ 子树遍历的三种情况：

注意到第二种情况没有给箭头定向和标序，因为从哪边走都是一样的，决策完回溯构造就好。

[★★] [WC2018] 通道

首先对第一棵树边分治（或者点分治+合并果子），然后在第二棵树上建虚树，dfs 的时候枚举 LCA，现在还没有处理的有 $d_{1+2}(u)+d_{1+2}(v)+\text{dis}_3(u,v)$，把前面分离的权值看成 $\mathcal T_3$ 下面每个点连一条长度为 $d_{1+2}(u)$ 的边，这样就等价于求直径，在虚树上合并就好。时间复杂度 $\mathcal O(n\log^2 n)$，如果 $\mathcal O(n)$ 建虚树可以砍掉一个 $\log$​。

[★] QOJ6830 Just Some Bad Memory

分讨。一个比较好的结论是判断一棵树有没有偶环，可以找出一棵生成树：如果存在两个环相交，或者一条非树边构成的环本身就是偶环，那么就有偶环。第一个条件是因为对于两个相交的环 $(a,u,v),(b,u,v)$，可以产生一个额外的环 $(a,v,b,u)$，这三个里面必定有一个偶环。

[★★] QOJ6545 Connect the Dots

把整个序列围成一个环，容易发现是一个 $n$ 边形，所以连线的上界是 $2n-3$。相邻点的连线已经可以确定，只要管中间 $n-3$ 条弦能不能连。如果存在一个颜色只出现过了一次，那么用这个点和其他的全部连一遍；如果 $m=2$，发现不能连的时候序列形式是 $1212121\cdots$，这个时候弦的上界是 $\dfrac{n-3}{2}$。于是可以拓展到对于 $m>2$ 的情况：我们不断找出能连的点，其中距离为 $2$，并将中间的点删掉。直到有一个点只出现过一次的时候，就采用第二个策略，否则按照 $m=2$ 做。

[★★] QOJ6509 Not Another Range Query Problem（#12）

先把询问离线下来，并把整个删除的过程补全成一个类似 DAG 的东西：

我们扫描 $k$ 的时候，假设在处理 $[l,r]$，等价于找到最大的一个区间 $[l',r']$，使得 $[l',r']$ 所有边支配的最大区间 $\subseteq [l,r]$，例如第三层的红色区间对应支配的就是最上面标红的区间，这个可以差分。可以动态维护所有连续段，但是这样非常繁琐，实际上我们只要求出每个数被删除的时间就好了，线性扫一遍，然后二维偏序。

[★★] QOJ6640 Talk That Talk（#13）

以下简写 $g_i=\left(\dfrac{i}{p}\right)$。

先枚举 $i-j=d\le t$，可以用 $\dfrac{(g_i+1)(g_j+1)(g_k+1)}{8}-\dfrac{(g_i-1)(g_j-1)(g_k-1)}{8}$ 刻画答案，化简得到 $\dfrac{g_ig_j+g_ig_k+g_jg_k+1}{4}$。把三项分开求，因为是类似的先只讨论 $g_ig_j$ 一项。展开为 $\sum\limits_{i=1}^{p-1-2t}g_ig_{i+d}$，上指标看着很难受，而且我们倾向于求 $\mathcal O(t)$ 量级的东西，容斥成 $\sum\limits_{i=1}^{p-1}g_ig_{i+d}-\sum\limits_{i=p-2t}^{p-1}g_ig_{i+d}$。后面这个可以直接暴力枚举 $i$，算出可行的 $d$ 的范围，预处理前缀和 $\mathcal O(1)$ 算。前面这个把他展开来就是 $\sum\limits_{i=1}^{p-1}i^{\frac{p-1}{2}}(i+d)^{\frac{p-1}{2}}$。后面这个是关于 $i$ 的 $p-1$ 次多项式。其中 $1\sim p-2$ 次项，因为有 $\sum\limits_{i=1}^{p-1}i^{p-1}\equiv 0\pmod p$ ，所以只要算 $p-1$ 次项，因为 $g_i\in\{-1,0,1\}$，所以上面式子值为 $-1$（而非 $p-1$），那么就可以 $\mathcal O(\sum t\log p)$ 计算答案了。

[★] QOJ6508 This is not an Abnormal Team!

flow 功底非常不扎实哈！

肯定先让孤立点最少。如果直接按照匹配边跑一次 flow 的话，能保证最后 $\ge 2$ 大小的组数最大，所以只要在这个基础上尽量把没匹配的点匹配到已经匹配的里面就好了。但是可能两边都有没有匹配的点，这样很难建边。但是自己想想实际上不会有这种情况，否则可以继续增广。所以一个连通块只有一部点可能有没匹配的点，只要把另一部点再增加单位 $1$ 的流，这样匹配的就是 $3$ 叉的形式了。

[★] QOJ6631 Maximum Bitwise OR

令区间 $[l,r]$ 或值最高位为 $k$，那么最大值为 $2^{k+1}-1$，可以对区间任意一个 $\ge 2^k$ 的数，对 $k$ 这一位操作两次得到。说明操作次数只有 $0,1,2$，$0$ 是容易的，重点在于判断 $1,2$。令或值最低 / 最高为 $0$ 的位为 $x,y$，那么能操作的数必须满足 $[x,y)$ 位为 $0$，同时值要 $\ge 2^y$。可以存储 $\log V$ 棵线段树，第 $i$ 棵存每个数 $\ge i$ 位第一个 $1$ 的位置，这样区间查询第 $x$ 棵的极值是否 $\ge y$ 就好了。但是可能操作之后有一位只出现一次，但是损失了。这样的数只有 $\log V$ 个，拎出来单独判断，时间复杂度 $\mathcal O(n\log n\log V)$。

[★★★] CF1458F Range Diameter Sum（#14）

首先可以倍增预处理出所有 $f(l,r)$，可以 $\mathcal O(1)$ 求单个值。对 $l$ 扫描线，考虑求出所有 $r$ 端点对应的 $\Delta_{r}=f(l,r)-f(l,r-1)$ 变化值：

• 引理一：对于一个任意的 $l$，有 $\Delta_{r}\ge \Delta_{r+1}$。

如果 $\Delta_r=0$，那么 $\forall r<r',\Delta_{r'}=0$，这个是显然的，如果 $\Delta_r>0$，说明 $f(l,r)$ 的一个端点为 $r$。现在我们来反证这个东西：当 $\Delta_r<\Delta_{r+1}$ 的时候，$f(l,r+1)$ 的两个端点必然是 $l,r+1$。又因为根据直径的基本性质，可以得到 $f(l,r)$ 和 $f(l+1,r)$ 有一个共同端点，$f(l+1,r)$ 和 $f(l+1,r+1)$ 有一个共同端点，并且 $f(l+1,r+1)$ 和 $f(l,r+1)$ 有一个共同端点，于是我们列出一个端点表格：

$f$	$l$	$l+1$
$r$	$(l,r)$	$(r,y)$
$r+1$	$(l,x)$	$(x,y)$

观察到从 $l+1\rightarrow l$ 的时候把两条直径的一个端点 $y$ 都替换成了 $l$。但是这种情况下 $\Delta_r\ge \Delta_{r+1}$，所以证伪，原结论成立。

于是得到了 $\Delta$ 单调的性质，但是仍然不够。大胆猜测相同连续段级别不是很大（没有具体证明，感觉是假的，但是没卡），所以只要每次扫 $l$ 的时候把连续段二分出来就好了。令连续段的级别为 $L$，时间复杂度为 $\mathcal O((n+L)\log n)$。

[★★] LOJ6696 复读机 加强版 / [BJ United Round #3] 押韵（#15）

$k\in\{1,2,3\}$ 见「集训队作业2018」复读机，以下令新的 $n$ 为 $nd$。

对于 $d=4$，同 $d=3$，单位根反演完需要求 $\dfrac{1}{4^k}\left[\dfrac{x^n}{n!}\right]\left(\sum\limits_{i=0}^3e^{\omega_4^ix}\right)^k$。因为 $\omega_4^0=-\omega_4^2,\omega_4^1=-\omega_4^3$，所以可以简化成两个基。一种做法是看成坐标轴上行走，把 $x,y$ 搞独立了直接枚举终点。或者直接写出二元 GF：$F(x,y)=x+y+x^{-1}+y^{-1}$，需要求出 $G=F^k$ 的所有系数，类似短多项式求幂，两边对 $x$ 求偏导：

$$\begin{aligned} G&=F^k\\ \dfrac{\partial G}{\partial x}&=k\dfrac{\partial F}{\partial x}F^{k-1}\\ \dfrac{\partial G}{\partial x}F&=k\dfrac{\partial F}{\partial x}G \end{aligned}$$

尝试列出两边 $x^ny^m$ 的系数（弃用了题目中的 $n$）：

$$\begin{aligned} nG_{n,m}+(n+2)G_{n+2,m}+(n+1)(G_{n+1,m-1}+G_{n+1,m+1})=k(G_{n,m}-G_{n+2,m})\\ (n+2+k)G_{n+2,m}=(k-n)G_{n,m}-(n+1)(G_{n+1,m-1}+G_{n+1,m+1})\\ (n+k)G_{n,m}=(k-n+2)G_{n-2,m}-(n-1)(G_{n-1,m-1}+G_{n-1,m+1})\\ \end{aligned}$$

可以递推了，$d=6$ 也是类似的。放一张推式子的图：

[★★★] QOJ6109 Similarity Graph（#16）

看似思路简单，实际上想到还是有难度的。

第一眼看到题可能想到直接构造方案，发现构造不出来，说明这题可能不用构造，直接推限制。如果我们能推出一组合法的 $p$，且能正确对应 $q$，那么做完了。单独一个 $a_{i,j}$ 推不出来什么关系，因为题目允许 $\mathcal O(n^3)$ 的复杂度，所以枚举三元组 $(i,j,k)$ 刻画他们之间的限制。枚举一下八种限制：

$(a_{i,j},a_{i,k},a_{i,k})$	$(0,0,0)/(1,1,1)$	$(1,1,0)/(0,0,1)$	$(1,0,0)/(0,1,1)$	$(1,0,1)/(0,1,0)$
能推出来的限制	无限制	$p_i<p_j\Leftrightarrow p_i<p_k\\p_i>p_j\Leftrightarrow p_i>p_k$	无限制	无限制

“无限制”的意思就是你单从一个 $p_i,p_j$ 的关系无法推出任何一个 $p_i,p_k$ 或者 $p_j,p_k$ 的关系，这个可以自己画一画。于是我们对每对关系见一个点 $(i,j)$（代表 $p_i<p_j$），可以互相推出来的合并，和 2-SAT 类似的，如果不合法那么 $(i,j),(j,i)$ 在同一个并查集里，否则选编号最小作为关系的就好，然后就可以推出 $q$ 了。

其实还有两个问题，一个是为什么我们已经考虑过所有的限制，还有一个是为什么这样构造出的 $p$ 一定能推出 $q$。如果 $q$ 能导出矛盾，那么存在关系链 $q_i<\cdots<q_i$。首先这个链长不会是 $2$，其次因为推出来 $p$ 的关系是竞赛图，所以可以归纳到链长为 $3$，而 $p$​ 的三元环关系我们已经全部考虑过了，这样就解决了上面的两个疑问。

[★] QOJ6504 Flower’s Land 2（#17）

如果是区间相同的数两两抵消，那么可以给每个值随机赋权判断区间异或是否为 $0$，这个特点在于匹配的时候只能就进匹配，也就是我们希望维护的信息没有交换律，容易想到矩阵。给每种数随机一个对合矩阵，那么判断区间乘积是不是单位矩阵；或者是直接随机一个矩阵，如果下标是奇数那么赋对应数的矩阵，否则赋逆。因为匹配的一对数一定是下标一奇一偶。

[★★] [ABC270Ex] add 1（#17，#18）

非常好赌徒模型，使我的大脑旋转。

这一题正常的做法对于一个状态，发现我们只关心 $\max\limits_i a_i-b_i$，其中 $b_i$ 是当前的值，具体的，如果当前重置的值如果小于这个值，那么计数 $-1$，否则目前最大的肯定是当前重置的这个元素，变为 $a_i$，然后就可以 dp 了。

但是，我们可以套用歌唱王国一题的赌徒模型：这里对匹配串的要求应该是最后 $A_2-A_1$ 个数只能选择 $1$，在数 $A_3-A_2$ 个数只能选择 $1\sim 2$，以此类推，那么当一个串匹配的时候，最终钱数应该是 $\sum\limits_{i=1}^{A_n}\prod\limits_{j=1}^ip_j$，$p_j$ 代表匹配第 $j$ 个字符的概率，这个可以等比数列算。

[★] [CTSC2017] 游戏（#19）

用贝叶斯推一下这玩意儿发现可以用矩阵维护，有一步是要统计一个区间挖掉每一个元素的乘积，这个维护 $f,g$ 代表全部乘积和挖掉的乘积就可以转移了：$g=f_lg_r+f_rg_l$。

[★] [SDOI2017] 树点涂色（#20）

颜色段转异色边，如果暴力的话每次要把所有修改路径上的颜色拉出来重新修改，看起来复杂度爆炸，实际上可以证明均摊下来操作次数是 $\mathcal O(n\log n)$ 的：

假设每个点有三种状态：

1. 和重儿子颜色相同
2. 和轻儿子颜色相同
3. 没有颜色相同的儿子

容易发现每次修改只会跳 $\mathcal O(\log n)$ 条轻边，那么每次 2 类型的总量是可以保证的，所以关于 2 类型的状态切换复杂度也是有保证的；现在只要考虑 1 状态和 3 状态的转化，容易发现 3 只会在端点产生，所以总量是 $\mathcal O(n)$ 的。

于是就可以暴力做了。细节就是对于每一条重链维护两个 set：代表重链上类型为 2 的节点和类型为 3 的节点，修改就可以直接拉出来了。比较优美的一种实现方式是：先把所有状态重置成 1，最后发现只有链底处状态可能不是 1，最后改回来就好。

[★] [BJOI2017] 树的难题

[★] [AH2017/HNOI2017] 影魔

已加入肯德基豪华弱智套餐。

[★★] [KTSC 2024 R1] 水果游戏

肯定要用线段树维护，发现如果出现三个连续段满足其中的值 $x>y<z$，而且如果 $y$ 合并到 $\min(x,z)$ 的时候无法变成完整的连续段（也就是 $cnt_y\bmod 2^{\min(x,z)-y}\not=0$），那么 $y$ 肯定没用了。最后需要维护的就是一个两边单调的东西，量级是 $\mathcal O(V)$ 的，所以就能做了。

这题实现上需要精简一点。例如合并的时候可以把一边的序列一个个插到另一个里面，这样只要考虑插一个数的关系。还有连续段如果能合并成更大的先别急着合并，因为你也不知道你这种合并会不会把后边加进来的数堵了。

[★★] [KTSC 2024 R2] 跳跃游戏（#21，#22）

被评价为套路题，但我怎么没想出来呢，我也觉得很套路啊！

转化成选点，两个点之间至少隔 $k$，最大化选点代价。容易列出 $\mathcal O(n)$ 的转移式：$f_i=\max(f_{i-1},f_{i-k}+a_i)$，套路的按 $\bmod k$ 分类，那么每次就是继承原来位置的数 $+a_i$，并和上一个取 $\max$。现在放到连续段上考虑，容易发现一个连续段的转移一定是在 $\le K$ 步内取 $f_{i-1}$，剩下的全部 $+a_i$，于是把第一个分界点找出来，剩下的暴力加，要动态开点。

还有一种方法需要一点观察：对于最优的选点方案，如果存在两点 $x,y$ 之间间隔 $>K$，那么 $y$ 一定是某个段的开头，否则可以调整。于是把端点离散化下来，特殊单点 chkmax 一下每个段的开头，其他全部 $+a_i$，时间复杂度 $\mathcal O(n\log n)$​。