CodeForces 2600-2900 – hydd's blog

1523E

刚开始想的是直接 dp，记录当前两端都没有/左右有一盏/两端都有的答案，转移就考虑哪个范围能继续递归。
其实可以有另一种思路，期望等于 $i$ 次操作后还没结束的概率之和+1（即 $E(x)=1+\sum_{i\geq 1} P(x>i)$）。
那么每一盏灯（除了最后一盏）就要求它后面 $k-1$ 个位置都没有灯，组合数就能计算 $i$ 盏灯的答案（选完后在每盏灯后放 $k-1$ 个空位，最后一盏除外）。

1391E

图上构造还是比较困难，考虑先求个 dfs 生成树。求完之后如果存在深度 $\geq n/2$ 的显然就存在路径。
dfs 树有非常好的性质，就是只会有祖孙边。所以如果两个同深度的点一定没有边，不同深度的只有祖孙关系才有可能有边。
现在知道了深度 $<n/2$，所以可以给同深度的尽量两两匹配，至少有 $n/2$ 对，然后两对之间，每个点在某个深度只有一个祖先，所以最多只有两条边。

555E

也是类似，图上构造比较困难，可以先缩点变成一棵树（原因是定向在边双里一定可以使得两两可达）。
然后就只有一条简单路径，给它定向即可，最后看有没有冲突。相当于是路径覆盖，直接树上差分即可。

13E

傻逼了。。。第一想法就是 LCT，其实不需要，范围这么小。
考虑直接暴力的话是操作复杂度 $O(n)$，询问复杂度 $O(1)$，且没有很好的性质。
那么可以直接用分块来分摊复杂度，比如说只暴力修改一部分（块内的），每个点维护第一个会到不是当前块的哪一个点。
那么对于修改一个块内的后继，只会影响当前块内的点；询问的时候暴力一块一块跳。

235C

直觉就是倍长后后缀自动机。。。因为循环同构相当于倍长后的一个长度的子串。
由于后缀自动机支持前面删去一个字符（link），后面加上一个字符（trans），直接在上面跳。
但是有个问题就是可能会算重，循环同构的有可能相同。这个一种可以求出 $x$ 的循环节（kmp），还有一种就是在 SAM 上标记一下说明这个点已经经过了。

321E

一眼决策单调性（进一步还满足四边形不等式，相交$\leq$ 包含）。
普通决策单调性可以分治，四边形不等式可以直接改变循环范围（从 $(i,j-1)$ 的决策点到 $(i+1,j)$ 的决策点）。

631E

不妨只考虑数字往后移动，往前移动类似。
考虑 $i$ 移动到了 $j,k$（$i\leq j\lt k$），如果 $k$ 比 $j$ 更优即 $(j-i)a_i-(S_j-S_i)\lt (k-i)a_i-(S_k-S_i)$，整理一下变成 $a_i\gt \frac{S_k-S_j}{k-j}$。
那么说明有效的点一定在凸壳上，维护凸壳。
加点的时候是在一端加入，可以直接弹栈再加；询问的时候二分找，然后转移即可。

1208F

维护一个 $d_j\And d_k=x(j<k)$ 时 $j$ 的最大值是多少，然后做个高维后缀和（最大值）。
枚举一个 $i$，一位一位确定答案，具体的方法是看答案这一位填 $1$ 是否可行（当 $d_i$ 这一位为 $0$ 的时候，看 $d_j\And d_k$ 新增要求这一位为 $1$ 后是否还存在 $j>i$ 的方案），通过高维后缀和判断即可。

741D

重排之后能形成回文串当且仅当最多只有一个字符出现了奇数次。
点分治/dsu，每次加入子树的时候枚举最后剩下的字符，看是否存在符合要求的答案。
时间复杂度 $O(n\log n|\Sigma|)$。

1439C

操作后仍然不会改变它是一个非降序列，直接线段树二分后覆盖。
询问的话，先去除 $x$ 的限制（给 $y$ 加上 $x$ 之前所有数字之和）。然后一定是分成不超过 $\log n$ 段，因为每一段取完，总和至少 $/2$（否则这一段一定还没完），而线段树上只对应不超过 $\log n$ 个区间，直接线段树上二分即可，复杂度是 $O(n \log^2 n)$。

547E

对 $n$ 个串建 AC 自动机。将询问离线后差分。每次插入一个串时给所有前缀 +1。
现在就变成某个前缀，问某个串出现了多少次，相当于求 fail 树上子树的权值之和，树状数组维护即可。
fail 子树代表的是以它为后缀的前缀。

1406E

容易想到，如果答案是素数，显然只能通过询问它本身才能判断（或询问完其它所有素数）。
根据经典结论，$\gt \sqrt n$ 的素因子最多只有一个。先把 $\leq\sqrt n$ 的素数都删掉了，如果过程中发现 $x$ 有这个因子就暴力求出它的幂次。
现在要找是否有 $\gt \sqrt n$ 的素因子，直接暴力显然不太行，还是考虑分块，每次连续删掉 $B$ 个，然后看现在剩下的数字个数是不是恰好少了 $B$，如果不是就说明其中有，再暴力找。
需要的次数应该是 $\pi(n)+\pi(\sqrt n)+(\pi(n)-\pi(\sqrt n))/B+B$，取 $B=\sqrt{\pi(n)-\pi(\sqrt n)}$，则不超过 $\pi(n)+\pi(\sqrt n)+2\sqrt{\pi(n)-\pi(\sqrt n)}$。而 $\pi(n)\leq 9592,\pi(\sqrt n)\leq 65$，总次数符合要求。

613D

可以建出虚树再做，显然影响并不大。
看一下边上有没有被缩起来的点，然后树形 dp（如果有缩起来的说明这条边也可以花 1 代价拆除）。
使用牛逼建虚树方法：“把点按 dfn 排序，相邻点的 lca 丢进去，再排序，每个点在虚树上的父亲就是自己和前驱的 lca。”

1439B

要达到集合的条件，度数 $<k$ 的点都是没用的，可以删掉，不停删去直到剩下的点度数都 $\geq k$。
要达到团的条件，可以降低一下条件，只删去度数 $\sqrt {2m}$ 时显然不能成团，而每判断一次会删去 $k-1$ 条边，所以复杂度是 $O(m\sqrt m)$。

940F

如果没有修改操作就是经典莫队（查询直接暴力查 tot，因为 mex 不会超过 2sqrt）。
现在带修改，所以得用带修莫队。就是按照（左端点所在块，右端点所在块，时间）排序。
注意修改移动的时候如果遇到了区间内的同时要更新 tot。

1110F

dfs 序是 $1,2,\cdots,n$，这很有意思。把所有叶子编号求出来，从小到大排成序列 $leaf$。
没有修改，考虑离线直接把答案处理出来。
现在知道了 $u$ 到所有叶子的距离，那么往 $v$ 走，会使得 $v$ 子树里的叶子（是一个 $leaf$ 下标连续的区间）的距离减少 $1$，其它叶子距离增加 $1$。
拿个线段树处理一下区间加减区间最小值。

364D

这题真不错，首先可以发现随机选一个数，有 $1/2$ 的概率在最后答案里。
你随机 10 次，求出其它数和这个数的 $gcd$，做个倍数和，求出 $gcd$ 为每个数是否可行（判断个数是否有一半），得到最大的就是必须选这个数的答案。

662C

首先有个暴力就是 $2^n$ 枚举每一行翻不翻，然后求每一列最优的方案，复杂度是 $O(2^nm)$。
发现列的顺序没有关系，只和列上每一行的状态有关系，求出 $2^n$ 种状态分别出现的次数 $f_s$。
如果你翻了 $t$ 状态的那些列，答案就为 $\sum_s f_s\times g_{s\oplus t}$，$g_s$ 表示状态 $s$ 中 $1$ 的个数。
改写一下就变成 $\sum_x \sum_y f_x\times g_y[x\oplus y=t]$，直接 FWT 就可以求出所有 $t$ 的答案。

1270G

条件移个项变成 $1\leq i-a_i\leq n$。这个很有意思，它对应的也是一个下标。
看一下条件，$\sum a_i=0$，改成 $i-a_i$ 的形式，也就是 $\sum (i-a_i)=\sum i$。
由于 $i-a_i$ 也是个下标，考虑将 $i$ 和 $i-a_i$ 连边，那么一个环就能恰好满足这个式子（每个数的下一个编号和=每个数编号和），且显然会有环。

455D

splay/fhq-treap 显然可以做。不过也可以用分块。
每个块维护起始的位置（块内真实的值，是这个起始位置开始取）。每次从前一块移动一个值的时候就把起始位置之前的位置替换，并把起始位置向前移一步。
询问的时候整块就维护一下每个数出现次数，散块就暴力。

1515F

操作相当于要求每次生成的点非负。如果最后的值（一定固定为 $(\sum a_i)-(n-1)x$）为负则一定无解。
之前做了好几道只要满足最后条件就合法的，不妨猜测这题也是。假如拿出了最大的和它旁边的（至少是最小的），若 $\max+\min<x$，那么最大可能的总和 $(n-1)\times \max+\min=(n-2)\times \max+(\max+\min)<(n-2)x+x=(n-1)x$，矛盾。
所以每次取最大值和旁边的就可以了，用并查集和邻接表维护（任意选择一棵生成树即可）。

1278F

拆一下，假设洗出王牌的轮数集合为 $S(x=|S|)$，那么 $x^k$ 的组合意义就是在 $S$ 中选择 $k$ 次数。
反过来考虑，知道 $k$ 次数分别选的什么求轮数集合的概率。
求出选 $k$ 个数（每个数在 $[1,n]$ 轮），有 $i$ 个不同的方案有 $dp(k,i)$ 种，对应轮数集合的概率是 $(\frac 1m)^i$（每张牌出现的概率仍然是独立的 $\frac 1m$）。

1370F2

首先把所有点都问一次，那么就可以得到一个在两点路径上的点 $u$ 和两点之间距离 $d$。
路径上深度最大的一定是一个关键点，直接二分深度，询问大于等于此深度的点距离是否可行。
另一个点也很好求，把和这个点所有距离为 $d$ 的都拿出来再询问一次。
这样需要 $12$ 次，不过可以优化：你知道第一次询问出的点 $u$，以 $u$ 为根，那么较深点的深度至少是 $d/2$，就可以减少一次。

240F

要排成回文串，先求出出现奇数次的数的个数，$>2$ 则不能排，$=1$ 把这个数放一个到中间继续排，否则直接排。
排的方法就是从 $a$ 到 $z$ 依次放，线段树维护区间每种字符个数。

650D

如果原先 LIS 必须包含这个被修改的数，那么不包含它的 LIS 长度 $-1$，否则不变。
包含这个数的就求出之前比它小的 LIS 最大的，之后比它大的 LIS 最大的，求和 $+1$。
离线即可。

700C

0 条边就是判断本身两个点是否不连通。
1 条边就是先缩边双成树，然后两点树上路径的所有边的最小值。
2 条边的话就一定不会删树边，剩下的给每条边权值加上 $+\infty$ 跑最小割，为了尽量少删边故一定会删 $\geq 2$ 条，边数最少其次权值最小的。

576D

先考虑怎么暴力，设 $dp[x][u]$ 表示点 $u$ 是否可以从 $1$ 开始走 $x$ 步到达，转移就看相邻的边是否已经可以走，更新过去的点。不过这个复杂度太高。
发现其实很多种不同的 $x$ 对应当前能转移的是一样的，把边权从小到大排序，那么对应的已经解锁的边是一个前缀。
对于每次对应解锁边集变化的 $x$，它到下一次边集变化 $y$ 之间都是不变的，bfs 一遍看能不能直接到达 $n$，如果不能就得看再走 $y-x$ 步能到哪些，可以用 or/and 矩乘，进一步可以用 bitset 优化，复杂度是 $O(m(n+m+n^3\log d/w))$。
其实还可以进一步优化，你发现你只需要知道答案矩阵的第一行，也就是哪些是可以从 $1$ 开始走到的（或者说本身只有第一行有值）。
那么如果你能快速维护另一个矩阵（当前能走边的邻接矩阵）的 $2^k$ 幂，那么就可以暴力乘（现在就乘就只需要 $O(n^2)$ 了）。
考虑修改一下，把某个原先是 $0$ 的 $a_{i,j}:=1$，那么对 $0$ 次方影响就是这个位置，$1$ 次方就考虑它做左边的影响和右边的影响，每次成功修改再考虑操作下一次，而每个最多变成 $1$ 一次，所有矩阵总共 $n^2\log d$ 个数，每次更新是 $O(n)$，复杂度是 $O(n^3\log d)$。

1363F

看这个操作，每次把 $s_r$ 移动到 $s_l$ 的位置，也就是每个数都可以往前移动若干个位置，求操作数。
首先两个串的可重集必须相同。考虑类似求编辑距离的 dp，设 $dp(i,j)$ 表示 $s[1..i]$ 和 $t[1..j]$ 匹配的最少操作次数（如果 $s$ 长度比 $t$ 小说明从后面拿了若干个上来）。
转移就考虑三种：直接匹配；从后面拿一个 $t$ 对应的字符（必须还有）；$s$ 当前字符被拿走了。
难以考虑的是你不能确定当前的状态是怎样的，可能 $s$ 这个字符已经被移走了但你拿来直接匹配，可能后面所有 $t$ 对应的字符都移走了但你还继续移过来，可能你还了一个没借过的字符。
不过显然得满足 $s[1..i]$ 的可重集 $S$ $\subseteq t[1..j]$ 的可重集 $T$（现在 $T-S$ 的都是从后面拿上来的），这样就能避免不合法情况（前两种会导出字符个数不同，最后一种会违反这个条件）。
所以直接这么转移是可以的，所有非法状态都不会记录到答案，而合法状态显然都会被计算到。

163E

和之前的 547E 类似，只不过匹配反过来了。
把 $S$ 的串加入 AC 自动机，建立 $fail$ 树，在每个串末尾对应的节点子树加 $1$（能匹配那些以它为后缀的）。
然后枚举询问串的每个前缀，看以多少个 $S$ 中的串为后缀，求和即可。

516D

这个 $f$ 就是到带权直径两端点距离的较大值。
把直径整条拉出来，那么不在直径上的每个点是它父亲的权值 $+val_e$，直径上的求出最小的点，往两边扩展也是 $+val_e$。
那么把直径上（也是全局）最小的点拿出来，以它为根，那么每个点的权值都是父亲的权值 $+val_e$。
双指针一下，$r$ 从大到小，$r$ 变小就是删除一个数（它一定没有儿子），$l$ 变小就是加入一个数（它一定没有父亲），并查集维护即可。

1554E

未被标记的节点个数。。。这个东西一看好像拓扑序，就是相邻拓扑序比它大的个数。
而它是棵树，可以随意定向不会成环，$a$ 的值就是出度大小。出度总和为 $n-1$，故 $k$ 必须得是 $n-1$ 的约数答案才不会为 $0$。
每次考虑一个叶子节点连边的定向，显然定两种方向会导致最终答案不同，每次删掉一个叶子节点，可以发现 $a$ 共有 $2^{n-1}$ 种。
那么，$k=1$ 的方案可以由总方案减去，其它情况得要求不能出现出度是 $1$ 的，所以叶子节点的边都是入边，现在出现的新的叶子还得满足 $k$ 的条件，所以 $k>1$ 最多只有一种方案。
有一个显著的优化是你只需要考虑素因子，求出方案后得到真实的 $k$，把那个 $k$ 的答案设成 $1$。

1039D

$k$ 减小答案不会变小，这是因为你 $k-1$ 可以用 $k$ 的路径方案且每条路径删掉一个点。
可能的取值只有 $O(\sqrt n)$ 个，直接写假的整体二分（每层判断复杂度和答案区间一点关系都没有）的复杂度是 $O(n\sqrt n\log n)$。判断就是 dfs，每次看子树上来两条最长的，能接起来就接起来。
不过也可以直接根号分治，$k\leq \sqrt n$ 直接暴力，$k>\sqrt n$ 答案种类只有不超过 $\sqrt n$ 个，二分和当前相同的右端点暴力判断。不过取块大小为 $\sqrt {n\log n}$ 应该会更优。

1495D

树上 $u$ 到 $s,t$ 的距离和原图相同。那么原图中在 $s,t$ 最短路径上的还得在树上 $s,t$ 的简单路径上，所以原图 $s,t$ 的最短路径必须唯一才有解。
对于其它点到 $s,t$ 要走的第一个的点得相同，从合法的那个点过来都可行，求出个数相乘即可。

505E

最小化最大值，先来个二分。就变成所有数都 $\leq mid$。
直接模拟可能会出现 $-p$ 之后 $<0$，还得重新考虑。
反过来操作，初始都是 $=mid$，每次可以把若干个 $+p$。
每次先减去 $a_i$，然后再给若干个加上 $p$，要求每一时刻都不能有 $<0$ 的（否则往后做答案就 $>mid$）。
要求结束的时候的值 $\geq h_i$。

293E

先点分治，然后就变成两个不同子树的点到根的 $A$ 值和不超过 $x$，$B$ 值和不超过 $y$。
把每个点对应的可以的点的限制拿出来，就变成二维偏序，注意去重（在同一子树，算成有序对，把选同一个点也算进去）。

258D

把期望拆成每个 $ia_j$ 的概率之和。设 $p_{i,j}$ 表示 $a_i>a_j$ 的概率。
交换 $x,y$，那么它们之间的概率变成 $\frac 12$，而其它数和它们的概率也是取平均值。
初始 $p_{i,j}$ 都是 $\frac 12$，修改的时候 $O(n)$ 计算影响，最后答案求和即可。

755F

先把排列建环，那么每个环最少可以花 $\lceil \frac {len}2\rceil$ 的代价使得它们都收不到。
换句话说，如果环长是偶数，每一步操作都可以删掉两个数；否则环长是奇数，最后一次操作只能删掉一个数。
要收不到的尽量多，那就尽量选一次操作能删两个的，如果还有的多就选能删一个的。
要收不到的尽量少，那每一个环第一次一定会影响两个，然后之后每次都可以只影响一个，最后一次可以一个都不影响。也就是如果取完一个环那么取了多少减少多少，否则会多减少一个。那么如果能正好有若干环的和为 $k$ 那么就可行，否则要多减少一个。
因为环的总和为 $n$，种类只有 $\sqrt n$ 种，把同样长度的环进行二进制分组即可。

1458C

这个题比较经典，只有前 $4$ 个操作的话那么就直接记录每个方向位移了多少次。
第 $5/6$ 个操作就是置换把两个反过来（下标和数值反过来）。
所以这个你就直接记录 $(i,j,p_{i,j})$，第 $5$ 个操作就是交换第一维和第三维，第 $6$ 个操作就是交换第二维和第三维，前 $4$ 个操作就是在第一维/第二维加上一个值再取模，记录现在三维的顺序和每一维加上了多少即可。

848C

区间 $[l,r]$ 里的 $pre_i\geq l$ 的贡献为 $i-pre_i$。
由于 $pre_i\lt i$，所以不妨把区间改为 $[1,r]$。也就是求 $l\leq pre_i,i\leq r$ 的 $i-pre_i$ 的数字之和。
你如果直接动态维护的话就必须得用二维数据结构了，但是可以套个 CDQ 分治来离线维护。
把操作变成添加/删除一个二维点 $(pre_i,i)$。对当前询问有影响的操作如果是添加就加上贡献，否则就减去贡献。
两边递归完后，合并时计算贡献即可。

724E

容易想到一个最大流是每个点从 $S$ 连 $p$，连到 $T$ 为 $s$，任意两点编号小向大建 $c$ 的边。
这个直接建边显然复杂度过高，但是可以由于最大流=最小割，而前 $i$ 个点具体是哪些和 $S$ 相连并没有关系，你只需要知道个数。
如果和 $S$ 连就断掉 $T$ 即可，和 $T$ 连不仅要断掉 $S$，还要断掉之前所有和 $S$ 相连的点的边。
记录之前有多少连到 $S$，当前到了哪个点，滚动数组优化 dp 空间即可。

908G

先枚举一个数，算它的贡献。对于每个 $i=1,2,\cdots,9$，把每一个数字变成 $\geq i$，最终的数字求和显然等于原数字。
记录一下到哪一位，是否压上界。如果填 $<i$，那么不会影响贡献；填 $\geq i$，在最后加入一个 $1$，枚举每个 $d$，计算答案后求和即可。

605E

容易想到记录 $dp[i]$ 表示 $i$ 到 $n$ 的期望天数。
假设当前已经求出的是期望天数前若干小的，感觉不太好转移。
考虑剩下的期望天数最小的有什么性质，由于它是最小的，如果没有往已经求出的那些点的边，那么它就会停在原地。求出这个条件下期望天数最小的天，就说明其它的作为剩下的期望天数最小的一定不可行（它比它们小，且它一定不会走到期望天数比它大的）。
就这样转移，具体来说每个的概率是比它小的边都没出现$$它出现了$$它的期望天数求和后 $+1$，注意要把不动的移过去解方程。
这个方法类似 dijkstra？

1301F

考虑路径长成什么样，走若干步 — 跳一步 — 走若干步 — 跳一步 — ...。
乍一看好像很难，想枚举第一步跳的在哪个位置，预处理后面的答案。
然后发现其实没必要枚举位置，枚举跳第一步的颜色，那么前面的也预处理，后面的也预处理。可以发现前后预处理的其实可以是一样的（前面不一定只能走，也可以允许跳）。
具体求法就是每一步要么走要么跳，跳就到所有颜色相同的（然后标记一下以后不更新这种颜色跳的了），bfs 即可。

713D

设 $dp(i,j)$ 表示以 $(i,j)$ 为右下角的最长正方形的边长。
怎么转移呢？和二维前缀和类似，只不过现在是取最小值，也就是 $(i-1,j),(i,j-1),(i-1,j-1)$ 的最小值 $+1$（如果当前位置没有拼图那么答案为 $0$）。
那么直接求答案很难，因为有不超出矩形的限制，所以可以二分答案，那么在前 $mid-1$ 行前 $mid-1$ 列为右下角就不能形成矩形，其它就求 $dp$ 最大值是否有 $\geq mid$，有说明答案合法。

961G

考虑每个单点的贡献（显然贡献系数是一样的）。
考虑和它同一组的数的个数，它的贡献系数就是所有方案下，所在组数的个数之和。
这个等价于再选一个同组的数的方案数。再拆开，枚举一个同组的数，求它们在一组的方案数，就是 $(n-1)S(n-1,m)$，注意同组的数可能是自己，所以还要加上 $S(n,m)$。
所以答案就是 $((n-1)S(n-1,m)+S(n,m))\sum_i a_i$。算单个斯特林数用组合数容斥即可。

1223F

考虑每个位置开始往后第一个能消完的，这之后的就是直接拼上去。
怎么处理第一个能消完的？首先先看下一个和当前的是否相同，是就到下一个就能消完；否则说明要先把下一个开头的消掉，也就是到 $nxt_{i+1}$ 又变成只有 $a_i$ 一个数，然后再继续判下一个数是否相同。换句话说就是 $i+1,nxt_{i+1}+1,nxt_{nxt_{i+1}+1}+1,\cdots$。
怎么优化判断？类似 $kmp$ 自动机，每个点记录往后路径上第一个某种字符出现位置，然后把中间的无效的暴力删去。一种实现是可持久化线段树，但有网友用了 map 的 swap，发现其实是可行的，因为任意两个数的 $nxt_i$ 不同（如果相同，那么不是最短的可以把最短的那段拿掉依旧合法，且长度变短，矛盾）。

1149C

它这个和普通的树括号序类似，只不过少了一个最左边的左括号和最右边的右括号。
树上两点距离，如果不是祖孙关系，就是 dfs 序小的右括号..dfs 序大的左括号之间去掉匹配的括号后的长度；是祖孙关系，就从 dfs 序小的左括号..dfs 序大的左括号之间去掉匹配的括号后的长度。
这里给出一个更进一步的结论：树上任意一个区间去掉匹配的括号都能表示树上的一条简单链，树上的所有简单链都能用这种方法表示。（后半句上面就已经说明了，前半句就看你把匹配的删去后是 )..)(...( 就说明是非祖孙关系的距离，是 (...( 或 )...) 就说明是祖孙关系）。
删去匹配括号后的长度，也有一个结论：在序列里找到一个分隔位置，最大化分隔位置后的和-分割位置前的和，其中和指把 ) 当成 $-1$，( 当成 $+1$ 求和。（如果找到的分割位置恰好是删去后剩下的某括号之后，一定不如放在最后一个 ) 之后。如果不放在某个剩下的括号后，一定可以移动到前面的剩下的 ) 之后，因为括号序列的一个后缀和一定是非正的，前缀和一定是非负的，减一下还是非正的，不如移到前面贡献变成 $0$）。
怎么求这个的最大值？考虑第一个把答案区间分成两部分的点，那么就是左儿子的一个后缀与右儿子的一个前缀，如果分隔位置在左边，那么右边就全是正的（右边前缀和最大值），左边先负后正（左边后缀答案最大值）；分隔位置在右边同理。所以要维护前缀和最大值，后缀和最小值，前缀后缀答案最大值，区间答案。

1364E

$0 \operatorname{or} x=x$，所以可以先求出 $0$ 的位置。
把排列随机打乱，然后求出第一个位置的值。
往后扫，如果有一个数是当前数子集（or 一下），就把当前数替换，求出新的数的值。
每个数求它的值就随机 $20$ 个位置 or 一下来判断，它错误的概率是 $0.001\%$，且错误了并不会导致答案错误，只有可能导致询问次数增加。
（不考虑发生错误的情况）理论上需要的次数为 $2n+11\times 20$，实际上跑不到 $11\times 20$，初始一定会满，且一次求值不一定只比原先少 $1$ 位数字。

442D

路径就分为祖孙链或非祖孙链。由于没有颜色数限制，所以非祖孙链一定可以从 LCA 断开分成两条颜色不同的一定不会更劣。
设 $dp_u$ 表示非根节点 $u$ 的子树（再加上 $u$ 往父亲连的边）的答案，那么答案最大的儿子一定要和它到父亲的边颜色相同，其它儿子颜色只能不同。
设 $v$ 为答案最大的儿子，$w$ 为次大的儿子。从 $\max(dp_v,dp_w+1)$ 转移过来（这个东西其实是到根节点的轻边数量的最大值）。
现在树是变化的，每次可能会加上一个儿子。但是到根轻边的数量最多 $\log n$，所以每次可以暴力往父亲更新，如果父亲的答案增加则继续更新。因为 $dp$ 总和只有 $O(n\log n)$，所以复杂度也为 $O(n\log n)$。

960G

容易想到前后缀可能是独立的，考虑前缀最大值和后缀最大值所在位置的下标，发现前缀最大值后缀最大值一定都包含最大值 $n$，那么前后的确就独立了。
那么设 $f_{i,x}$ 表示前 $i$ 个数有 $x$ 个数是前缀最大值，那么 $ans=\sum_{i=1}^n {n-1\choose i-1}f_{i-1,a-1}f_{n-i,b-1}$（枚举最大值的位置）。
转移就是 $f_{i,x}=(i-1)f_{i-1,x}+f_{i-1,x-1}$，发现转移就是第一类斯特林数，且初始值也是一样，所以就是第一类斯特林数。
考虑组合意义，就是从 $n-1$ 个里选出 $i-1$ 个组成 $a-1$ 个环，剩下的 $n-i$ 个组成 $b-1$ 个环。
由于是对所有 $a$ 求和且有组合数，所以前 $a$ 个环和后 $b$ 个环的组成元素和个数没有具体要求，所以可以先组成 $a-1+b-1$ 个环，然后再从其中选 $a-1$ 个。
即答案是 ${a+b-2\choose a-1}s(n-1,a+b-2)$，组合数好算，难点在于斯特林数。
具体斯特林数可以构造生成函数，因为 $f_{i,*}$ 本身就是生成函数式的转移，分治 NTT 即可求出。不过也可以多项式求逆的方法倍增求出。

204E

先建立广义后缀自动机，拿个线段树记录一下每个点在哪些串中出现过。
线段树合并求出子树里有多少种字符串， $\geq k$ 的就说明可行，对于每个串的结尾节点求一下到根路径上有多少可行节点累加即可。

1254D

操作等价于换根后子树加。
每个点如果要加，那么选择的 $r$ 和当前点必须在根的不同子树。
根据树剖的套路，只对特殊的外子树和重子树直接更新，询问的时候就跳重链（重链上的直接更新完了，只有链切换的时候贡献要算）。

1209F

把边拆点，使得每条边都只有 $1$ 位数（注意要变成有向图）。
bfs，原先距离小的先更新，距离相同的按照添加的数从小到大更新。
为了方便可以把距离相同的存成一个 vector 加入队列。

1389F

假设当前另一种右端点最靠右的位置是 $x$，那么你只能选这种左端点 $>x$ 的。
设 $dp_i$ 表示选 $i$ 的答案（且 $i$ 是当前右端点最靠右的），那么就要枚举另一种的 $j$ 使得 $r_j\lt l_i$，然后选择所有 $r_j\lt l_k,r_k\leq r_i$ 的所有当前种的区间。
把两种区间都按照右端点排序，那么 $j$ 的范围就是另一种的一个前缀。现在要快速计算最优的转移点，也就是要求出转移点的贡献。那么 $i$ 右移的时候，会更新一个前缀 $+1$。
所以只需要维护一个前缀最大值，前缀 $+1$，单点修改的数据结构，线段树即可。

356D

首先可以发现，子树和最大的一定是某棵树的根，且所有根的子树和必须得是 $s$。
这两个是必要条件，但是否充分？可以发现可以把剩下所有的按照子树和从大到小接到子树和最大的形成一条链。
所以现在就要求是否有若干个点的和为 $s$（最大的必选），可以发现这个就是 $01$ 背包，但是复杂度太高。但是由于值域并不大，且只需要记录是否出现，故可以用 bitset 优化。
不过还需要记录方案，但是每个点只需要记录一次。所以对于每次新增的 $1$，暴力记录它们是这一轮加入的，和加入前的 bitset xor 一下然后 _Find_next 跳过去即可。

1148F

它用 $mask$ 操作一次等价于用 $mask$ 里每一位的都操作一次。
不妨假设初始和是正的，现在要变成负的。
每个数只和它为 $1$ 的那些位有关，那么不管低位怎样，最高位还是能确定当前数的符号。
把每个数按照最高位分类，那么从低到高考虑每种最高位的数，那么你可以知道这些数现在的和，可以把它取负。
你只要把每一组的和变成非正，而由于初始和为正，所以不可能每组都是 $0$，就符合题目要求了。

671D

设 $dp_i$ 表示 $i$ 的子树和 $i$ 到父亲的边都覆盖的最小权值和。
但是这样还不够，这个点可能还有往上的路径覆盖了好多个点。
拿个线段树维护覆盖了链上深度为 $\geq x$ 的点的答案，子树转移覆盖到的取 $x$ 的最小值。启发式合并一下点，$x$ 从小到大维护答案越来越小的。注意还要加入选择当前点往上的路径，此时所有儿子只需要取代价最小的。

1553G

你操作一次之后一定会变成偶数，所以你可以把 $s,t$ 都操作一次一定就连通，所以答案不超过 $2$。
答案为 $0$ 容易判断，看是否在同一个连通块（每个质数建虚点，并查集合并）。
答案为 $1$ 可以考虑每个 $a_i+1$ 会使得哪些原先不连通的质数连通块连通，给两两连通块标记一下（$C(7,2)$）。

535E

每个人花费的时间是 $T=\frac S{s_i}+\frac R{r_i}$。把时间除以 $R$ 变成 $T=\frac{\frac SR}{s_i}+\frac 1{r_i}$。
设 $k=\frac SR,x=\frac 1{s_i},y=\frac 1{r_i}$，$T=kx+y$，$y=-kx+T$。
确定了斜率 $\frac SR$ 后就确定每个需要的时间，你发现这等价于用一条斜率固定的直线去切，那么只需要保留凸包上的点。
不过注意，你用来切的线斜率必须是负的，所以你保留的是下凸壳，最后取斜率为负的部分（左半部分）。
注意时间一样的人是可以保留的。

724G

还是和 WC2011 的那题一样，任何一条路径都能由起始两点的一条简单路径再加上若干个环组成，这个之前也证明过，取个生成树后加边归纳即可。把所有简单环的异或和加入线性基。
如果线性基上第 $i$ 位有 $x(x>0)$ 个 $1$，那么能异或出 $2^{tot-x}\times 2^{x-1}$ 个第 $i$ 位是 $1$ 的数，剩下的都是第 $i$ 位为 $0$ 的数。如果没有 $1$ 则异或出的都是第 $i$ 位为 $0$ 的数。
简单路径就是两点到根路径上权值异或，可以求出简单路径第 $i$ 位为 $0/1$ 的个数。
对应能异或出多少个答案第 $i$ 位是 $1$ 的，就可以求出来了。最后乘上 $2^i$ 求和即可。

311D

模数不特殊不太能做，这种对单个数一直操作就考虑有没有循环节。研究一下模数，发现它是质数。
因为你每次三次方，所以你想看的应该是不停三次方后会不会形成循环节，也就是 $a^{3^x}\equiv a\pmod p$，也就是 $(p-1)|(3^x-1)$，然后打个表发现 $x=48$ 就满足条件。
线段树，每个节点维护 48 个和，表示当前区间做 $0,1,\cdots,47$ 次操作后的区间和。

482C

容易想到的一种做法是先枚举答案，然后状压 dp。
不过这样复杂度太高，好像有一句玄学的话：概率从前往后推，期望从后往前推。
我们倒着设状态，$dp_s$ 表示当前问了状态 $s$，确定字符串的期望步数。
设 $num_s$ 表示 $s$ 状态有多少种字符串，彼此不能区分。你考虑这一次问什么，加上这一位，只有那些 $num_{s|2^i}$ 中的那些还是不能区分，所以可以计算概率后转移。
至于 $num$ 数组的计算，先记录在这个状态下不能区分的是哪些字符串（二进制状态）。
直接枚举两个字符串然后枚举 $s$ 复杂度还是太高，可以先求出两个串共有的位置，然后再求个高维后缀和。

1473F

一眼最大权闭合子图。
直接建边能达到平方，不过可以发现，往前连，两个相同的数字只需要连后面的那个。
现在边数只有 $O(n\max d(a_i))$，根据经典表格，$\max d(a_i)\leq 12$。
接下来就可以跑最大权闭合子图了。原图的边连 INF，S 向非负权点连权值，负权点向 T 连权值绝对值，先累加非负权边，再减去最小割即可。

1469F

链接上去的时候，显然选链的中点是最优的（白点数量固定，那么一定是深度越小越好）。
操作的策略？你想让整体深度深度都小，每次接的一定接到深度最小的点（你不可能一直不接它接深度大的）。那么每个点接到的深度+半链长度就是这条链会达到的最大权值。
容易猜测会长度从大到小接，每次选长度最长的接不仅使当前答案最小，也有更多的深度小的候选点（更严谨的证明可以考虑调整）。
那么，每次相当于是给某个区间深度的加 $1$，由于你是从小到大取的，所以可以直接差分更新。

1422F

在线乍一看没啥思路，先想想离线。
枚举右端点，考虑线段树维护左端点的答案。右端点移动时，那么有些后缀的幂要增大到当前 $p$ 的幂次，拿个单调栈维护指数的后缀最大值，然后弹栈暴力区间乘，线段树即可。
那么在线也一样，只不过需要用可持久化线段树记录历史版本。

79D

区间取反，可以变成差分。差分后最多把 $1$ 的位置变成 $2k$ 个。
反过来，初始有一些灯亮，每次可以选择两盏距离为 $d$ 的灯一起取反。
那么由于操作顺序无关，你每次可以选择一盏亮着的灯和另一盏灯取反，继续操作那一盏灯和另一盏，以此类推，直到两盏灯都关了。
那么，从每盏亮着的灯开始求到其它亮着的灯的最短路，求出之后就可以状压 dp 两两删去。

1140F

你发现 $x_0,a$ 一直在左边，$y_0,b$ 一直在右边，容易联想到矩阵。操作变成矩形有三个点的时候第四个点也会有。而矩阵对应二分图，行向列连边。
二分图连通的部分，左边和右边的两两都有连边。用并查集维护一下。
但是并查集不方便删除，这个好办，线段树分治一下即可。

372D

首先有个经典结论，树上包含 $a_1,a_2,\cdots,a_k$ 的连通块的最小边权和为按照 dfs 序排序后当成一个环相邻点距离和再 $/2$，因为这样把每一条边都算了两次。
然后就可以 set 来维护点 dfs 序大小，双指针求即可。

1373G

这里用的题意是 luogu 的翻译，认为二元组第一个数是行，第二个数是列。
每个格子不能有多个棋子并不重要，你可以调整顺序满足要求。
求出每个球用最小的步数到 $x$ 行时 $y$ 是多少，对于 $y$ 相同的需要往后放，那么就是 $y\geq v$ 的个数不能超过 $ans-v+1$，设 $y\geq v$ 的个数为 $f_v$，那么 $ans=\max{f_v+v-1}$。
那么修改就是前缀加/减，求全局最大值，线段树即可（注意值域是 $2n$ 而不是 $n$）。

1372E

由于是平方，所以尽量要放到同一个位置的数量尽量多。考虑先枚举最多的。
设 $dp_{l,r}$ 表示被区间 $[l,r]$ 完全包含的，那么选择一个 $k$ 认为它放最多，能放的都放到位置 $k$，剩下的变成 $[l,k-1]$ 和 $[k+1,r]$。
有多少个包含的可以预处理。然后就可以直接转移了。

512D

你发现操作等价于每次选择一个度数不超过 $1$ 的点删去，求删去 $k$ 个点的方案数。
相当于是拓扑排序前 $k$ 个数计数，你先把拓扑排序排完后剩下的环删去，那么那些和环有一端相连的树认为它们是有根的，否则是无根的。有根时认为根不是叶子。
对于有根树，设 $f_{i,j}$ 表示 $i$ 的子树选择 $j$ 个删去的方案数，树上背包合并（必须子树的点都选才能选自己），需要乘上一个组合数。
对于无根树就比较麻烦，考虑把所有点当根都计算一次，那么每种方案会计算 $tot-k$ 次，也就是除了删掉的点当根其它的方案都会算到，最后除掉即可。
树上背包可以卷积优化，但没有必要。

487D

这种做多了就知道是倍增或者分块，这个倍增显然不好维护，就只能倍增。
先考虑暴力，那么直观想法是维护每行的点第一个会到上一行的点在哪一列，操作 $O(m)$ 询问 $O(n)$。
然后考虑优化，这种倍增不容易维护，使用分块，每 $O(\sqrt n)$ 行分一块，操作复杂度就变成 $O(m\sqrt n)$。
那么分了若干层之后，每次修改直接重构整一块，询问就一块一块跳。
由于本身操作次数是 $O(\frac nm)$ 级别，所以总复杂度是 $O(n\sqrt n)$。

633F

选择两条不相交的链，那么一定有一条边可以分成两部分，使得两条链分别在两个子树。
用记录边的 dp，就可以转移了（或者也可以换根 dp 之类的也行）。

85E

这个曼哈顿距离最小容易想到转成切比雪夫。
那么就是要用两个边长相等的正方形覆盖所有点，且要让边长最小。
求出一个能包含所有点的最小的矩形，显然它四条边上都有点。
两个正方形至少得包含两个边界上的点，且如果某一维超出边界可以平移。
那么两个正方形一定靠在矩形的两个对角，具体边长可以二分或者看每个点到两个角的切比雪夫距离取小的。

1207G

操作串一直在变，不妨对询问串建 ACAM。
操作串在 ACAM 上跑，询问只需要知道多少跑的过程中经过的点在 $t$ 的子树里。
你跑的时候给当前点加 $1$，询问在 dfs 序上树状数组即可。
但是操作串总长可能很大，不过每次改变量不大，给操作也建个树，每次走到一个就加入这个串新增的字符。

917D

设 $g_i$ 表示钦定 $i$ 条边重合的方案数，那么即分成 $n-i$ 个连通块的方案数。
根据经典 Prufer 序列结论，把若干连通块连成一棵树的答案是 $\prod a_i\times n^{k-2}$。
这个 $\prod a_i$ 有个经典组合意义是每个连通块选一个点，dp 记录当前在哪个点，有多少连通块，当前连通块是否选点即可。
最后给 $g$ 二项式反演一下就可以求出答案。

338E

要求 $a_i+b_j\geq h$，那么就是 $a_i\geq h-b_j$。
你要匹配一定是把两个区间排序后两两匹配，但是排序不好维护。
不妨考虑类似括号序列的方法，在 $h-b_j$ 位置 $+1$，$a_i$ 位置 $-1$，要求任意前缀和非负。
变成后缀加减要求任意值非负，线段树维护。

542E

可以发现操作就是把两个点捏起来。
感觉三角形是捏不掉的，想让它消失必须选一个内部一个外部，但是即使选了新的 $x$ 还是会连原先三角形的边，所以有三角形就无解。进一步猜测和二分图有关，考虑奇环和偶环。
奇环如果选一个环内一个环外和刚才一样，环长都不会变；如果两个都在环内，会变成一个奇环一个偶环，而环长变成 $3$ 时就无解。
偶环如果选一个环内一个环外，环长也不会变；环内的有可以变成两个奇环或变成两个偶环。
所以只有二分图有解，对于二分图的每一个连通块，能取到任意两点最短距离的最大值，取一个 bfs 树同层的点合并即可。

1365G

按位或是可以重复合并的。
由于任意两个不同数至少有一个二进制位不同，也就是任意 $x\neq y$，$x$ 取反和 $y$ 一定有相同位。
求出和 $x$ 取反有相同位的数合并，这个等价于拿出 $x$ 取反的每一位，和这一位相同的数字的或。
直接处理需要 $20$ 次，但是处理完之后询问的次数不是瓶颈，考虑减少处理的询问数。
现在这样要询问每一位是 $0/1$ 的，我们希望找到一个满足任意两个不同的数它们至少有两位不同（一位是 $1/0$，另一位是 $0/1$），那么我们只询问 $1$，就只需要 $13$ 次询问。
有一种满足上面条件的就是每个数字重标号后 $1$ 的个数一样，那么上面的就成立了。由于 $C(13,6)>1000$，所以就可以选择重标号成 $13$ 位其中恰好有 $6$ 位是 $1$，那么就可以询问每位是 $1$，恰好需要 $13$ 次完成。

1601D

分情况讨论这个最大值，这种一般就考虑调整：
最大值都是 $a$，不妨假设 $a_i<a_j$。
$j$ 先上 $i$ 一定上不去，不如先让 $i$ 上且 $j$ 有可能上去且最后高度不会更高（结论是 $i$ 先上）；
如果一个最大值是 $a$ 一个最大值是 $s$，不妨设 $i$ 的最大值是 $a$，$j$ 的最大值是 $s$。
如果 $a_i>s_j$ 则还是 $i$ 先上 $j$ 一定上不去，不如先让 $j$ 上可能上去且最后高度不会更高（结论是 $j$ 先上）；
不如 $a_i\leq s_j$ 则 $i$ 先上不会影响 $j$，$j$ 先上则不一定（结论是 $i$ 先上）。
最大值都是 $s$，不妨假设 $s_i<s_j$。
$i$ 先上，一定不会影响 $j$；$j$ 先上，可能会影响 $i$（结论是 $i$ 先上）。
所以发现最大值小的一定优先，最大值相同的可以直接贪心思想，一定是 $s$ 小的先上。

1023F

由于你的连接都想让顾客选，所以先把边权都设成 $0$，求一棵最小生成树。
对于剩下的对面的边可能可以替代你，对于那些边考虑它和树边形成的环，那么你的权值就不能 $\geq$ 它的权值，这样就可能选他的了。
所以你把你的边权值设成 $+\infty$，其它树边权值设成 $0$，每次链取最小值即可。
注意可以离线，所以可以把剩下的边权排序后并查集维护。

702F

暴力就是按照 $q$ 从大到小，其次 $c$ 从小到大，能购买的依次购买。简单点说就是如果余额 $\geq c$ 就减去 $c$，答案 $+1$。
直接做不好做，考虑拿平衡树维护每个人剩下的价格。
但是如果你暴力直接 split 成两部分，然后暴力减去再一个一个插入，复杂度也不对。但是你 split 成三部分，$[0,c),[c,2c),[2c,+\infty)$，只需要暴力加入第二部分，第三部分的相对大小一定还是比之前大，所以可以直接 merge。
这样复杂度是对的，因为每次操作后至少减半。

549F

使用经典单调栈来求出每个点作为最大值的区间（使用经典方法认为相等时前面大）。
然后每次枚举最大值和长度较短的区间，用 vector+binary search 求出较长区间的答案。这个本质上等价与 dsu on tree，所以复杂度是 $O(n \log^2 n)$ 的。

1348F

构造一组方案可以贪心，从小到大枚举 $i$，每次把 $i$ 给包含 $i$ 的右端点最小的。
是否有第二种？如果有一定能通过交换一个和之前 $r$ 最大的得到，判断一下即可。

1400G

容斥，直接 $O(2^m)$ 枚举哪些不满足的条件都同时出现了（注意这个是可以容斥的，考虑容斥原理的式子）。
枚举集合的大小 $x$，那么 $x\in[l,r]$ 的都可行，在里面用组合数选择 $x$ 个。
有多个限制的情况，那么要求 $x$ 在他们 $[l,r]$ 的交集内，依旧用组合数选，但是注意已经有若干个选好了。
而已经选好了多少个数可以枚举，预处理组合数的前缀和，$[l,r]$ 的答案就前缀相减一下即可。

1355F

一种暴力的想法是我一个一个质数问幂次，次数太多。
一种优化方法就是相邻两个质数一起问，但次数还是太多。
首先你知道只需要枚举到平方根，但这还不够。枚举到四次方根，如果当前剩下的 $1$ 则直接结束。否则剩下的因数最少的是一个质数（$2$），次数最多的是三个不同数相乘（$8$），取中间数 $4$ 乘到当前答案上即可。
比较小的质数，因为不同的质因子不超过 $9$ 个，可以先把质数分组使得乘积不超过 $10^{18}$（可以轻松的分成 $5$ 组），然后询问求出哪些质数出现了，再逐个询问个数。

1051E

dp。关键在于如何快速转移。
如果 $1..i-1$ 都已经划分，考虑 $i$，那么如果 $i$ 的位置为 $0$ 就不行，否则长度在 $[|l|+1,|r|-1]$ 的都可以，长度为 $|l|$ 的和长度为 $|r|$ 的要特殊判断，具体方法就用 exkmp 来求出每个后缀和 $l,r$ 的 lcp，然后判断 lcp 的后一个数。

578D

这题好像是 GP of Korea 的弱化版，那题是求 $LCS\geq n-k,0\leq k\leq 3$。下面就讲那题。
求 LCS 可以用二维 dp，记录 $s[1..i]$ 和 $t[1..j]$ 的 LCS。
首先记录 LCS 状态（其中有一个固定），一般可以对于一个固定的 $j$ 记录所有 $i$，但是直接记录状态数量太大，但是可以差分记录 $LCS(i,j)-LCS(i-1,j)$，它的值显然 $\leq 1$，当作二进制状态记录。
这样状态还是太多，但是可以发现所有 $|i-j|\gt k$ 的状态都是没有用的，它们更新到的 LCS 一定一直长度不到 $n-k$。
再记录一下 $i-LCS(i,i)$（$LCS$ 满足至少是 $i-k$），状态数量变为 $(k+1)2^{2k}$。
转移就考虑枚举当前 $t_j$ 是什么，更新二进制状态，转移复杂度为 $O(|\Sigma|k)$。
总时间复杂度是 $O(|\Sigma|k^2 2^{2k})$。

1451F

如果没有 2 操作，那么就是简单的 nim。
考虑能不能把数分个类还是变成类似 nim 的操作。
你发现，因为除了起点，其它的数都在右下角，所以按照 $x+y$ 分层那么这一层的只能减。
考虑和 nim 类似维护每一层的各自的异或。那么你操作的时候这一层就一定会变化，比它大的层你一定想调整成什么就调整成什么（原来的异或和为 $s$，原来的当前数是 $a$，想把异或和调整成 $t$，那么把 $a$ 换成 $s\oplus a\oplus t$ 即可）。
那么，容易想到分成全为 $0$ 和不全为 $0$ 两种，全为 $0$ 只能变成不全为 $0$，不全为 $0$ 可以把第一个不为 $0$ 的组变成 $0$（这个就是 nim，取异或和第一个不为 0 的位把这一位对应为 1 的某个数操作），其它的组可以随便调所以都可以变成 $0$ 就能变成全 $0$ 的组，且游戏不会一直进行下去（每层按照字典序的比较方式每次都减小），结束状态为全 $0$，所以全 $0$ 就必败否则必胜。

794F

用线段树维护区间所有数字的贡献系数标记（标记记录的是数字为 $i$ 的要变成什么）。
求答案的时候就把贡献系数和值乘起来相加即可。
注意标记下传时，父节点的标记是后操作的，对于子节点现在是 $x$ 的，看父节点中 $x$ 会变成什么即可。

811E

由于只有对列的询问，所以可以直接对列建线段树。
记录区间里左右边界的点属于的连通块编号，合并的时候对于中间交界处两边相同的就可以直接并查集合并，最后重标号一下。

725E

如果你加入的硬币不会被他选那么一定没用。
反之如果硬币都被它选了，把这些硬币加起来合并成一个面值，那么之前要选的剩下的还是会选。
不过还可以优化，面值相同的都是等价的，每一次找下一种（预处理）还有的面值尽量买，这样复杂度就变成 $O(c\sqrt c)$。

1380F

考虑没有修改怎么 dp，那么 $dp_i=(c_i+1)dp_{i-1}+c_{i-1}==1dp_{i-2}$，显然可以写成矩阵形式。
有修改相当于是修改一个矩阵，动态 dp，线段树维护矩阵乘积即可。

914G

枚举结果的 $2^i$，再求出 $s_a|s_b=x,s_c=y,s_d\land s_e=z$。
$\sum_i \sum_{x\&y\&z=2^i} f_i\times f_j\times f_k\times (\sum_{s_a|s_b=x,s_a\&s_b=0} 1)(\sum_{s_c=y} 1)(\sum_{s_d\land s_e=z} 1)$。
第一个子集和卷积，第二个直接记录，第三个异或卷积，最后用与卷积合并即可。

325E

$n$ 是奇数，这个图会有两个自环分别是 $0,n-1$，且它们对应的其它入边就为唯一的 $\frac{n-1}2$，而非 $0$ 点只能经过一次，故无解。
考虑 $n$ 是偶数，这个图仍会有两个自环分别是 $0,n-1$。那么 $x$ 和 $x+n/2$ 连的出边都相同，且对应的那两个点也只有这两条入边。
给每个点指定一条出边，使得每个点出边指向的点不同（也就是 $x$ 和 $x+n/2$ 指向不同），就会形成若干个环。
题解说有多个环时，一定存在某个 $x$ 使得 $x,x+n/2$ 不在一个环。考虑反证，如果所有 $x,x+n/2$ 都在一个环，那么它们对应的 $2x,2x+1$ 也在环内，这一定能从 $1$ 开始覆盖到所有点，故只有 $1$ 个环了，马屁吨。
每次选择一个 $x,x+n/2$ 不在同一个环的把出边交换一下，就合并了两个环。

1584F

因为数据范围很小且串很多，考虑直接记录当前最后一个字符是什么，而因为每种字符在每个串最多出现两次，所以可以直接用二进制状态记录这个串匹配的是第几次出现。
每次加入一个字符的时候看这种字符下一次出现位置即可，直接转移难固定顺序，可以用 bfs 的方式转移。

1422E

可以直接 $dp$，设 $dp_i$ 表示以 $i$ 开头的后缀的最小答案，如果能删除就 $dp_i=\min(dp_{i+2},s_i+dp_{i+1})$ 转移（不过 $dp_{i+1}$ 不会删掉它的前面两个，否则和删掉前两个的相同，所以等价于 $s_i+s_i+dp_{i+2}$），否则就 $dp_i=s_i+dp_{i+1}$。
第一种转移不是很容易，不过可以先求个第一个不同位置（显然之前都是同一个数），然后再比大小。由于每次都是在前面加入所以可以反转过来，维护后缀相同的数字个数即可。

1515G

回路上所有点都在 $v$ 的 SCC 中。
由于 SCC 任何两点间都有回路，所以对于 SCC 上的某个回路可以并上一个能到点 $v$ 的回路 $t$ 次，你对于任意两个点的回路都并上来，那么回路上就有 SCC 的所有点。所以 $s,t$ 相同的情况下，SCC 任意一点的答案相同，只需要找出环，不需要考虑是否能到所有点。
那么对于现在的回路，也可以任意两个并起来权值相加，因为两个回路都能到达所有点，可以先走完第一个再走第二个。根据裴蜀定理，能走出所有环长和 $t$ 的 $\gcd$ 的路径。
根据经典套路，求个外向树，所有非简单环都可以用非树边形成的环表出，有个巧妙的证明是 $\sum val(x_i,x_{i+1})=\sum d_{x_i}-d_{x_i+1}+val(x_i,x_{i+1})$，如果是树边后面的值就是 $0$，否则就是包含它的环的大小（即使是横叉边也可以通过乱走得到这个）。

1312G

这个 $S$ 直接求出来总长度可能很长，但是给出形式可以直接建 trie。
然后 dp 求每个需要耗费的时间，一种从父亲的时间 $+1$ 转移，表示后面加一个字符；一种是从某个祖先加当前字典序位置转移过来，预处理初始时所有串的字典序位置，那么当前字典序是这个串字典序减去祖先字典序。
dfs，维护一个单调栈即可。

627D

最小值最大，容易想到二分答案，对符合条件的点染色。
关键在于如何判断，先考虑固定根的情况，那么对于完全被染色的子树显然可以走，其它的子树只能走一个且走完了需要满足答案。考虑 $dp$，满的子树直接加进答案，不满的子树选最大的加入。
对于一个点，选出两个不满的儿子都可以加入，父亲的子树不满的情况一定可以往上到某个点使得父亲子树为空或为满，从一个不满的儿子进来到另一个即可不满的儿子出去即可。

995F

虽然 $d$ 很大，但是最多只有 $n$ 种本质不同的权值。
考虑 dp 离散化后的权值，这样中间有可能有空着，所以要容斥一下（二项式反演）。
求答案的时候用组合数乘一下求和即可。

1493E

最大的答案显然是和 $r$ 最高位相同，比它低的位全 $1$。$r$ 就是全 $1$ 时答案显然就是 $r$。
如果 $l$ 和 $r$ 的最高位不同，那么能达到最大值（选 $[2^x-1,2^x]$）。
如果最高位相同，那么要使得最高位有，所以区间长度一定是奇数。
对于一个偶数 $x$，$x\oplus (x+1)=1$。区间长度很小时特判，由于区间长度为奇数，所以最后的结果只会形如 $x$ 或者 $x\oplus 1$ 或者 $1$。那么 $r$ 是奇数答案显然为 $r$，否则区间长度够长（$\geq 5$）那么答案为 $r+1$。

797F

显然老鼠相对顺序不会改变。
直接 dp，$dp(i,j)$ 表示前 $i$ 个洞有 $j$ 只老鼠的最小距离，那么 $dp(i,j)=\min_{j-c_i\leq k\leq j}(dp(i-1,k)+sum(i,j)-sum(i,k))$，$sum(i,j)$ 表示前 $j$ 只老鼠都到 $i$ 的距离。
把和 $k$ 有关的拿出来，拿个单调队列维护即可。

1558D

它给出这么多，实际是给你了一些不等式 $a_x<a_y$ 或 $a_x\leq a_y$。
根据最后的结果，所有相邻的都是 $a_{i-1}\leq a_i$ （过程中的结果的条件一定比这个弱）。
其实还有一些条件，插入的时候会有 $a_i<a_p$，如果插入之前有条件 $a_{p-1}<a_p$，就把那个符号改成 $\leq$。
重新整理一下题意，就是现在有一个序列 $a'$，相邻两项满足 $a'{i-1}\leq a'_i$ 或 $a'{i-1}<a'_i$，问方案数。
直接做不好做，考虑把两种的形式变成一样，如果 $a'{i-1}\leq a'_i$，可以转化成 $a'{i-1}<a'i+1$，为了不影响其它条件，给 $a'_i,a'{i+1},\cdots,a'_n$ 整个后缀 $+1$，且给 $m+1$。
假设有 $c$ 个是 $<$，剩下 $n-1-c$ 个是 $\leq$。要从 $n+(n-1-c)$ 里选 $n$ 个数给 $a$，方案数为 ${2n-1-c}\choose n$。
求出 $c$ 的大小即可。一种方法是平衡树（要手写，因为和排名有关）维护插入，还有一种是线段树，倒序维护（线段树不方便维护插入），每次删掉一个数再计算贡献（注意留下的前一个对后一个就不会是小于号了）。

241E

所有无法从 $1$ 到达的点都是没用的，所有无法到达 $n$ 的点也都是没用的。
由于是个 DAG，从 $1$ 到达任意剩下的点长度都唯一才行（否则不同的两条再走相同的路到 $n$ 就不合法了）。
这样的好处是说明了如果合法必定存在一个数组 $d$ 使得 $1$ 到第 $i$ 点的唯一距离是 $d_i$，且这个数组容易转移。
由于每条边只和两端点有关，那么一条边 $(u,v)$ 实际上是限制 $d_u+1\leq d_v\leq d_u+2$，直接建图差分约束即可。

285E

恰好且数据范围很小，考虑二项式反演。
用 dp 来计算，不是钦定完美数的位置不需要考虑，最后阶乘计算一下即可。
设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 个数钦定了 $j$ 个完美数，前面一个数没选/选，当前数没选/选的方案数转移就考虑这个数钦不钦定，钦定了的话选前面的还是后面的即可。
最后乘上阶乘二项式反演一下即可。

1519E

极角不同即斜率 $y/x$（$x=0$ 特判）不同。
把点和能到的两个斜率对应的特殊点连边，两个非特殊点能匹配当且仅当有一个公共点和它们都相邻。
发现有特殊点非特殊点很麻烦，而非特殊点只会连两个点，不妨把它删去变成一条边，问题就变成有公共点的两条边能匹配，问匹配方案数。
这个就经典了，每个连通块分开考虑。先求个 dfs 生成树，从下往上考虑每个点向子树的边，如果有偶数条则直接匹配，如果有奇数条则和这个点向父亲的边匹配。只有边数是奇数会剩下一条边。

235E

$\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c d(ijk)$，那么考虑一个约数，尽量让它从 $i$ 中选，其次从 $j$，最后从 $k$。

$$
&\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c\sum_{x|i}\sum_{y|j}\sum_{z|k} [\gcd(i/x,y)=1 \& \gcd(i/x,z)=1 \& \gcd(j/y,z)=1]\
=&\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c\sum_{x|i}\sum_{y|j}\sum_{z|k} [\gcd(x,y)=1 \& \gcd(x,z)=1 \& \gcd(y,z)=1]\
=&\sum_{x=1}^a\sum_{y=1}^b\sum_{z=1}^c \lfloor\frac ax\rfloor \lfloor\frac by\rfloor \lfloor\frac cz\rfloor[\gcd(x,y)=1 \& \gcd(x,z)=1 \& \gcd(y,z)=1]\
$$

如果没有 $\gcd(y,z)=1$ 的限制可以分开来计算，但是如果有，可以枚举 $g=\gcd(y,z)$ 莫比乌斯反演。那么这个 $g$ 和 $x$ 要互质，剩下的可以枚举个 $x$，其它的预处理一下计算（$\lfloor\frac a{xy}\rfloor=\lfloor\frac{\frac ax}y\rfloor$）。

1557E

考虑把国王逼到最后一行，刚开始放在左上角。要保证任意时刻国王不在当前行和当前行上面。
如果某一步国王往下走，说明国王不在下一行，那么你也可以往下走。
如果国王一直左右横跳，则你从这一行左边扫到右边，如果它一直左右横跳，说明它不在下一行，往下走；如果它往上说明搞错了他之前不在下一行，再重新扫；如果它往下，那么你也往下。
由于每次它往下你也一定往下，所以它最多往下 8 次，往上也最多 8 次。它每上移动一次你都要重新扫，而本身会把所有都走一次，所以次数应该是 $2\times 7\times 8$，可以通过。

1430F

一种是某波打完后为了之后不超时的换弹，一种是打某波过程中的换弹。
设 $dp_i$ 表示第 $i$ 波打完后换弹需要的最少子弹数，然后枚举下一次打完后换弹的时间，暴力求中间是否可行和需要的子弹数量。

293B

路径上一定会有 $n+m-1$ 个点，那么 $k<n+m-1$ 一定无解。
且每个点和右下方的任何点都可以形成到达 $(n,m)$ 的一条路径，所以每个数和右下角的数都不同。
直接搜索，每个点不能和左上方的点颜色相同，用二进制状态记录哪些出现的。有一个剪枝就是如果是选一个没出现过的颜色，那么选任何的都是一样的，只需要计算一次。

1153F

不妨变成 $l=1$ 最后答案乘上 $l$。
选择的线段的端点重合的方案数小一个数量级，故不需要考虑。
只需要考虑 $2n$ 个区间端点和随机变量 $x$ 的相对位置。
设 $dp_{i,j,0/1}$ 表示前 $i$ 个点有 $j$ 个左端点还没匹配，当前 $x$ 是否被选了的方案数。
一种就是新增一个左端点，一种是选择之前的一个左端点匹配，一种是放 $x$（要求没匹配的 $\geq k$）。
由于 $dp$ 时钦定了线段间和同一线段两端点顺序，所以答案是 $dp_{2n+1,0,1}\times 2^n\times n!/(2n+1)!$。

1322D

把序列翻一下，要求选一个不降的子序列。
设 $f_{i,j}$ 表示攻击力为 $i$ 的有 $j$ 个人的最大收益，转移就是 $f_{i+1,\lfloor j/2\rfloor}=\max(f_{i,j}+\lfloor j/2\rfloor\times c_i)$。每次加入一个新的人更新这个数组。
直接暴力是 $O(n^3)$ 的，不过可以发现由于这个式子的特殊性，这一层对 $n$ 个 $j$ 产生影响，到下一层就变成 $\lfloor n/2\rfloor$ 个，再下一层 $\lfloor n/4\rfloor$ 个……，所以只会影响 $O(n)$ 个位置的值。故总复杂度 $O(n^2)$。

1146G

这个数据范围容易想到网络流。
一个是代价一个是收益不好做，先假设所有的高度都是 $h$，加到初始答案，如果最后高度是 $x$ 则代价为 $h^2-x^2$。
给每个点往外连 $h,h-1,h-2,\cdots$ 高度对应的代价形成一条链。
对于每个分区限制新建一个点，在区间内的点 $x+1$ 代价的边后的点往新建点连 $+\infty$，新建点往 $T$ 连 $c_i$。
跑个最小割，从初始答案中减去即可。

986E

如果差分不破坏性质，能差分就差分。
这题也是一样，$calc(x,y,w)$ 可以变成 $\frac{calc(1,x,w)\times calc(1,y,w)\times \gcd(w,val_z)}{calc(1,z,w)^2}$（其中 $z=LCA(x,y)$），因为逆元一定存在。而且 $w$ 也可以分解成若干个质数的幂次。
由于询问可以离线，你直接把询问挂到对应的点上。现在关键在于如何快速维护，由于 $\gcd$ 本质是幂次取最小值，所以要求的是到根路径上所有数这个 $p$ 的幂次和当前数取最小值求和。
由于询问只有 $1e5$，你可以处理出所有不同的要询问的 $p$ 的最高幂次，而幂次总和最多只有 $\log$，暴力维护所有 $p$ 幂次的个数，查询直接暴力查询（为了使得总复杂度是 $\log$，操作直接 $O(1)$，询问只枚举比它小的，比它大的用总个数-比它小的计算）。

1185G2

这题的关键点在于顺序是重要的。
考虑先分开计算一种歌选出 $x$ 首使得总和为 $t$ 的方案数，类似背包转移即可，这部分复杂度是 $O(n^2T)$。
然后现在要考虑合并，先把三种分别有 $x_1,x_2,x_3$ 合并的方案数算出来，这个直接 dp 即可。
然后暴力思路是直接枚举三种个数和时间，这个复杂度显然太高。先合并两个也不行，这样复杂度是 $O(n^2T^2+n^3T)$ 的。
可以直接在 dp 的时候就合并两个，合并还是记录两种的数字个数，只是记录总时间，这样复杂度就是 $O(n^3T)$，应该有 $1/27$ 的常数。

444E

虽然形式比较奇怪，但是本质上还是最小值最大，所以先考虑二分答案 $mid$。
二分完之后就变成存在一个序列 $p_i$ 使得所有 $g(i,p_i)\geq mid$，$g$ 对应的是最大值，也就是不存在 $(i,p_i)$ 路径上的边都 $<mid$。
把那些 $\geq mid$ 的边拿出来，剩下的缩起来只保留点数和其中的 $p$ 之和，每个可以和不同块的匹配，要求每个被匹配的不超过 $p$ 之和。
从第一块开始，每到新的一块，尽量把这一块填满（把以前放到其它位置的都放到当前位置），这样一定是其它占用它能占的最少的方案，然后再占其它的。只需要记录之前有多少个就可以判断。

671C

区间越短答案越大。具体来说，$l$ 相同时，$r$ 越大，$f(l,r)$ 越小。
那么对于每个 $i$，存在一个 $r'$，使得 $r\geq r',f(l,r)\leq i$。
考虑 $i$ 减小会如何变化，$\gcd=i$ 的就不能在一个区间内了，$[l,r]$ 区间外最多只能有一个 $i$ 的倍数。
假设 $i$ 的倍数的位置分别是 $x_1,x_2,\cdots,x_k$，那么 $l\gt x_2$ 的时候直接无解，记为 $r$ 至少是 $n+1$；$x_1\lt l\leq x_2$，$r$ 至少为 $x_k$；$l\leq x_1$，$r$ 至少是 $x_{k-1}$。
对于每个 $l$ 维护最小的满足条件的 $r$，则 $r$ 对应的序列是单调不降的。所以这个区间 $\max$ 可以变成线段树上二分后区间覆盖。而答案可以表示为 $\sum_i [f_{l,r}\geq i]$，线段树维护一下区间取 $\max$，全局求和即可。

1158D

网上的题解不知道在写什么。。。
看了看官方题解，先选一个凸包上的点（可以取 Down-Left，不需要真的建出凸包）。
每一步保证当前的点在剩下的点的凸包上，如果往右就选剩下极角最大的点，否则取极角最小的点。发现这样一定在剩下的凸包上且剩下的点怎样连边都不会碰到之前的点。

536D

和图的具体形态无关，只和 $1,n$ 到它的距离有关。先跑两次 dijkstra 求出每个点到 $1,n$ 的距离。
然后把这个距离离散化一下，到任意时刻，取走的一定是距离 $1$ 不超过 $x$ 或距离 $2$ 不超过 $y$ 的。
容易想到直接把这个记录到状态里去 dp，关键问题在于转移时怎么求出新增的点权。
这个可以前缀和预处理，还是把这两个记录进状态处理出 $s$。假设操作 $y$，那么新增 $s[x][y]-s[x][y']$。

864F

字典序最小不好做，一般字典序最小路径会倒着做。
而数据范围很小，考虑直接枚举 $t$ 建反图倒着做，先求出哪些点能到达 $t$，然后每个点选能到达 $t$ 的编号最小的相邻点连边。
非成环部分形成内向树，把边反向，从 $t$ 开始 dfs，维护一个栈。把询问离线下来，就可以通过栈求出答案。

1510B

reset 显然是到达了某个关键状态后按的。直接建图难点在于：到了关键状态后还能继续走；处理 reset。
由于最终目标是你要到达所有的关键状态至少一次，所以每个关键状态可以建一个对应的新点替代连原先的点要连的边，$S$ 向新点建 $(1,0)$ 边，原先的点只连到 $T$ 的 $(1,0)$ 边（这样的正确性在于走的状态不会成环）。
reset 相当于回到原点，给原点多次出发的机会，每次出发需要花 $1$ 代价（第一次出发不需要代价，最后减去）。建一个新的 $S'$ 替代 $S$ 连原先 $S$ 连的边，$S$ 向 $S'$ 连 $(+\infty,1)$ 的边。
跑个最小费用最大流（注意答案要 $-1$），构造方案就看每个新点连出去的最后从哪出了，变成若干条链，依次输出每一条即可。

587E

线性基不好做区间修改，考虑变成维护相邻两个数异或（类似差分），那么就变成两个单点修改了。
线段树维护区间的线性基，合并直接把一个插入到另一个。询问的时候再看区间第一个数能否插入，求出线性基大小后求个 2 的次幂输出即可。

1067C

牛逼构造题。只考虑 $n\geq 9$。
考虑一个 $3$ 行，$(2n-1)/3$ 列矩阵的 $i+j\equiv 0\pmod 2$ （$i,j$ 从 $0$ 开始）。
那么这样能把这整个矩阵填到每行只缺 $2$ 个。然后它会往上往下，每往上一层就少了最前最后两个。忽略常数项，$2\sum_i(2n/3-4i)+2n/3>n^2/9$。

682E

看这个题面形式，容易猜到就是先求出面积最大的三角形然后坐标扩展两倍（下图红色三角形为最大三角形）。

发现如果有任意大三角形外的点，拿出它和红色三角形对应的另一侧的两点，面积一定比红色三角形大，矛盾。
现在问题就是找出这个红色三角形。由于三角形的三个端点一定在凸包上（假设某个 $x$ 不在凸包上，考虑另外两个点，相当于求到这个直线的距离，最远的一定在凸包上），所以枚举第一个，枚举第二个的同时双指针第三个即可。

633G

先求个 dfs 序，把树拍平了。现在变成区间加一个数区间询问。
由于数据范围很小，且 $(n+q)m\leq 2\times 10^8$，所以考虑直接线段树上维护 bitset 表示区间出现过的数字，修改的时候直接平移，询问的时候 or 起来再和质数对应的 bitset 做一下 and。
时间复杂度 $O((n+q)m\log n/w)$。

601E

考虑只加怎么做，只加的话每加入一个可以暴力更新背包（维护 $w$ 之和不超过 $x$ 时 $v$ 之和最大值）。
背包是不支持删除的，撤销是可以的。所以可以在外面套个线段树分治。
时间复杂度 $O(k(n+q)\log q)$。

814E

最短路唯一而不是最短路长度唯一，这说明最短路树（bfs 树）是唯一的。
如果知道了最短路树，那么其它边只能在同层之间连。
$i$ 的最短路 $\geq i-1$ 的最短路说明 $i$ 要么和 $i-1$ 同层，要么在它下一层。
这一层的方案只和下一层有多少点有关，要选出一个一些边（有序）给下一层的点连，再求出剩下两两连边的方案数。
根特殊考虑。对于其它层，可以直接设 $g[t][x][y]$ 表示下一层有 $t$ 个点，这一层有 $x$ 个 $2$，$y$ 个 $3$ 的方案数，每次要选一个给下面一层的就是选一个 $2$ 或一个 $3$ 减去 $1$。
当 $t=0$ 时就说明要同层匹配了，每个点都有一个父亲，所以实际度数要减 $1$。同层匹配不考虑顺序，先考虑把那些 $2$ 弄没了。考虑第一个 $2$，它可以选另外一个 $2$ 或一个 $3$ 匹配，继续转移。
当 $t=0$ 且 $x=0$ 此时只剩 $3$ 了，即每个度数都为 $2$，会形成若干个环，枚举第一个所在的环的大小 $c$，组合数算一下（注意翻转还是同一个，两个点的环不合法），方案数为 $(c-1)!/2$。
现在就考虑把这些合起来，设 $f[i][j]$ 表示到第 $i$ 个点，$i-j+1,i-j+2,\cdots i$ 在同一层的方案数。转移就枚举下一层的点数，用 $g$ 计算一下这一层的方案数，转移下去即可。
最后计算答案的时候别忘了还得更新最后一层内部连边的方案数。

455E

这个 $i$ 相当于是你还剩下的步数。假设最后 $j=j'$，那么可以得到所有 $a[j'],a[j'+1],\cdots,a[i]$ 各自乘上非 $0$ 系求和，要求系数之和为 $n$。
如果你知道了最后的 $j'$，那么你一定会在中间 $a[j]$ 最小的位置停留最长时间（系数最大）。且如果最小的位置不是 $j'$ 那么这个 $j'$ 一定不优。
所以一定可以转化成先做若干步 $j-1$，然后 $j$ 一直不变，答案就是 $pre[j]-pre[j']+a[j']\times (i-(j-j'))$，把无关项分开就是 $pre[j]+(a[j']\times j'-pre[j'])+a[j']\times(i-j)$。
这是若干一次函数的形式，但是它还有 $j'$ 的限制（$i\geq j-j'$ 即 $j'\geq j-i$）。所以需要维护凸包或维护树套树（线段树套李超树）。
树套树就比较常规（不知道空间行不行），这里说一下维护凸包，其实直接线段树维护也是不行的，但是由于它是在最后加入，所以可以更新线段树区间内已经满的区间（显然只会满一次），询问的时候二分；
或者觉得这个东西显式建出来很难看，可以考虑对于每个 $i$ 维护后 $1,2,4,\cdots,lowbit(i)$ 个点的凸包，转移可以直接转，询问类似于树状数组跳。这样维护的总点数是 $O(n\log n)$ 的，总时间复杂度也是 $O(n\log^2 n)$。

8E

不大于取反串说明第一个位置是 $0$。
考虑枚举前 $\lfloor n/2\rfloor$ 位，假设为 $x$。以下先考虑 $n$ 是偶数的情况。
逆序串和逆序取反串只有一个有用，如果最后一个位置为 $0$ 则只考虑逆序串，否则考虑逆序取反串，两种分别计算个数。
如果是逆序串，那么所有不合法的方案是：之前位相同，第 $t$ 位是 $1$，翻过来那边是 $0$，后面位任意。所以对应的不合法的方案数就是 $x$。
如果是逆序取反串，不取反时不合法的方案数是 $x$，那么把后一半取反方案数应该还是不变。
$n$ 是奇数要特殊考虑中间的位置，逆序串中间的数字随意（方案 $\times 2$），逆序取反串如果两边正好相反那么中间只能填 $0$（方案 $\times 2-1$）。判断一下是不是已经够了，如果够了就再枚举后面的位然后一个一个判断。

1421E

区间 dp 出合并成一个数，最大和最小是什么。转移很容易，但是这样是 $O(n^3)$ 的。
但是无论怎样最后所有数的符号都是 $\pm 1$，看看最优解的符号有没有什么规律。
第一步操作后，系数和减少了 $3$。看看所有的系数和 $\bmod 3$ 有什么性质，$n=1$ 一定是 $1$，$n>1$ 时每个数字都是 $\bmod 3=1$，那么合并了之后还都是 $\bmod 3=1$。所以任何时候都是 $\bmod 3=1$。
那是不是所有满足这个条件的都可以呢？$n=3$，$1,-1,1$ 的系数就不行，因为第一步就一定会让某两个相邻的系数是相同的。那是不是满足 $\bmod 3=1$ 且有相邻的系数相同的条件就可以呢？
答案是可以。证明可以考虑归纳，$n=1,2,3$ 显然成立。
对于相邻相同第一个长度 $\geq 2$ 的连续段 $x,x+1,\cdots,x+k-1$，如果 $x>1$ 或 $k=2$，合并 $(x,x+1)$，就和 $x-1$ 或 $x+2$ 相同了，归纳成立；否则如果 $k=n$ 且由于此时考虑 $n\geq 4$，所以合并 $(x,x+1)$ 后还有相同的；如果都不满足则说明 $x=1$ 且 $k<n$，合并 $(x+k-2,x+k-1)$。

773D

这个题意写的很奇怪，意思是原图是个完全图，有边权。对于每个点当根，要选个生成树，使得每个点到根的边权最小值总和最小，输出这个总和。
容易想到一种类似于 Prim 求最小生成树的做法，但很不幸这是错的。如果有一个很小的边，其它都可以接在它下面那么你可能会先尽全力到那个点，剩下都让它去到达。
考虑一条最小的边，由于整个图连通，故一定有一个端点通过一条路径连到根，那么剩下的没经过的点都可以通过这个到根（因为是完全图）。
所以到最小边一定是一条链，链上的点算到根路径上最小的代价，其它点算最小边的代价。
对于链上的，认为代价是到根路径上最小值-最小边代价，要让总代价尽量小。可以发现，这条链上不会有相邻的都不是前缀最小值的边（不然你可以变成一条）。
然后再变换一下，对于一条边，可以花再花它的代价走到任意点（从 $x$ 开始的所有出边，可以和最小值*2 取 min）。重新计算原图的边权，跑个最短路就可以求出链的权值。

1491G

排列会形成若干个环。考虑只有一个环怎么做。
假设环形如 $a_1\rightarrow a_2\rightarrow \cdots a_n\rightarrow a_1$（$n>2$），每次交换 $a_n$ 和 $a_{n-1}$ 的出边，并且 $n$ 减少 $1$。最后会使得所有数都归位了，且 $a_1$ 和 $a_n$ 是反着的。发现此时再归位并不容易，考虑开始的时候就把两个反过来。
开始的时候，先交换 $(a_n,a_1),(a_1,a_2)$，环变成 $a_2'\rightarrow a_1\rightarrow a_3\rightarrow a_4\cdots\rightarrow a_{n-1}\rightarrow a_n'$，就可以用上面的方法归位。但是这样对于长度为 $n$ 的环需要 $n+1$ 次，有多个环就不行了。
其实一个环上有两个反面的都是可以的（不一定相邻），因为你可以每次交换靠后和它前一个位置，环长减少 $1$ 且两个反面的更近了，一定到某一步会相邻，就可以和上面一样做。也就是说 $n\geq 2$，恰好有两个反面的需要的次数就是 $n-1$。
那么每次你可以花 $1$ 的代价把环长分别为 $a,b\geq 2$ 的并起来，然后再花 $a+b-1$ 的代价把环归位。这样你可以每次花 $a+b$ 的代价删去两个环，最后如果还有多余的环，当作一个环长为 $1$ 的环和它一起归位即可。

958F3

这个数据范围不大，可重集容易想到生成函数。
对于有 $a$ 次出现的数，对应的生成函数为 $1+x+x^2+\cdots+x^a$。
把若干生成函数乘起来直接分治 FFT 即可。

1028F

由于直线过原点，故两个点到原点的距离必须相同。
两个点关于图像对称当且仅当两个点的中点在直线上。
把任意两个到原点距离相同的求一下中点然后化成最简比例存一下。
询问的时候也化成最简比例询问即可。而到原点距离相同的点整点数量不超过 $144$，加入删除可以直接暴力。

1400F

感性理解一下，x-prime 的并不多。因为当 $x>1$ 时 $1$ 就不能出现，猜一下应该是 $x=19$ 时答案最大，跑个暴力就发现只有不到 2500 个。
对 $x$ 的 x-prime 建 AC 自动机，然后就要求不出现 AC 自动机上的作为子串，直接 dp 记录当前的 $i$ 和 AC 自动机上的节点编号即可。

1487G

不存在长度为奇数且大于 $1$ 的回文串也太经典了，这个只需要考虑长度为 $3$ 的。
没有 $c$ 的限制就可以直接 dp 了，但是有 $c$ 的限制，考虑容斥，容易发现最多违反两个限制。
设 $dp[i][u][v][x][y]$ 表示当前在第 $i$ 位，第一种特殊字符用了 $u$ 次，第二种特殊字符用了 $v$ 次，倒数第二个字符是第一种/第二种/其它，最后一个字符是第一种/第二种/其它的方案数。
设当前新加的字符是 $z$，$z=0/1$ 只有一种选择，否则 $24$ 种选择（如果 $x=z$ 只有 $23$ 种）。
不满足条件的是一个后缀，求个二维后缀和。最后容斥合并即可。

113D

没看懂网上的题解。
枚举终点 $x$，设 $f(i,j)$ 表示当前在 $(i,j)$，到终点的概率。那么 $f(i,i)=[i=x]$。
方程可以表示为 $Ax=B$ 的形式，其中 $B$ 是个列向量，不同终点改变的只是 $B$。
不妨把 $B$ 变成一个矩阵的形式（把多个询问按列排在一起），最后只需要询问 $(a,b)$ 这一行即可。
至于怎么消元？类似的把 $AB$ 接起来，把前 $n^2$ 列消完即可（可以认为是现在每个方程对应的是一个行向量）。

1366F

$k$ 很大一定不是简单路径，容易想到后面会绕着一个环走。而一直绕着环不如到了环上的最大边之后反复横跳这条边。
特殊处理 $k\leq m$ 的答案。当 $k>m$ 时，就可以通过某条路径到达一条边，之后在这条边反复横跳（之前的边都比它小，不过即使不满足也没关系，一定比之前到最大的就开始反复横跳劣），可以处理出这种方案关于时间的函数 $f_i(t)=k_it+b_i$。
求出 1 号点到任意点更新 $i$ 次的最长路（bellman-ford），对于每条边斜率都相同，选截距最大的，求个凸包后再计算答案即可。

1257G

首先如果所有 $p_i$ 两两不同，容易想到选那些 $deg(x)=\lfloor \frac n2\rfloor$ 的，这样就一定不存在一个为另一个因子的情况。
$p_i$ 有相同的情况也差不多，还是取 $deg(x)=\lfloor \frac {deg(m)}2\rfloor$ 的，证明可以看 luogu 题解（不过有地方写错了，对称链的 1. 是 $deg(d_1)=deg(m/d_h)$），大概就是可以分成若干个不交的链（对称链），且每个对称链只能选一个，且每条链恰好有一个 $deg(x)=\lfloor \frac {deg(m)}2\rfloor$ 的点，就说明这样取是最大的。
求 $deg(x)=\lfloor \frac {deg(m)}2\rfloor$ 的个数可以通过生成函数求对应项系数，分治 NTT 即可。

703E

根据表格 2，可以知道 $10^{12}$ 以内因数最多的数字是 963761198400，有 6720 个因数。
可以直接设 $dp[i][j]$ 表示现在考虑到 $a_i$，与 $k$ 的 $\gcd=j$ 的最小数字个数（其次是元素总和）。
对于每个数 $a_i$ 和 $k/val_j$ 取个 $\gcd$ 再乘上 $val_j$ 求出新的下标转移。

103E

$n\leq 300$ 很有意思，要么是 $O(n^3)$ 要么就是网络流。
子集并的大小比子集个数大的条件感觉非常奇怪，不知道如何下手。它对询问的影响是子集的并不可能比子集个数小，不需要考虑这种情况。
现在想让权值和最小，能不能用一种方法，使得子集的并比子集个数大的权值一定不会是最小的。
不妨这样，让点也有权值 $+\infty$，集合加上权值 $-\infty$，这样如果子集的并比子集个数大，权值就一定多了至少 $+\infty$，不需要考虑了。
这还是不好处理，总不能直接状压枚举然后二进制求并来找哪些出现过。由于要权值最小，可以转化成选择了子集就得选里面的点，不会单独选择不被子集包含的点（这样只会凭空加上 $+\infty$）。
选择了 $x$ 就必须选择 $y$，求最小权值。建最小权闭合子图即可。

1198F

这什么哈人题。。。
一个数里不同的质因数个数很少，所以可以直接 random_shuffle，然后从前往后取尽量少的使得 $\gcd$ 变成 $1$（如果 $\gcd$ 是当前数的约数就不用选当前数），然后把剩下的给对面看行不行。
因为随着 $n$ 增加，$\gcd$ 变小的速度很快，而 $n$ 很小的时间又很充裕，所以这样就可以了。

599E

数据范围这么小，考虑状压 dp。
设 $dp[u][s]$ 表示以 $u$ 为根，子树里的状态为 $s$ 的方案数。
直接增量转移可能会出问题，因为子树之间本身是无序的。要钦定一个顺序，每次加入这个点为编号最小的点的子树。

639E

这种乍一看不好求的顺序，考虑一下调整。
固定 $c(c>0)$，假设之前已经经过了 $t$ 秒，一种是 $p_i(1-\frac{c(x+t_i)}T)+p_j(1-\frac{c(x+t_i+t_j)}T)$，另一种是 $p_j(1-\frac{c(x+t_j)}T)+p_i(1-\frac{c(x+t_j+t_i)}T)$。
如果不需要调整，即第一种 $\geq$ 第二种，那么整理一下变成 $-p_it_i-p_j(t_i+t_j)\geq -p_jt_j-p_i(t_j+t_i)$，再整理变成 $p_it_j\geq p_jt_i$，即 $\frac{p_i}{t_i}\geq \frac{p_j}{t_j}$，当然相等的其实可以随便排。所以最佳做题顺序和 $c$ 关系不大（相等的可能会有关）。
先考虑简单点的情况，还是固定 $c$，如果 $p_i\lt p_j$ 且 $p_i(T-cx_i)\gt p_j(T-cx_j)$。为了使得任意最佳做题顺序都满足，所以 $\frac{p}{t}$ 相等的时候让 $i$ 排第一个，$j$ 排最后一个。
把所有数按照 $p$ 的值分组，一组一组做即可。而这个 $p_i(T-cx_i)\gt p_j(T-cx_j)$ 条件可以变为 $c(p_ix_i-p_jx_j)\gt T(p_j-p_i)$，解出来就是 $c\gt$ 一个数或 $c\lt$ 一个数，二分一下即可。

708D

先正常建图，流量 $>0$ 从超级源连向当前点流量，否则从当前点连向超级汇流量绝对值。接下来考虑每条边。
如果 $f\leq c$：
减小 $f$：花 $1$ 的代价减少 $1$，最多减少 $f$，故连 $(v,u,f,1)$。
增加 $f$：当流量 $\lt c$ 时可以花 $1$ 的代价增加 $1$，最多增加 $c-f$，故连 $(u,v,c-f,1)$。当流量 $\geq c$ 时可以花 $2$ 的代价增加 $1$（同时增加 $f,c$），故连 $(u,v,+\infty,2)$。
如果 $f>c$：最终在 $c,c+1,\cdots,f$ 之间需要花的代价都为 $f-c$，不妨先把 $c$ 扩大到 $f$，花 $f-c$ 的代价。
减小 $f$：当流量 $\gt c'$（原先的 $c$）时可以花 $0$ 的代价减少 $1$，最多减少 $f-c'$，故连 $(v,u,f-c',0)$。也可以花 $1$ 的代价减少 $1$，连 $(v,u,c',1)$。还可以花 $2$ 的代价增加 $1$，连 $(u,v,+\infty,1)$。
从原先汇点到源点连 $(T,S,+\infty,0)$ 直接从超级源和超级汇跑个最小费用最大流（对于 $S,T$ 来说是最小费用可行流），就可以了。

607D

子树中每个点的贡献系数是到子树根上每个点的 $sz$ 乘积。
类似于前缀和优化，到子树根的 $sz$ 乘积=到根的 $sz$ 乘积/子树根的父亲到根的 $sz$ 乘积。记录到根的 $sz$ 乘积为 $pre_u$。
那么就是每个点 $w\times pre$ 最后再除掉 $pre_{fa_u}$。维护一下所有点的 $w\times pre,pre$。
先把整棵树建出来，然后加点的时候对子树修改一下贡献。

500F

直接做显然是 $0/1$ 背包，但是 $0/1$ 背包不支持删除。一种方法是使用线段树分治，还有一种是双栈模拟队列。
之所以是队列是因为所有区间等长。具体做法是每次插入到第二个栈，弹栈的时候弹第一个栈。如果第一个栈空了则暴力重构，把第二个栈的插入过去，第二个栈清空。询问的时候直接扫描一个，和另一个一起更新答案即可。

924E

如果到某一步使得当前放了就在 $\geq l$ 的位置，就一定开始放剩下的重要的箱子（按照高度从小到大）。
可以发现，一定存在最优方案能使得重要的箱子都排成一个连续段。然后你会选若干个当底座来垫高，剩下的从小到大放。
这样还是不好做，其实有结论：把所有关键的按照高度排序后，一定是选后缀中的若干个来垫高，剩下前缀从小到大放（也就是在说不会存在一个高度更长的放里面了而高度更短的拿来垫，因为这样交换一下总长不变且一定不会更劣）。
每次把最大的关键的加入 0/1 背包，然后选 $\geq l$ 最小的可行的位置，从小到大放看能放几个即可。
预处理一下长度为 $x$ 会选前多少个，0/1 背包用 bitset 优化即可。

936C

构造一个比较小的矩形然后再平铺，具体来说，如果 $c$ 的 $\gcd$ 不为 $1$，那么可以把所有 $c/=g$，最后再平铺 $g$ 次。
两个矩形放在同一行首先要求 $w$ 相同，其次每一行的 $h$ 得相同。
每一行的放法也差不多，考虑第一行，把所有的都除以他们 $\gcd$，再判断每一行是否都是这个的若干倍，再求出这个倍数的 $\gcd$，这个 $\gcd$ 的约数个数就是答案。

620F

这个 $f(i,j)$ 属实典中典，先变成前缀，再通过如果 $2|x$，$x\oplus (x+1)=1$ 来优化求的速度。
然后用回滚莫队，每次插入一个数，求两个数异或的最大值，还有回滚一下就可以了。
时间复杂度 $O(n\sqrt m\log V)$。

1044F

首先有一点，由于你后面求的还是 dfs 树，所以一定不会出现横边。如果你加入的边出现了在原树上的横边则这个根一定不好。
且如果没有横边就一定能走的出来这棵树。进一步发现，如果你连成一个环，考虑以哪些点为根会形成横边。
可以发现，形成横边当且仅当到环上的非端点比到两端点要早，也就是只能是环上非端点和它们往环外子树上的点。换句话说只有两端点对应的外子树和它们自己合法，求出两个对应的 dfs 序区间，把剩下的标记一下即可。
最后用总数减去不好的即可求出答案。

477D

先求第一问，考虑设 $dp[i][j]$ 表示这一段开头在 $i$，长度为 $j$ 的方案数。转移就对于 $i+j$ 看最短的 $\geq$ 前面一段的（是一个后缀），更新即可。这个转移点可以预处理，预处理任意两个位置开头 lcp 长度即可。
对于第二问，可以一样的求，注意最后求答案要加上最后的值，$dp$ 只需要记中间的输出次数。

1109E

对于和模数不互质的部分，直接记录这些因子出现次数。
对于互质的部分，可以直接求逆元（exgcd）。

1613F

直接做不能很好的记录状态，考虑容斥。
显然每个点最多和其某个儿子不满足条件，所以这样会形成若干条链。一条链要求从上到下颜色依次 $+1$。
那么可以给每条链上排个相对关系，且这个相对关系唯一确定了每个点的权值。也就是分配颜色的方案数和链的条数有关。
链的条数也就是 n-不合法的边数。所以只需要求出有 $i$ 条不合法的边的方案数。这个对应多项式 $\prod_u (tot_ux+1)$ 的 $i$ 次项系数，其中 $tot_u$ 表示 $u$ 的儿子个数。
一种方法是直接分治 NTT，还有一种牛逼 $O(n\log n)$ 做法，先把 $tot_i$ 相同的放一起，直接二项式展开。设现在每个多项式的度数分别是 $deg_1,deg_2,\cdots,deg_n$（即 $tot_i=x$ 的点数为 $deg_x$）。从后往前直接暴力乘起来，那么复杂度是 $\sum_{i=1}^k ideg_i$。发现这个不超过 $n$，因为这个代表的就是原图每个点儿子数量之和。之间这样乘复杂度是 $O(n\log n)$。

763E

直接回滚莫队应该是可以做，加个并查集，这样复杂度是 $O(n\sqrt n\log n)$。
不过 $k$ 很小，可以线段树记录区间里前后 $k$ 个数，合并的时候对于每条边并查集合并，最后重标号即可。

480E

维护每个点往上的长度。
倒着操作，操作造成的向上长度的贡献可以 $O(n)$ 处理，而询问也可以枚举每一行，对每个点维护每个左边有多少个往上的长度达到 $ans+1$ 的（称为合法的）。
如果答案增加了 $1$（最多增加 $1$），对原先所有的合法的恰好是 $ans+1$ 的暴力修改一下即可。
维护左边有多少个合法的可以用线段树。

418D

没看懂怎么用直径做的。
到两点的最短距离最长的值，首先要从两点路径的中间分成两部分，然后两部分分别求最长的最短距离再求最大值。
倍增来维护，如果 LCA 恰好是中点，通过倍增预处理的两条链的答案求个最大值即可；如果不是，那么一边上面会属于另一边，所以还得反过来记一个。
也就是倍增维护每个点往上的一条链上向外的子树（不包括链尾的）的最大深度-/+链上向外点的深度的最大值，容易直接合并。

698D

只需要对于每个怪都判断一下即可。
先枚举谁打了最后一个怪，那么它打了路径上的所有怪之前应该都被打了，再枚举谁打了路径上倒数第二个怪（反正都得有人打），依次类推，复杂度应该是 $O(kk!)$。
再加上外面的 $O(n)$ 就是 $O(nkk!)$。

524F

一定是先移位完再加入。
要加的括号一定是堆在最前面和最后面最优，用总和与最小前缀和求出要加多少左右括号。
假设有 $x$ 个左括号，$y$ 个右括号，$x\geq y$，则一定可以循环移位只补 $x-y$ 个右括号在末尾，证明很简单，把最小前缀和拿出来放到结尾即可。同理 $y>x$ 也一定可以循环移位只补 $y-x$ 个左括号在开头。
先按照长度比较，之后比较字典序可以用后缀数组。

163D

感性理解一下，不同的方案并不多。
不过直接递归还是复杂度太高，考虑剪枝：
$a,b,c$ 顺序无关，不妨钦定 $a\geq b\geq c$，进一步有 $a^3\geq V,ab^2\geq V$（可行性剪枝）；
而由于 $bc=V/a$，那么 $S=2a(b+c)+2bc\geq 4a\sqrt {bc}+2bc=4a\sqrt {V/a}+2V/a$，如果第一步就比当前最优答案大就不需要考虑（最优性剪枝）。

1616F

要么两两不同，要么全部相同这个条件要表示出来。
只有 $3$ 种颜色，考虑 $\bmod \ 3$ 分析。如果一个三元环和为 $0$ 则合法。
现在就变成有若干（$\leq m$）个未知数，问有多少种方案满足所有式子。
可以直接高斯消元，三元环个数是 $O(m\sqrt m)$ 的（三元环计数），复杂度是 $O(m\times m\sqrt m\times m)$ 即 $O(m^3\sqrt m)$。这样其实足以通过，不过可以用 bitset 优化三进制异或，复杂度变为 $O(m^3\sqrt m/w)$。

1088F

代价点上也有边上也有，不好做。不过点上的限制又是相邻边的数量 $\times$ 权值，不妨把权值直接放到相邻的边上。现在每条边的权值变成 $a_u+a_v+\lceil dis(u,v)\rceil\times \min(a_u,a_v)$。
还有一个奇怪的限制，除了权值最小的，相邻的有一个比他小。不妨以权值最小的为根，每个点往相邻的权值比它小的走，必须走到根（否则走不动的点就不满足条件），也就是每个点的父亲的权值都比当前点小。
每个点在新树可以选任意比它小的当父亲，但是可以发现，如果选的不是祖先，那么选它们的 LCA 就会在祖先链上且会使得边的权值更小。
而这个 $dis$ 恰好和 $\log $ 有关，所以可以直接倍增求到祖先连边中权值最小的。

407D

设 $dp_{x,l,r}$ 表示下边界在 $x$，左右边界在 $l,r$，上边界最小是多少。
那么和最大正方形类似，先求 $dp_{x-1,l,r},dp_{x,l,r-1},dp_{x,l+1,r}$ 的最大值，现在没有考虑的只有 $x,l$ 和第 $r$ 列的影响与 $x,r$ 和第 $l$ 列的影响，这个可以枚举 $x$ 的时候一起维护每一列某个值最后一次出现的行数。

325D

即存在一组闭合曲线把圆柱分成上下两部分。先把整个网格图在右边复制一份。
每次加上一个点，如果形成了闭合曲线，那么它一定在闭合曲线上，则 $(x,y)$ 和 $(x,y+c)$ 一定连通（闭合曲线不会穿过环两次，否则本身就存在闭合曲线）。
判断也是类似判断，看两个点八连通的有没有在同一个集合内的即可。

1267F

各自的个数得满足限制，剩下的一定是一个左部点一个右部点，所以要求 $|a|\leq m-1,|b|\leq n-1$。
然后就直接贪心，度数为 $0$ 的就是现在的叶子节点，拿出来，和另一部的开头连边，那个点度数 $-1$。
度数为 $0$ 就可以加入到叶子节点，如果另一部的序列为空了就随便连。

1411G

先要求出 $sg$ 值，根据经典结论，$sg$ 值最多只有 $O(\sqrt m)$，因为一个 $sg$ 值为 $x$ 的点至少有 $x$ 条出边（对于求 $sg$ 其实不需要，因为出边总和只有 $m$ 条，可以直接暴力跑）。
Alice 输当且仅当选出的点的 $sg$ 值异或和 $=0$，然后设 $f_x$ 表示当前还没结束且当前异或和是 $i$ 的概率，就枚举 $y$ 转移到 $f_{x\oplus y}$ 即可（还有 $\frac 1{n+1}$ 的概率直接结束）。高斯消元解方程即可。

480D

任意时刻，一定是下面的区间包含上面的区间，也就是下面的区间 $r$ 更大，$l$ 更小。
直接记录有哪些还在栈中不容易，考虑倒过来记录栈顶和当前的总重量限制。
把所有区间按照 $r$ 从小到大，其次 $l$ 从大到小排序。每个区间可以从之前选若干个互不相交的且都被当前区间包含的 dp 值转移过来，这个可以直接再写一个 $dp$ 来转移。
时间复杂度 $O(n^2S)$。

758E

深度大的边是否合法与深度小的没有关系。
对于一条边，要修改的时候还是得修改子树里的。
从下往上，如果有一条边不满足就从子树里选减少能减少的深度最大的边。
可以用堆启发式合并来维护可行的边。

1004F

区间 $or$ 固定了左/右端点后只有 $\log V$ 种不同的。
对于一组询问，可以把它从中间分开，求出后缀和前缀的，就知道哪些要跨过中间。剩下的递归成两部分即可。
有修改就套个线段树，线段树节点上维护前后缀的 or，合并就直接当成 $\log V$ 个数来合并就可以了。

1582G

不同的质因子独立，先分开。分开之后就是每个质数的幂次的前缀和非负。
对于每个 $l$ 找到最大的 $r$ 满足条件，$l$ 从大到小扫，每次不影响的那些质因子不用管，影响的重新计算位置。
怎么重新计算位置？就是幂次修改的时候把中间的最近的一次出现位置改一下（拿个数组记录）即可，总共个数是 $O(n\log n)$，vector 维护一下即可。

1214F

如果是两条链那么就是顺序匹配。
环也是一样，如果第一个人匹配了 $i$，那么第二个会匹配 $i+1$，也就是在环上找个位置破开。
匹配的距离应该是 $\min(|x-y|,m-|x-y|)$，直接分类讨论，以 $x\geq y$ 为例：
$x-y\leq m/2$ ：贡献 $+x$，$-y$；
$x-y>m/2$：贡献 $-x$，$+y$，$+m$。
也就是每个数对下标差不同的贡献也不同。对于两边的每个数，给不同的下标差位置加上对应的贡献。
最后枚举下标差看对应权值的最小值即可。这个区间加直接用差分即可。

754E

先考虑暴力。直接枚举 $i,j$，再枚举 $x,y$ 来判断是否能匹配。
这样没什么前途，假设你少枚举 $x,y$ 的一维，则需要能快速判断两个串是否能匹配。
换个思路，枚举 $x,y$，再枚举 $i$，现在要快速求出哪些位置内匹配当前字符就直接 bitset 就知道了，那么对应的左上角就是往上若干行，列循环移位一下（这个也可以 bitset）。
总时间复杂度 $O(rcnm/w)$。

1031E

zzq 出过一个数据随机版本的，不过在 NOI 现场神秘老哥和我说有不随机的题在 CF 上，就是这道。
由于需要 $n/3$ 次，容易想到能不能考虑 $1$ 步归位 $3$ 个数，其实可以，你直接认为后面还有很多位置，把 $1$ 的位置都选上（如果只有 $1$ 个 $1$ 直接选第 $4$ 个数）。
上面的方法无法归位剩下长度 $\leq 6$ 的。长度很小的直接记录二进制状态 bfs，发现 $n=8$ 所有情况都有解，所以如果 $n\geq 8$ 的用上述过程剩余长度 $\leq 6$ 可以强制要求多保留两个 $0$。

37E

容易想到把过程反过来也是等价的。
最终同色的连通块过程中不会颜色不同，因为没有必要（把某一部分翻了再翻回来不如直接翻整个）。
然后就变成经典问题：每次选一个块反色求变成全白最少步数。从每个点开始，到最远的黑色块的距离的最小值。
直接建图，再从每个点开始跑 $0/1$ 最短路即可。

1514E

这个题我竟然以前没写过题解。。。
首先竞赛图有哈密顿路径，先求出一条，具体方法是归并排序，对于两条 $a_1\leftarrow a_2\leftarrow \cdots\leftarrow a_x,b_1\leftarrow b_2\leftarrow \cdots\leftarrow b_y$，先看合并出来之后的开头，$a_1,b_1$ 连边方向，不妨设 $a_1$ 为开头，那么 $b_1,a_2$ 都连向 $a_1$，再看它们两个连边方向，以此类推。可以直接 stable_sort，cmp 要求后面的连向前面的。
然后就在哈密顿链上看每个点往后连到哪就知道强连通分量了，每个点看它所在的强连通分量最右边的点是什么，如果和它之后还有边说明后面还有在同一个连通分量的，对于在连通分量的点依次判断扩展即可。

616F

服了，又搞混了 AC 自动机和广义 SAM 各自解决的问题了。AC 自动机是把模式串（匹配串）加入，广义 SAM 是把文本串（被匹配串）加入。
这题给你一大堆的是文本串，所以理所当然的用广义 SAM。广义 SAM 的节点表示了 $n$ 个串的所有子串，所以 $S$ 一定在它们之中（否则权值为 $0$）。
考虑固定了 $S$ 代价如何计算，也就是要知道出现次数对应的权值和与 $|S|$。这个和求 endpos 类似，直接在增量构造的每个节点（trie 树节点加入后得到的节点）上放上贡献，那么每个点贡献就是 fail 树子树的贡献和，对于当前点而言一定选长度最大的最优（如果贡献和是负的那么一定不如 $0$），也就是长度为 $len$，计算一下即可。

1000G

$(u,v)$ 的简单路径一定经过。
对于剩下的，就是路径上其它子树的可以进去再出来，这个是可以直接 dp 的。设 $dp[u]$ 表示从 $u$ 父亲开始走到 $u$ 子树最后走回到 $u$ 父亲的最大权值（不算父亲点的权值），那么就把儿子 dp 值 $\geq 0$ 的拿出来加起来。
比较特殊的是 LCA 处的外向子树，这个其实还是一样可以用 dp 解决（类似经典两遍 dp）。
怎么求 $(u,v)$ 的答案？路径上点的 dp 值都可以加，不过要去掉链方向的子树（或者换一种方法算，本身就会把所有子树加上，漏加了就说明权值是负的，只需要 LCA 的值与链上其它负的值），还得减去算了两次的链上的边（只需要算一次），还有 LCA 到父亲的边，再加上 LCA 向外子树方向的。

67C

这题啊，绷不住了。。。
先考虑没有交换操作，那么就是普通的编辑距离。
有这个交换操作，那么你一定不会插入一个数之后再换到其它位置，那不如直接加到换好的位置。且显然你不会把交换后的东西删除，不如你直接删了再交换。
且由于 $2t_e\geq t_i+t_d$，所以不会把一个数交换两次。所以你交换的话一定是把交换中间的所有数删掉再交换，之后这两个数就不会再交换了。
那还是一样的 dp，设 $dp[i][j]$ 表示 $a[1..i]$ 和 $b[1..j]$ 相同需要的次数。前三种和原先一样，交换的话你一定会把之前 $b_j$ 最近一次出现的拿出来，把中间都删了，再交换，把中间的补回去（如果不是最近一次，那么和它与它到之前那次的都删掉也是一样），对于另一边 $a_i$ 也是一样。所以就分别找到两边的位置，算出删除加入需要的代价，再加上交换的代价即可。

685C

先二分答案。
这种类似的题容易想到转成切比雪夫 $(x+y+z,x+y-z,x-y+z,x-y-z)$，但是还是不好求（四个值三个式子）。
设 $a=x+y-z,b=x-y+z,c=-(x-y-z)$，那么 $x+y+z=a+b+c$，你就可以求出 $a,b,c,a+b+c$ 的上下界。而 $x=(a+b)/2,y=(a+c)/2,z=(b+c)/2$，由于要求是整点，故 $a\equiv b\equiv c\pmod 2$。
枚举它们 $\bmod\ 2$ 的值，每个都减去后 $/2$。是否有解就判断 $a,b,c$ 的最小值之和，$a,b,c$ 的最大值之和形成的区间和 $a+b+c$ 最小最大值的区间是否有交即可。

1108E2

先把操作用到的区间拿出来离散化，以后操作的都是完整的若干个小区间。现在只有 $2m$ 个小区间，每个小区间只需要保留最小最大值。
枚举最大值所在的小区间，那么就想让其它的尽量小，那么你会选所有不包含这个区间的小区间（选了这个小区间的答案要么减小要么不变，还不如不选）。
$m$ 很小，可以直接 $m^3$，也可以先求出前缀后缀最小值，这样能 $m^2$，或者再套个树状数组变成 $O(m\log m)$。

187D

容易想到和 $\bmod\ (g+r)$ 有关。
如果你到某一时刻停在了某个路口，那么下一次你出发的时间是 $\bmod\ (g+r)=0$ 的时间。
你可以用权值线段树维护出如果在时刻 $d$ 从当前位置出发会到哪一个路口停下，在 $j$ 停下说明 $(pre_j-(pre_i-d)) \bmod (g+r)\geq g$，存一下之后的 $pre_j$ 即可。而每个位置也求个以 $d=0$ 开始需要求的答案。
询问的时候也这样查询一下，中间的用前缀和，第一个停下的位置之后的用之前预处理出的答案即可。

513E2

有个绝对值，但是符号还是有可能会抵消。
对于一个连续上升/下降的段，中间的数都是不需要考虑的，也就是选都不用选。
如果你符号错了那么一定是更劣。直接记录当前选了几个到状态即可。注意第一个和最后一个的贡献是 +1/-1 而不是 +2/-2。

1612F

无论如何你都会用两边最大的，因为选小的 +1 一定还是没有当前的大。
所以你每次一定会拿最大的，问题就变成每次拿哪一个。
枚举拿的次数 $c$，记 $f[i]$ 表示拿了 $c$ 次后左边最大是 $i$ 时右边最大的能是多少。
转移就看当前的力量值，看给左边变成这个值还是右边变成这个值。
你每次上下上下的操作（先小的加大的，再做另一边），那么每次会 $\times 2$，不妨设 $m\leq n$，则那边增长到了 $m$ 后另一边还需要增长到 $n$，所以需要大概 $O(\log m+\frac nm)$ 。
如果不满足 $m\leq n$ 就两种交换，$f$ 下标记录 $m$，就可以 $O(n+m+m\log m)$ 解决了。

269D

直接按照高度来做，要向中间的都连边，不太好做。
考虑换一种，由于你有交所以必定有先后，所以每个可以在 $x$ 较大的再连边。
且如果某个被之后加入的挡住了，当且仅当后面的那个上下分别是它向上和它。
把左右端点分开来，每次加入的时候修改一下连边，删除的时候直接从 set 删除。
最后 DAG 上 dp 即可，倒着过来做即可。

1313E

不是很好搞这个两个接起来，你直接枚举两个的开头位置还得枚举第一个长度。
枚举长度是因为不知道第二个从哪个位置开头匹配，容易发现一定要匹配到结尾，所以可以倒着过来匹配。
现在是要枚举 $l1,r2$，那么这个交集非空就好处理了，因为串长固定，只需要 $r2-l1\leq n$ 就行。另一个条件就是满足 $LCP(a[l1:],s)+LCS(b[:r2],s)\geq n$。
exkmp 预处理两个，查询就是定长区间中大于某个值的个数，滑动窗口+树状数组即可。

750F

假设初始在一个叶子节点，那么每个点知道一个深度为 $3$ 的点需要 $1+2+3+4=10$ 步。
问一下它自己，以及和它距离为 $1$ 的没问过的两个，就知道距离为 $2$ 可能的四个，问其中的三个就能确定，需要 $1+2+3=6$ 步。
如果初始不是叶子，可以先往三个方向都走，直到两个方向一起撞到即可确定深度，之后操作询问过的就不需要再询问，优先使用询问过的值。对于初始深度分析一下发现还是可以通过的（初始深度小差不多就问完了，深度大问的步数也少）。

763D

判断同构一般都是用的树哈希。
本身子树总共只有 $2(n-1)$ 种（每条边的两端）。
用一些牛逼哈希方式，比如子树和*当前子树大小+当前子树大小平方。然后换根一下只会改变两个的 dp 值。每个点再暴力看看所有子树（反正不超过 $2(n-1)$）有多少不同，用 set 之类的都可以。

778D

A 变成 B 的问题，一般有几种做法：
异或类型的把其中一个变成全为 0；
可逆的变成一个中间状态；
直接 A 变成 B。
这种是可逆的，考虑变成中间状态，比如全是横着（不妨设 $m$ 为偶数，不然可以行列互换）。
从左上角依次考虑，如果是横着的就跳过；如果是两个竖着的就变成两个横着的；如果是左边竖着右上边横着，如果右下边也是横着就可以右边的先转一下再转左边的；否则现在就要给右下的变成横的，可以递归，递归不动了一定满足条件，再倒推回来。
这样需要的步数是 $O(n^3)$ 的，应该有个 $\frac 12\times\frac 12\times 2$ 的常数。

961F

这样例提示了的一点：一个 border 掐头去尾又是一个更短串的 border。
从短的到长的，每次答案最多增加 $2$，可以直接判断是否是 border，如果不是就减小再判断，以此类推。由于每次最多增加 $2$，所以暴力复杂度是对的（刚开始还想需不需要什么牛逼优化）。
每次判断用哈希或者 SA 求任意两位置 LCP 长度即可。

542D

先看看怎么求这个 $J(x)$，可以发现先把 $x$ 唯一分解成 $x=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，那么每个 $p_i^{\alpha_i}$ 要么出现要么不出现，出现的数字相乘，所以 $J(x)=(p_1^{\alpha_1}+1)(p_2^{\alpha_2}+1)\cdots (p_k^{\alpha_k}+1)$。
容易想到把 $A$ 分解成若干个，每个看是不是 $p^\alpha+1$ 的形式，但是要求不能有两个的 $p$ 相同。
先求一下每个 $A$ 的因子的唯一表示法，具体来说就是先 $-1$ miller-rabin 判断是否是质数，再 $sqrt$ 一下看看是不是质数，否则就在预处理的表里看。
之后就直接按照 $p$ 的顺序给因子排序，再来个 dp，每次看乘不乘当前数，最多也就 $d(x)^2$（注意 $p$ 相同的集体从上一层转移，转移完再合并）。

1264D2

显然的一点是，你只需要把深度最深的路径上的那些括号拿出来，剩下的全部删掉，也就是最后剩下 $((\cdots(())\cdots))$。
你一定会选最左边的若干个左括号和最右边的若干个右括号，假设权值是 $x$，那么正数第 $x$ 个左括号的位置 $\lt$ 倒数第 $x$ 个右括号，它们中间形如 $))\cdots)(\cdots(($，枚举最中间的分界，那么左/右边正好有 $x$ 个左/右括号。
枚举这个分界，假设其左边有 $x$ 个已知左括号和 $L$ 个问号，其右边有 $y$ 个已知右括号和 $R$ 个问号，那么它对应的贡献为：
$$
\begin{aligned}
&\sum_{i\geq 0} (i+x){L\choose i}{R\choose i+x-y}\
=&L\sum_{i\geq 1} {L-1\choose i-1}{R\choose (i-1)+x-y+1}+x\sum_{i\geq 0} {L\choose i}{R\choose i+x-y}\
=&L\sum_{i\geq 0} {L-1\choose i}{R\choose R-i-x+y-1}+x\sum_{i\geq 0} {L\choose i}{R\choose R-i-x+y}\
=&L{L+R-1\choose R-x+y-1}+x{L+R\choose R-x+y}\
\end{aligned}
$$
每个分界的贡献求和即可。

167E

图，-1 的逆序对数次方，想到 LGV 引理就和行列式有关，但是具体是什么不太熟悉，一查发现这题应该是模板题。。。
还是来推一下。首先先不考虑不相交的情况，设 $f_{i,j}$ 表示从 $i$ 到 $j$ 的方案数，可以直接求行列式得到答案。
不过，如果有相交的路径，把最小的相交的两个点到达的换一下，那么系数就会变成负的，所以有相交的会互相抵消。所以上面的结果同样也是原题答案。
先把矩阵求出来（bfs 上 dp）再求行列式即可。

8D

先把 t1,t2 变成绝对长度。
如果两个都能先到 C 再到 B 那么就可以直接这么走。
否则就是到一个点 D，第一个直接到 B，第二个先直接到 C 然后再直接到 B，把 C 到 B 的距离从 t2 减去，就变成一个到 B 一个到 C 都得满足距离限制。
二分共同走的距离 $d$，画三个圆，以 A 为圆心半径为 $d$，以 B,C 为圆心半径为 $t1-d,t2-d$，看第一个圆上（不要求是边界，你可以绕远路）的点有没有同时在第二个圆和第三个圆上的。
现在就是三个圆是否有公共部分，先要求两两不相离，否则不行。如果存在一个包含另一个则可行，否则看两圆交点是否在另一个圆即可。

815D

第一维不满足条件的，第二三维必须满足。
第一维满足条件的，第二三维至少有一个满足。
$a$ 从大到小枚举，那么二三维的条件会越来越严格，用经典方法，用数组直接记录第二维取 $i$ 时第三维至少是多少，对于必须满足的要给第二维的前缀赋成 INF，剩下的取 max；至少有一个满足的要给前缀取 max。
这样的操作显然求出来的是个不增的数组。反过来记录每种还剩多少取值就变成不减的数组，前缀取 max 直接二分+区间赋值，所有位置求和就是当前 $a$ 的贡献。线段树维护即可。

1477D

首先，度数是 $n-1$ 的无论如何定向位置固定，不如放在开头，把这些点删去。
现在所有点度数都 $\lt n-1$，说明每个点在反图上都有一条出边。
反图是个菊花很有用，因为一种先中心后其它，一种先其它后中心一定一个位置都不同（点数>=2）。考虑给反图进行菊花剖分。
每次加入一个点：如果相邻点有没被划分的就划分到一起；如果相邻有一个中心（点数=2 时都是中心）可以接到那个中心；如果相邻点所在菊花点数>2 可以把那个点拿过来。
这样就使得任意两个位置都不同。

51F

经典捏点操作。一个环除非捏成一个点，否则还是有一个非自环。
因为毛毛虫是不能有非自环的，所以可以先缩点（边双），然后再考虑剩下的树。
叶子节点没必要合并，假设你知道了最后的链，如果链上连出去的儿子不是叶子，说明把叶子都删了，那不如把它父亲删了留下它们。
把非叶子节点求个直径保留下来，其它的非叶子都合并到直径上，现在就满足条件了。
对于若干条链最后需要一条一条并起来。

142D

如果某一行只有某种颜色的格子且没有被占满，那么这个人就不会输，因为它可以一直移动这一行的一个格子。
如果双方都不会输，就平局；如果只有一方不会输，那么这一方获胜（其它的就一直 attack 到对面的旁边，如果不能动就不动）。
否则每行为空，要么有两个不同的。为空的行不用管，那么对于每行，如果一个跑得更远，另一个可以复读。
题解是说等价于 nim-k，感觉大概类似，但是这个不需要必须 $k$ 个，复读的话次数也会变少，但是结论还是一样，具体证明？

761F

先求出每个矩阵和原矩阵与 26 种纯色矩阵每个位置的距离，再把这些矩阵加起来。
对于每个要变的，即把原矩阵的某个子矩阵替代成纯色子矩阵。减掉原来的再把当前颜色的加回来即可。

611G

这个面积差要绝对值，这个其实好处理，你知道固定一个端点后另一个端点两边差面积一定先小后大，中间有一个分隔的位置。这个容易双指针求。
根据经典方法，求面积可以随便选个中心点按照极角顺序求三角面积加起来。
实现的时候要把最后和开头形成的三角面积用叉积展开计算。

1310C

$n$ 很小，直接把所有子串拿出来排序，排序时的比较用两个位置开头的 lcp 长度（预处理）。
然后二分答案，怎么判断呢？也就是求每个字典序都 >= 当前串的分割方案，直接设 $dp[i][j]$ 表示前 $i$ 个字符分成 $j$ 段的方案数，转移就看 $i+1$ 开头的和答案的 lcp，长度不超过 lcp 的显然不行，看 lcp 的下一个位置是否合法，合法那么整个后缀都能加上这个的方案，否则就不能。
记录一个差分的懒标记就可以了。

1082F

每个结束点向上第一个标记点（或只有一个字符的点）距离 +1。
从下到上树形 dp，记录一下子树根往上第一个标记点的距离，子树选了几个标记点。
时间复杂度 $O(nk^2\sum len)$。

685E

你要经过的边的编号是单调递增的。
我有一个奇妙思路：考虑把边建图，但直接这样转复杂度太高。先把边拆成有向的，从同一个点出发的边按照权值依次小到大连，一条边对应的要连到它原先出点往外连的边第一条不小于（等于连了没关系，相当于没走）它的，每次就是询问 $s$ 往外连的第一条不小于 $l$ 的，和 $t$ 往外连最后一条不大于 $r$ 的（之前连等于就派上用场了，满足条件的都可以往回连）。然后就发现还是没法求，边数太多了。。。
这题是可以离线的，考虑先离线，只保留时间 $\geq l$ 的。每次加入一条当前编号最小的边 $(u,v)$，它们两个之间的需要最小的时间变成了当前边的编号，而由于当前是编号最小的，所以新增的路径只有以这条边开头的，用 $u$ 的更新 $v$，用 $v$ 的更新 $u$ 即可。时间复杂度 $O(nm)$。

434D

这个限制容易想到差分约束，但是还有一个奇怪的收益差分约束无法解决。
不过它这个 $l,r$ 都很小，可以考虑网络流。其实感觉这种只能取一个权值的比较像最小割，不过答案要求的是最大的总收益。
这个其实好办，因为你期望就是每个只选一个值，把所有的代价用某个较大的值$t$ 减去即可。
每个点挂一条链 $l_i,\cdots,r_i+1$，$x$ 向 $x+1$ 连这个点 $t-$取 $x$ 的收益。对于一个限制 $x_i\leq x_j+d$，从 $i$ 挂出的链向 $j$ 挂出的链代表的差值为 $d$ 的连边 INF。
本来我以为做完了，结果一看题解，说这样还是有问题，仔细一想确实没考虑限制边连出去比另一端 $r$ 还要大，这样说明你这个不能选，所以直接向 $t$ 连个 INF。

1392G

选一个区间看着就不好做，因为种类数是平方的，且看上去不太好优化。
不过根据都交换等于没交换，可以变成只有一维，先在 $s$ 上做 $[l,n]$（即 $[l,r]+[r+1,n]$），再为了把后面的操作抵消，再在 $t$ 上做 $[r+1,n]$。
这样 $s,t$ 操作都只有 $O(n)$ 种，问题转化为两个长为 $n$ 的数组，每个数字 $1$ 的个数相同。每次可以选 $1\leq im$ 求 $x_i\oplus y_j$ 中 $0$ 的位数最大值。还是不能暴力两边枚举一个看相同的个数。
相同的个数不容易看出，不过由于 $1$ 的个数固定，所以可以通过两边都是 $1$ 的位数 $w$ 与两边 $1$ 的个数 $u,v$ 解出两边都是 $0$ 的个数 $k-(u+v-w)$ 进一步求出答案为 $k+2w-u-v$。由于 $u,v,k$ 固定，所以就要 $w$ 最大。
$w$ 最大也就是 $\And$ 起来 $1$ 的位数最多。这就经典了，求出包含状态 $sta$ 的位置 $s$ 最小 $t$ 最大分别为多少，对于每个 $sta$ 判断是否可行，可行就将其中 $1$ 的个数更新到答案。

36E

有个不保证连通，如果连通块个数 >2 显然无解，如果恰好 2 个连通块就分别跑欧拉回路。
只有一个连通块，如果奇度数点的个数为奇数或者 >4 也无解。个数为 0 或 2 只需要一条路径/环就可以，拆开即可；个数为 4 先给某两个连一条边跑欧拉路，然后再断开分成两段。

333C

后四位随便填，设填完的是 $x$，那么前四位是 $k+x,k-x,-k-x,-k+x$ 都可行。
直接枚举后四位的方案，平均每个数有 60 种，那么就有近 600000 种合法的，就够了。

196D

回文串不存在长度 $\geq d$ 的回文子串，等价于不存在长度为 $d$ 或 $d+1$ 的回文子串。
由于字典序要 $>s$ 且最小，所以让 $s$ 和答案串的 lcp 尽量长。
如果发现某个位置和前若干个形成了长度为 $d$ 或 $d+1$ 的回文子串，那么最优的策略是把它替换了，且一定是替换成比原先大的且与之前不会形成长度为 $d$ 或 $d+1$ 的回文子串的。如果这个位置没有可选的替换方案就考虑前一个位置以此类推。
之后的问题就没有字典序大小的限制了。还是一样的用贪心，每个位置尽量填最小的，且不用考虑没有能填的问题（26 个字符，最多 ban 两个）。
是否是回文怎么判断？直接哈希，每次是在最后插入字符，容易维护前缀哈希值。

140F

假设对称点是 $(x,y)$，考虑如何快速判断。
对于点 $(x_i,y_i)$，它的对称点是 $(2x-x_i,2y-y_i)$。
把 $x_i$ 按照从小到大的顺序排序，那么 $2x-x_i$ 会从大到小。$y_i$ 同理。
所以把所有 $(x_i,y_i)$ 当作 pair 从小到大排序，如果不删点就是 $i$ 和 $n-i+1$ 对称。
因为只能删掉 $k$ 个，所以开头 $k+1$ 个至少有一个没被删除，最后 $k+1$ 个也至少有一个没被删除，枚举两个对称的，判断一下。时间复杂度 $O(nk^2)$。

1288F

这种有一大堆大小限制而且不好用差分约束的，考虑一下网络流。
由于要求的是一种大于另一种，也就是两种差的个数>0。在流量平衡上动点手脚，不妨设 r 是正的 b 是负的（对流量的贡献），那么 R 的净流量 > 0，B 的净流量 < 0，连到 t/从 s 连至少为 $1$ 即可。
发现这样还是不太行，如果两边颜色相同理论上两边变化的符号也相同，所以换一下右边的判断条件（右边 R 的净流量 < 0，B 的净流量 > 0），现在就可以认为红边给左边的+1，右边的-1；蓝边给左边的-1，右边的+1。
对于每条边双向连一下，下界为 0 上界为 1（如果两个都流/都不流说明不涂），有色点就按照刚才说的连，无色点可以从 s 连过来或连到 t，说明它没有限制。
跑最小费用可行流即可。

261E

先把 $query(l,r)$ 变成 $query(1,r)-query(1,l-1)$。
它这个 $p$ 很小，这就说明很多数字无法表示。由唯一分解，$x$ 中最大的质因子 $p_k$ 只能由它或它的倍数表出，所以 $p\geq p_k$。
只需要保留最大质因子不超过 $p$ 的。这个限制其实很强，你出现质因子 $>p$ 的就直接不行了，所以可以直接暴力搜，只有不到 $3\times 10^6$。
设 $dp[i][j]$ 表示 $b=i,a=j$ 需要的最小操作次数，转移要么给 $i+1$，要么给 $a\times i$，注意不要越界。

1415F

每个位置要么是人在那里要么是分身在那里。
题目保证了时间或坐标互不相同，就不会出现一个分身某一次用到了之后还能用的情况。也就是每一时刻的分身要么没有，要么是准备给之后某一时刻用的，且你放下了一定会让它用，否则你不如不放。
状态可以表示成两种：当前在 $x_i$，时间为 $t_i$，分身在 $j>i$ 是否可行 $dp_{i,j}$；当前在 $x_i$（放下了一个分身），之前都经过了，最小时间为 $g_i$。
$g_i$ 的转移：
前往 $i+1$，在时间 $t_i$ 后放下分身 $\longrightarrow g_{i+1}$;
前往 $j(j>i+1)$，在时间 $t_i$ 后放下分身，再折返回 $i+1$ $\longrightarrow dp_{i+1,j}$。
$dp_{i,j}$ 的转移：
$j>i+1$，前往 $i+1$ $\longrightarrow dp_{i+1,j}$;
$j=i+1$：
a. 前往 $i+2$，在时间 $t_{i+1}$ 后放下分身 $\longrightarrow g_{i+2}$;
b. 前往 $j(j>i+2)$，在时间 $t_{i+1}$ 后放下分身，再折返回 $i+2$ $\longrightarrow dp_{i+2,j}$。

238E

先求出每辆巴士最短路的必经点，只有在这些点上才一定能上，否则车可能特意不从你这走。
上了某辆巴士后，巴士一定会往使得答案最大的方向开，而人一定会在其中答案最小的地方下车。
用（当前所在的点，巴士编号）作为状态，每次走后继答案最大的，类似最短路的方法求答案即可。

736D

排列和奇偶性有关的，考虑一下行列式/积和式。
如果有限制 $a_i,b_i$，可以把矩阵 $(a_i,b_i)$ 赋成 $1$。
怎么求数量的奇偶性？就是积和式的值，而积和式的 mod 2 = 行列式 mod 2，所以可以直接求行列式。
现在把每个位置赋成 $0$ 问行列式的奇偶性。由于只改变了一个位置，考虑对行拉普拉斯展开，即一个 $A_{i,j}$ 的系数变成 $0$。换句话说，答案的增量是 $-C_{i,j}$（$C_{i,j}$ 是 $(i,j)$ 代数余子式）。
每个位置代数余子式的值就是余子矩阵，而余子矩阵是伴随矩阵的转置。如果原矩阵可逆，那么伴随矩阵 $adj(A)=det(A)A^{-1}$。由于保证初始是奇数，所以一定可逆，在 mod 2 意义下 $det(A)=1$，所以只需要求 $A$ 的逆。且由于是 mod 2 意义下可以用 bitset 优化，时间复杂度 $O(n^3/w)$。

1622F

先特判 $n\leq 2$。
考虑能不能先拆一些平方项出来。假设 $n$ 是偶数，那么可以把 $1!2!$ 分一组，$3!4!$ 放一组，...，$(n-1)!n!$ 放一组，剩下的非平方项就是 $2\times 4\times 6\times \cdots\times n$，即 $2^{\tfrac n2}(\frac n2)!$，根据伯特兰-切比雪夫定理，$(\frac n2)!$ 在 $n>2,2\mid n$ 时不会是平方数。
如果 $4\mid n$，那么由于 $2^{\tfrac n2}$ 是平方数，$(\frac n2)!$ 是非平方数，所以至少要删掉一个数，且删掉 $\frac n2$ 就满足条件。
如果 $2\mid n$ 且 $4\nmid n$，先删掉一个 $2$，就变成和 $4\mid n$ 一样，删去 $\frac n2$ 就满足条件。
否则如果 $2\nmid n$，先删去 $n$ 变成 $n-1$ 的子问题再做。所以最多只需要三步。
去掉一个数，$O(n)$ 判断。去掉两个，先枚举一个和 $x$ 异或，加入 map，再询问。去掉三个就用上面的构造。

1493F

行和列是独立的，行的方案数乘上列的方案数就是答案。
由于是平铺，所以可以直接求出最短循环节吗，它的倍数都是可行的。
怎么快速检测分成 $x$（$x$ 是质数）段是否可行？如果 $x=2$ 就直接判断，否则 $x$ 是奇数。由于不能重叠，可以分别拆成询问 $[l,r-1],[l+1,r]$ 与 $[1,r-l]$（$r<2l$），通过这个方法可以查询出 $[\frac{x+1}2,x]$ 是否全部相等，也可以知道 $[1,\frac{x-1}2]$ 与 $[\frac{x+1}2,x-1]$ 相等，推出所有元素全部相等。

1543E

容易想到从一个点开始，给自己标号为 $0$，给相邻点标号 $2^i$，剩下的点标号就唯一了。这个显然是对的，你可以通过给每个数异或上一个值，交换两位做到一种满足这个条件的。
第二问，每种颜色是对称的，而由于每个点都有一个相邻的颜色为 $c$ 的，而每个颜色为 $c$ 的点贡献是 $n$，所以颜色为 $c$ 的点数是 $\frac{2^n}n$，所以 $n$ 也只能表示成 $2^k$ 的形式。
先考虑 $0$ 号点，给它颜色 $0$。相邻的点，不妨给 $2^i$ 的点颜色 $i$。那对于 $2^i$ 的点，它相邻的点和它的异或也是 $2^0,2^1,\cdots,2^{n-1}$，给它们分配当前的异或 $0,1,\cdots,n-1$ 即可。这样就没有任何矛盾，换句话说，$x$ 给二进制表示中 $1$ 的位置下标的异或即可。

652F

经典题。
蚂蚁掉头和两只蚂蚁互相穿过是没区别的，而原问题蚂蚁的相对顺序不会改变。
记录一下初始 1 号蚂蚁之前的蚂蚁数，如果有其它蚂蚁顺时针过来那么当前蚂蚁的蚂蚁之前多了一只，如果有之前的蚂蚁逆时针过去那么就少了一只。注意当前蚂蚁穿过了 1 的情况（负的也没关系，认为在 mod n 意义下）。

1423L

这个 $S$ 这么小，考虑一下 meet in the middle。
如果只有一组询问，容易想到一边带着初始状态跑，一边直接跑。但是现在有多组询问，意味着你不能带着初始状态，询问的时候得枚举一边。
但是这个 $D$ 也不大，所以可以一边跑 $2^{2S/3}$ 一边跑 $2^{S/3}$，把多的一边插入到表里，少的一边每次枚举一边，看表里有没有对应的即可。

1036G

如果不满足类似 Hall 定理的东西，也就是存在一个源点集合 $S$ 且 $S$ 不是全集时，对应能到达的汇点集合 $T$ 如果满足 $|T|\leq |S|$ 答案一定是 NO（其它汇点到不了当前 $S$ 中的点了）。
直接枚举所有状态即可。

1229D

康托展开。设 $a_i$ 表示值为 $i$ 的数前有多少个比它大的，那么康托展开的值是 $\sum_{i=1}^n a_i\times (n-i)!$。
预处理任意排列的乘积。然后枚举左端点，不同的右端点（会新增的）最多只有 $k!$ 个（总共只有 $k!$ 种）。一种想法是每次加入一个当前无法表出的置换然后暴力扩展，但这样复杂度太高。
根据群论的拉格朗日定理，子群的阶一定是有限群阶的约数，所以每次扩展后大小至少扩大一倍。扩展得到的置换可以看作是每次加入的置换之间做任意乘法得到的，所以基底大小只有 $O(k\log k)$，总时间复杂度为 $O(nk!k\log k)$。

226E

先树剖，每次看现在时刻的主席树减去那个时刻的主席树就是不能走的，在主席树上二分。
修改的时候新开个版本即可。

1388E

最小值一定出现有两个线段相交于一点，否则你看往哪边两端的长度会更小，在那个方向加个 $\epsilon$ 即可。
所以现在只需要考虑有两个线段相交的情况，对应的角度也只有 $O(n^2)$ 种。直接暴力判断是 $O(n^3)$ 的。
先考虑求出哪些是合法的，把角度排序，如果某个角度是在使得某两个相交的角度区间内就不行。
现在知道了一些合法的角度，按照顺序，答案是凸的，三分即可。

1221G

首先 $n=40$，可能是 meet in the middle。
其次这三个条件不好计数（一是至少不好算，二是有三个条件），考虑容斥成全部-没有 0-没有 1-没有 2+没有 01+没有 02+没有 12-没有 012。
特判 $m=0$，剩下的情况一定不会出现没有 012，现在最多只有两个限制。
一个一个算：
全部：方案数 $2^n$；
没有 1：不存在相邻两个为 0,1，对于一个连通块，如果有 0/1 相邻的都得是 0/1，所以每个连通块颜色相同，方案数为 $2^{tot}$（$tot$ 为连通块数）；
没有 01：和没有 1 的分析类似，至少有 $2$ 个点时连通块里只能都是 1，方案数为 $2^{tot2}$（$tot2$ 为只有一个点的连通块数）；
没有 12：和没有 01 对称，方案数也为 $2^{tot2}$；
没有 02：相邻两个数字不同，如果有连通块不能黑白染色则没有方案，否则方案数为 $2^{tot}$；
没有 0：考虑 meet in the middle，分别算出两部分各自合法的填法，枚举一边，对于横跨两部分的边的限制，假设左边的是 $0$，右边的对应位置必须是 $1$。处理出每个左部分的点如果是 $0$ 会对右边哪些点有必须是 $1$ 的限制，方案数就是高维后缀和。FWT 预处理一下高维后缀和即可，设 $k=\frac n2$，时间复杂度为 $O(2^kk)$。
没有 2：和没有 0 对称，方案数也相同。

1081F

zzq 出的交互。。。
考虑依次询问出每一个位置 $i$ 的值，直观的想法是我直接询问两次 $[i,i]$，如果是除了 $i$ 都反转了那么就得到了 $i$ 的值，如果是没变那就什么都没得到。
怎么判断是否反转了？如果反转的数字个数是奇数那么一定会改变 $1$ 的个数，否则不一定。如果 $n$ 是偶数，就可以一直问 $[i,i]$ 直到和变了再判断（注意操作是永久的，其实问到的是 $a_1,-a_2,a_3,-a_4,\cdots$）。
如果 $n$ 是奇数，也可以类似问 $[i,i+1]$（问到的是 $a_1+a_2,a_2-a_3,-a_3+a_4,a_4-a_5,\cdots$）。现在你可以知道 $a_1+a_i$ 的值。因为 $n$ 是奇数，所以 $a_1$ 只有一种取值是合法的（符合总和限制的，你可以知道 $na_1+\sum_{i=2}^na_i$）。

249D

这个题也太哈人了。
先考虑可行度数区间是 $[0,\frac \pi 2]$ 的情况，即每次都得选右上方的，也就是求一个最长不下降子序列。
现在的也是一个坐标系，只不过两个轴变了。还是类似于向量分解变成两个轴的系数，又变成了求最长不下降子序列，排序之后做即可。

377E

机器新买的一定是 $v$ 比以前都大的并且立刻拿来用，且如果你确定了要买某机器那么到了金额就一定会立刻买。
把机器按照 $c_i$ 从小到大排序，每个机器如果要买，就在之前的机器产生金额达到 $c_i$ 的时候立刻买。且显然如果有一台机器 $c_i$ 不比它大且 $v_i$ 比它大那么现在这台机器就没用了。
维护之前的机器到金额 $c_i$ 的时候的最少时间，那么首要的就是时间最少，次要的是剩下来的金额尽量多。
维护之前的机器形成的凸包（可以认为是斜率优化），由于 $c_i$ 单调递增，所以可以双指针在开头弹出，且每次加入的斜率比之前都大所以可以直接在结尾加入。

802C

如果一本书留下来，就省下了下一次再把它放进来的时间，代价就是在中间的时间段占了一个位置。反之如果不留下来，在这一次请求完就可以扔掉，中间的时间段省下了一个位置。
换句话说，可以多花 $c_{a_i}$ 的代价使得 $[i+1,j-1]$ 的时刻少占 $1$ 的空间。
直接建图，每个点向下一个点连 $(k,0)$，表示这个时刻结束容量至多为 $k$；每个点向下一个相同请求的位置连 $(1,c_{a_i})$，表示可以花 $c_{a_i}$ 的代价省下中间的容量；S 向每种请求的第一次出现连 $(1,c_{a_i})$，表示第一次需要花这么多的代价；每种请求的最后依次向 T 连 $(1,0)$，表示可以直接扔掉。
不过这样有个问题，这样建图你买的当天如果直接卖了它在这个时刻结束时并没有占空间（顺序是买-卖-判）。不妨重新划分下时刻，认为每天先卖后买，如果要买就在前一天下班的时候（顺序是卖-买-判），向每种请求连的边往前连一个位置即可。

1131G

设 $f_i$ 表示前 $i$ 块骨牌全部推倒的最小代价。
一种是 $i$ 直接往左推，从 $f_{l_i-1}+c_i$ 转移过来。
另一种是从某个 $j(j\leq i\leq r_j)$ 推倒 $[j,i]$ 区间内的，从 $f_{j-1}+c_j$ 转移过来。
发现第二个转移不好做，需要数据结构维护，做不到线性。但是如果有 $r_j\geq i(j<i)$，那么一定有 $r_j\geq r_i$，也就是区间要么不交要么一个包含另一个。
那么之前所有 $r_j\geq i$ 的，一定前面的包含后面的。每次如果包含的条件不满足就弹栈，栈里维护权值不增的，从栈顶更新即可。

30D

这好像是 Qingyu 爆切的某题的弱化版。
先考虑起点在 $n+1$ 的情况，一定先走到下面的某个端点，再一路走过去（如果走到中间再走到某一边，根据三角形两边之和大于第三边一定不优）。
否则如果起点在数轴上，再分情况，走到 $p$ 之后是否还下来：
不下来了，走到左右某端点再走到另一端点再到 $n+1$；
先从 $k$ 开始走完了 $[l,r]$ 内的，然后到 $p$，再下来走。根据两边之和大于第三边，也是只会先往左再往右/往右再往左，然后走上去。且继续根据两边之和大于第三边，如果 $l\neq 1$ 且 $r\neq n$，下来后还得整个走过来一次，这就不如上去之前就把一边走完。

1379F1

$2n\times 2m$，先把它分成若干 $2\times 2$ 的小块，每一块选择一个。
每个小块是左上一个白格子，右下一个白格子。删掉一些白格子就使得某些小矩阵的方案固定。
一个矩形放了右下就会使得下方、右方和右下方的三个也只能放右下。所以无解就是一个 R 的右下方的矩阵中有 L。
维护每行最右边的 L 和最左边的 R，新加入的时候就线段树维护之前行的 R 最小/ 之后行的 L 的最大值，和当前区间是否已经有不合法的。

183D

这种期望题就用线性性拆。拆成对于每种情况，每种喜欢的人数和数量的最小值之和。
然后就可以用线性性拆成每种分别考虑，第 $x$ 种 dp 出前 $i$ 个人需要 $j$ 件这种衣服的概率。
直接求出所有 dp 值的复杂度是 $O(n^2m)$，不过可以发现你要求的并不是 dp 值，假设有 $u$ 件这种衣服，那么你要求的期望是 $\geq 1$ 个人要的概率+$\geq 2$ 个人要的概率+...+$\geq u$ 个人要的概率，容易看出是凸的。
由于总数量的和为 $n$ 且是凸的，每次可以给新增的值最大的加 $1$。每次维护一下新增之后会增加多少值，且新增后可以花 $O(n)$ 的时间处理出下一次操作会新增的值。

1142D

对于一个排名为 $k$ 的，在它后面增加一个 $c$ 扩展出的 $k'$ 排名是：$9+\sum_{i=1}^{k-1}(i\bmod 11)+c+1$（不能被扩展出的 $1,2,\cdots,9$，比 $k$ 小的所有扩展出的，$k$ 扩展出的比它小的）。
你只需要关心排名 $\bmod 11$ 的余数，记录 $dp[i][j]$ 表示当前在 $i$，排名 $\bmod 11$ 为 $j$ 的方案数。转移也简单，余数够大的下一个数就能加，否则不能。

1510I

这题是 WC2022 的讲课题。
跟大神和来投票，分别会在大家水平都不好与只有少数水平很高上出问题。
不妨把两个并起来，让所有人投票，正确率高的人权值高，然后按照这个概率来随机选择。

1217F

这个强制在线没什么用，还是可以线段树分治。
每次加入的时候就并查集，询问就异或 lastans 然后询问，用只按秩合并的并查集支持回退。

838D

神仙题。相当于是每个人选择一个位置，然后向左或向右走，问合法的方案数。
不合法也就是走到了 $0$ 或 $n+1$，不妨把它变成一个环，加入一个点 $n+1$，要求不能有人停在 $n+1$ 的方案数。
认为初始也可以放在 $n+1$，不过放了显然是不合法的。这样的话所有点就是对称的，每个点有人坐的概率也是一样的，$n+1$ 有人的概率是 $\frac{m}{n+1}$，也就是 $\frac{n+1-m}{n+1}$ 的概率没人，乘上方案数 $(2(n+1))^m$ 即可。

842E

有一个结论，直径如果长度为奇数那么所有直径交于一条边（直径最中间），长度为偶数那么所有直径交于一个点（直径最中间）。
现在就是求到这个中心距离最大的点数（把边上拆出一个点）。
先把这棵树建出来，每次“加入”点的时候，看父亲是否是距离最大的点之一，如果是就考虑把直径中心往当前方向移，对距离的变更就是某个子树内减 $1$，剩下的 $+1$。每次加入的时候 active 这个点，没 active 的点是无效的。

886F

在某条直线上，前一半的点要和后一半的点对称，那么它的坐标应该是所有坐标的平均值。
由于向量 $a$ 在单位向量 $b$ 上的投影是 $(\vec a\cdot \vec b)\vec b$，因此你可以先求出原来所有坐标的平均值（称为重心），那么无论如何中心点都是重心的投影。如果有两个关于重心对称那么显然投影后还是对称（如果所有点两两对称那么就用无数种方案），删去这些点，以重心为原点。
考虑和剩下的第一个点配对的，它们的投影要求关于原点对称，通过上述式子确定直线（联立容易解出斜率），再判断剩下的点即可。

850D

根据兰道定理，把比分序列从小到大排序之后要求前 $k$ 个之和 $\geq \frac {k(k-1)}2$。
用这个定理，先把 $a$ 排序，dp 一下记录集合大小，构造出的点数，总共边数，dp 一下求出原度数。
构造就比较容易，由于竞赛图删去一个点和与它相邻的所有边还是一个竞赛图，按照兰道定理贪心的删去一个出度最小的即可。

277D

这个罚时定义的比较奇怪。题目的意思类似于一个多重背包。
顺序怎么放？一定是先把暴力放前面，因为暴力放后面就意味这着之前的时间都有了贡献，暴力之间的顺序无关紧要。
记录一下当前的最大期望得分和最小期望罚时（注意暴力的时间都是加，而正解的时间是用当前时间替换）。
如果是暴力，就一定放前面，可以直接加上得分与时间。
如果是正解，其中暴力的部分也直接加，剩下的正解的时间一种是打炸了，就用暴力的时间；另一种就是用当前的时间。
现在问题是正解的顺序怎么放。还是用调整法来比（两个都写挂的情况不用考虑），可以得到应该是按照 $\frac {(1-p)t}p$ 从大到小排序。就按照这个排序就好了。

1599G

这题就是 Qingyu 爆切的。和 30D 类似，不过先得求出这条直线。这个简单，前三个点必定有两个在直线上，枚举一下看，然后旋转到 $x$ 轴，把剩下的点标号 $n+1$。不过当时好像做复杂了，讨论了一些奇怪情况。
先考虑起点在 $n+1$ 的情况，一定先走到下面的某个端点，再一路走过去（如果走到中间再走到某一边，根据三角形两边之和大于第三边一定不优）。
否则如果起点在数轴上，再分情况，走到 $p$ 之后是否还下来：
不下来了，走到左右某端点再走到另一端点再到 $n+1$；
先从 $k$ 开始走完了 $[l,r]$ 内的，然后到 $p$，再下来走。根据两边之和大于第三边，也是只会先往左再往右/往右再往左，然后走上去。且继续根据两边之和大于第三边，如果 $l\neq 1$ 且 $r\neq n$，下来后还得整个走过来一次，这就不如上去之前就把一边走完。

325C

先做 $\min$ 的这一边。
假设怪物 $i$ 能拆成 $x$ 个钻石和集合 $S$ 的怪物，那么 $f_i=\min_{(x,S)\in Split(i)} f[S]+x$。
可以倒着既像拓扑排序又像 dijkstra 的方法，对于每个求出值的 $i$，如果它是某个拆分里最后一个求出的值，就更新那个拆分的点。
正确性也显然，如果某个之后求出来的比之前求出来的小，之前没取到它的原因是它当时的值过大，之后变小说明是中间某一步拆分的值给它用了，而中间拆分的值给它用了它一定比中间拆分的值要大，就矛盾了。
这样顺便能跑出无论如何都拆不完的，输出 -1。
再做 $\max$ 的这一边。
因为每种拆分至少得到一个钻石，所以如果有环，那么能到达环的全部都是 -2（这里的图是每个点直接连能拆出来的点），剩下的就是一个 DAG，按照拓扑序依次做即可。

1620F

二分图就要求没有奇环。容易想到可能只用判断长度为 3 的奇环。
大于有传递性，设奇环上的点为 $p_1,p_2,\cdots,p_k(2\nmid k)$，如果有相邻两个的大小关系相同（$p_ip_{i+1}>p_{i+2}$）则就形成了一个长度为 $3$ 的奇环。但长度为奇数，它们间的大小关系的数量也为奇数，故一定有相邻两个相同。也就是只需要判断 $a$ 是否有长度为 3 的下降子序列。
记录一下当前位置，之前长度为 1 的最后一个数的最大值，此时长度为 2 的最后一个数最大值最小是多少。但是这样还是 $O(n^2)$ 的。
新增的只能 $\geq y$。如果比 $x$ 小，dp 值要更新成新增的值；否则要更新 $y$。所以只需要记录一下是哪个等于当前的值，当前的是正是负，存的是另一个值即可。

1572D

显然是二分图，因为可以按照 1 的个数分类。但是直接匹配显然复杂度太高。
每个点会连出去 $n$ 条边，选择了一条匹配总共会减少 $2(n-1)$ 条，包括这一条总共就 $2n-1$ 条。所以如果只保留最大的 $k(2n-1)$ 条边就可以了（否则你考虑反证法，最优方案里选最大的若干条边，剩下的也替换成最大的若干条不会更劣）。
接下来就把边权设成两端点之和跑二分图带权匹配即可。

1500D

对于每个右下角，记录一下往左/上/左上方向前 $q+1$ 近的元素与切比雪夫距离。
这些信息容易合并，合并完了之后就知道以这个为右下角的边长可以是多少，给答案数组前缀加 1，差分即可。

1487F

首先容易发现一个数不会加 10 次，不然不如用后面加一位 1 的再减去 1 用的 1 的个数更少。
如果之前的 $m_0,m_1,\cdots,m_{i-1}$ 都加了 9 次，它们的和也只有 $m_i-i$，也就是说 $i>0$，只用不超过 $i-1$ 的数是不能表示出 $\geq m_i$ 的数的。
设 $dp_{i,x}$ 表示加减完所有 $m_j(j>i)$ 并且当前值为 $x$ 的最小代价，由于之后的数字能表示出的值的绝对值不超过 $m_{i+1}$，所以 $x$ 也不能 $\geq m_{i+1}$。
固定 $i$，对于 $x \bmod m_i$，合法的数字一定在一个长度为 $O(|n|)$ 的区间（认为是一个环，也就是 $[l,n]\cup [0,r]$ 也是区间）。证明如下：刚开始显然满足条件，而你这一次操作要变成绝对值 $<m_i$ 的，且操作的都是 $m_i$，所以对 $\bmod m_i$ 的值不影响。这一层操作完之后就变成两个区间 $[a-m_i,b-m_i],[a,b]$，而 $m_i\bmod m_{i-1}=1$，所以相当于 $[a-1,b-1]$ 和 $[a,b]$，长度最多增加 $1$。
所以可以直接记录合法的状态 $x$。注意需要高精度。

598F

根据经典结论，奇数次经过多边形边界时进入，偶数次是穿出。
如果这条直线是完全竖着的可以翻转横纵坐标。
还要考虑加上直线与多边形的边重合的情况，把重合部分记录答案之后，如果前一条边和后一条边相对直线的位置相同则认为没有相交（没有出去），否则认为相交了（出去了）。

1386C

问题可以变成删去中间的一些边问原图是否是二分图。
删除不好做，考虑改成选择其中的一些。把序列倍长，就变成选择一个区间问是否合法。
考虑对每个左端点求出最大的右端点满足是二分图，而二分图的条件可以弱化为若干棵树的条件。容易想到并查集，但是并查集无法删除。使用 LCT 维护，后加入的边优先级更大（形成偶环也可替换环上最早的边），双指针，每次到再加下一个就会形成奇环的时候停止。
能不能不用 LCT？由于 $l$ 增大 $r$ 也增大，可以使用类似决策单调性的方法，分治。
$solve(l,r,x,y)$ 表示左端点在 $[l,r]$，已经知道右端点在 $[x,y]$，现在要求出 $[l,r]$ 的所有右端点。也是类似决策单调性求出 $mid$ 对应的右端点 $m$，那么可以递归到 $solve(l,mid-1,x,m),solve(mid+1,r,m,y)$。
发现现在这样反而不好移动指针，还是用原问题的删除，到儿子之前用儿子的最大可能区间更新并查集，回来的时候再回滚即可（现在这样结果应该是递减的，递归的时候要注意）。并查集只需要维护连通性和每个点到根的距离，这足以求出两个点的距离是奇是偶。

717F

根据经典结论（或简单手推），只需要考虑从左到右，且每个为左端点的操作次数为 $a_i-a_{i-1}+a_{i-2}-\cdots+(-1)^ia_1$。
把奇偶位置的线段树分开来维护。把一次区间加操作，拆成两个后缀操作。$\geq l$ 的位置，和 $l$ 奇偶性相同的会加上 $k$，奇偶性不同的不变。
线段树维护区间最小值，在把前面位置的加上，判断一下即可。

1140G

相当于是你在每个点可以花一个代价切换，然后要在树上从 $u$ 走到 $v$。
切换实际上不一定是直接切换最优，可能走到某个点—切换—再走回来更优。
求出这个真正的切换的代价，剩下的一定在树上的最短路径走（你中间走出去再走回来，如果不切换一定不如不走出去，切换了也不比切换过的最小代价优）。
这个切换的代价可以直接两遍 dp，从儿子转移/父亲转移。
之后就可以倍增了，预处理这个点在 0/1，上面的点在 0/1（距离 $2^i$）的最小代价，分别求出到 LCA 的，再合并起来即可。

1540C2

如果操作后 $a_i$ 变了，说明 $a_i>\frac{a_i+a_{i+1}-b_i}2$，即 $b_i>a_{i+1}-a_i$。如果操作后 $a_{i+1}$ 变了，说明 $a_{i+1}<\frac{a_i+a_{i+1}+b_i}2$，即 $b_i>a_{i+1}-a_i$。发现两个数要么都变要么都不变。
如果变了，现在这两个数的和还是 $a_i+a_{i+1}$。条件是两个数之差 $<b_i$，在两个数之差变成了 $b_i$。
所谓收敛就是做不了了，因为这个状态是有限的。要求最后所有 $a_{i+1}-a_i\geq b_i$，但是你把 $a_{i+1}-a_i$ 变成了 $b_i$ 的同时会使得 $a_i-a_{i-1},a_{i+2}-a_{i+1}$ 都会减小，且你手动操作只会造出 $b_i$，造不出比 $b_i$ 大的。
这就说明如果最终序列如果有 $t_{i+1}-t_i>b_i$，那么一定没有操作过 $(i,i+1)$（否则就变成 $b_i$，之后无论如何都不会更大），把 $i$ 称为断点。
你只需要求出 $t_1$ 的最小值。假设你知道了答案中第一个断点的位置，由于断点没有操作，所以前后的和都是不变的，前面一段根据 $\sum_{i=1}^k t_i=sa_k \Leftrightarrow \sum_{i=1}^k (t_1+sb_{i-1})=sa_k \Leftrightarrow kt_1+tb_{k-1}=sa_k$ 即可以解出 $t_1=\frac{sa_k-tb_{k-1}}k$（$sa$ 是 $a$ 的前缀和，$sb$ 是 $b$ 的前缀和，$tb$ 是 $sb$ 的前缀和）。最小值一定在所有断点形成的值的集合中。
对于任意的 $k$，一定满足 $\sum_{i=1}^k (t_1+sb_{i-1})\leq \sum_{i=1}^k f_i$，而无论怎么操作一定有 $\sum_{i=1}^k f_i\leq sa_i$，故一定有 $t_1$ 是所有断点求出的值的最小值。
dp 记录当前位置 $i$，$sa_{i-1}$ 的值（$tb_i$ 是固定的，可以预处理），算出当前 $sa_i$ 的界后直接前缀和优化转移。
设 $m$ 为 $\max_i {c_i}$。如果 $sa_i=i\cdot m$ 都不满足，答案必定为 0；如果 $sa_i=0$ 都满足，答案必定为 $\prod (c_i+1)$。
剩下只有 $x\in (\min_i {\frac{-tb_i}i},\min_i {\frac{i\cdot m-tb_i}i}]$，此时 $x$ 只有 $m$ 个候选，全部处理出来即可。

81E

每个连通块都是树（重边）/基环树。
树显然好做，直接树形 dp。基环树一般也考虑断掉一条边变成树。
树上就可以求出树的答案，但是这样不一定是最优的，因为断掉的边可能也在匹配中。不过可以发现如果断掉的边匹配了，那么和它两端点相邻的边一定不能选，拿出一条相邻的边，断掉它再做一次即可。

232C

首先 $a,b$ 很小，$fib_{79}>10^{16}$，所以可以缩小 $n$，和 $80$ 取最小值。
分情况讨论，如果 $a$ 在 $n-1$ 层且 $b$ 在 $n-2$ 层，此时必须走连接两部分的边，所以 $a$ 必须走到开头或结尾，$b$ 必须走到结尾；都在 $n-2$ 层，直接在 $n-2$ 层走就行；都在 $n-1$ 层，一种是直接走，还有可能一个到开头，一个到结尾，再通过两条边连起来。
处理一下 $a,b$ 在每一层的位置，再加上开头结尾，每一层 4 个点两两之间距离处理一下即可。

1010E

先求出包含 $n$ 个点的最小矩形。
对于每个询问，如果在矩形内就一定包含，如果扩展到把这个点包含的最小矩形包含了 $m$ 个点中的其他点就一定不包含，否则未知。拆一下变成类似三维偏序的东西就可以做了。

991F

容易发现不会出现两个纯数字相乘，也不会出现两个纯数字相加。
题目非常高素质的给出了 $10^{10}$ 的解法，所以剩下最多 10 位（它自己本身就是一个表示）。
如果有两个加号，而且因为不能都是数字，所以至少是 $a^b+c^d+e$，已经有了 9 位，且值显然很小。
所以只有三种表示法：$a^b,u+v,x\times y$。其中 $a,b$ 必须是数字，$u,v$ 可以是表达式（此时不能有加法且最多只能有一个乘号，一个幂次），$x,y$ 必须形如 $p^q$。都讨论一下即可。

23D

由于是四边形的三条边，所以三条边一定相邻。
枚举中间的那条边，假设它的端点是 $p,q$，中点是 $b$。
由于边的长度相同，所以 $p$ 在 $ab$ 的垂直平分线上，$q$ 在 $bc$ 的垂直平分线上。
实际上两边的也相等，不妨把 $c$ 关于 $p,q$ 对称过来，那么 $a,b,c'$ 到 $p$ 的距离都相同，即可求出 $p$，同理也可求出 $q$ 以及另外两个端点，再判断是否是凸的即可。

1031F

首先只需要考虑每个质数的幂次形成的集合。
一个集合的数字和很小（不超过 log），且很多达不到。跑一下发现集合只有 289 个。
但是中间过程不一定，考虑扫出所有幂次和不超过 log 的（保留多少其实可以手动试），再从 289 个起点开始跑 bfs。

240E

bfs，每个点如果入边为 0 则一定是最优的不会更改，入边为 1 可能之后还会更改（但是为 1 的两两之间地位相同）。
直接做，每个点只会经过最多两次。

1473G

由于有一个 $|a_i-b_i|\leq 5$ 的限制，容易想到把 $a_i$ 和 $b_i$ 当成一组做。
容易发现，一列是 $x$，一列是 $x+1$，那么两列都可以走到另一列相邻的。
前 $a_i$，每个都可以往右或右上走；后 $b_i$，倒着过来，也是可以往左或左上走。
枚举这一组开头的行，下一组开头的行，枚举中间的行，两边用组合数取一下哪几次往上走即可。
枚举中间的行其实没什么用，因为你可以把其中一个组合数的下面翻转，那么下面的和就固定了，用范德蒙德卷积合并。
枚举这一行，再枚举上一行，乘上一个组合数就可以转移过来。这是一个卷积，可以用 NTT 优化。
由于题目的限制，行数最多只有 $5n$，所以复杂度是 $O(n^2\log n)$。

568D

选了 $k+1$ 条线必须有两条有一个交点，然后和它们两个交点相交的其它线之后也不需要考虑。
直接这样递归可能会超时，不过还可以优化，因为一个在至少 $k+1$ 条线上出现过的点一定要选（两条不同的线最多一个交点，如果不选，这些线两两不能一起选，至少要分成 $k+1$ 组）。
当 $n$ 达到 $O(k^2)$ 的级别时就一定会出现至少 $k+1$ 条线上出现过的点，可以随机两条线然后判断它们的交点是否可行。这个概率不小，跑个 100 次足够了，之后的再来跑递归。

185D

牛逼数论题。先考虑两个数的 gcd。
假设 $\gcd(k^{2^x}+1,k^{2^y}+1)=d$，则 $d|(k^{2^x}+1),d|(k^{2^y}+1)$。
$k^{2^x}\equiv k^{2^y}\equiv -1\pmod d$，可得 $\left(k^{2^x}\right)^{2^{y-x}}\equiv (-1)^{2^{y-x}}\equiv 1\equiv -1\pmod d$，即 $d|2$，$d=1$ 或 $2$。
由于两两 $\gcd$ 只会是 $1,2$，所以有没有 $4$ 的倍数呢？$x=0$ 显然不满足，假设 $x>0$ 有，即 $\left(k^{2^{x-1}}\right)^2\equiv -1\pmod 4$，但不存在完全平方数 $\bmod 4=0$。
所以只需要看是否都不是 $2$ 的倍数，也就是 $k$ 是否是偶数，是偶数就直接求值，是奇数就再除掉 $2^{r-l}$。
现在就要求所有数的乘积，先令 $k$ 变成 $k^{2^l}，就变成类似二进制表示，每个 2 的幂次选不选，可以表示出所有的 $k^0,\cdots,k^{2^{r-l+1}-1}$，当 $k=1$ 时特判，否则就等比数列求和即可。

1389G

一个边双是可以定向使得两两都能到达，所以可以先缩起来，权值变成里面特殊点的权值之和。
现在变成一棵树，又可以发现对于只有根是关键点的子树，可以直接定向成从上到下，对子树外的点不影响，且子树内的定双向也没有意义。子树里所有点的答案和根的答案一样，如果根是饱和的，那么所有点都是饱和的，把 $c$ 都加到根上删除掉除根以外的点即可。
不妨以关键点为根，此时所有叶子都是关键点。容易发现饱和点一定是个连通块，且只有连通块内部是双向边，其它都指向连通块是最优的。换根 dp 即可。

1155F

边双每个点至少在一个简单环。考虑每次加入一个简单环（更具体说是一条两端在已经加入的点上的一条链）。
预处理 $x,y$ 是否能和 $s$ 中的点形成一条链，转移就枚举子集，看是否存在两端点使得能是一条链（对的原因是因为耳分解），只需要知道是否存在两端点所以可以只枚举一个另一个 and 一下。
时间复杂度 $O(n3^n)$。

1393E1

给每个串末尾加一个很小的字符 '\0' 用于不同长度的串比较。
容易想到设 $dp_{i,j}$ 表示删掉第 $i$ 个串的第 $j$ 个字符（不删即删去 '\0'，好处是串长不变）。直接暴力比较复杂度过高。
但其实一个串不同的删法的大小关系是容易比较的。假设删掉 $x,y(x<y)$，$x$ 前面的不需要考虑，而第一个串（$x+1\cdots y$）要和第二个串（$x\cdots y-1$）比较，如果还是一样说明整个都一样（后面的也不需要考虑），每个位置预处理一下往后第几个位置会出现不同。
现在就可以双指针比较了，比较的过程也可以用上面类似的方法，上一行删去 $x$ 这一行删去 $y$，$x$ 之前的对应比较（可以预处理每个位置开头 lcp，中间每个位置处理和位置差为 1 比较的 lcp）。不过哈希加二分应该也行。

975E

根据物理知识，重心一定在固定点垂直下方。
凸多边形的重心可以通过先三角剖分，求出每个三角形的重心，再按照面积加权平均。
根据一个点和一个重心可以求出另外一个点（预处理重心和每个点的角度差，根据固定点即可求真实角度）。

446D

预处理出从 $u$ 走到 $v$ 中间不经过其它陷阱的概率。
对于非陷阱点，可以枚举一个出边以概率走过去。这样可以求出非陷阱点到陷阱点的概率（高斯消元）。
对每个陷阱点再这样求一下，就可以求出陷阱点到陷阱点的概率，然后矩阵快速幂即可。

1562F

当区间没有素数的时候，可得 $n\leq 85$，暴力求解。当 $n>3$ 时 $a_i$ 就等于它和其它数 lcm 的 gcd，$n=3$ 特判即可。
$n>85$ 则一定有素数，随机 $200$ 个下标，每个下标随机 $25$ 个位置求它和那些数的 lcm 的 gcd，找到回答中所有质数最大的那个，通过它求出所有的答案。

1379E

有解的 $n$ 一定是奇数，否则构造不出每个点都有 0/2 个儿子的二叉树。
先构造出一个上界：一条长度为 $\frac{n+1}2$ 的链，再给除下端点外的每个点加一个儿子。这样链上除了最下面两个点都是可以的，也就是有 $\frac{n-3}2$ 个点都是可以的，可以发现这样构造就是最大的（不平衡必须有一个儿子大小大于 1）。
再构造出一个下界：容易想到构造完全二叉树，在 $n=2^t-1$ 时能构造出所有点都是平衡点，否则会有一个不平衡点。
然后考虑下界到上界调整，如果 $k<2$ 可以直接判断和构造，否则可以求 $n-2,k-1$，再造一个根连构造的结果和另一个点（要 $n-2>1$）。当 $k=0,1$ 的时候特殊考虑，这样每一步一定有 $k\leq \frac{n-3}2$。
但是你要求最后 $k=1$ 时变成的 $n-2(k-1)$ 不是满二叉树，如果本身就不是那么就可以，否则考虑最开始拿掉两个点（要求点数够多）。发现 $n=9,k=2$ 无法构造（$n-2(k-1)$ 是满二叉树，且你拿掉两个点后根节点直接平衡了，也不行）。

1379F2（*，同 F1）

$2n\times 2m$，先把它分成若干 $2\times 2$ 的小块，每一块选择一个。
每个小块是左上一个白格子，右下一个白格子。删掉一些白格子就使得某些小矩阵的方案固定。
一个矩形放了右下就会使得下方、右方和右下方的三个也只能放右下。所以无解就是一个 R 的右下方的矩阵中有 L。
维护每行最右边的 L 和最左边的 R，新加入的时候就线段树维护之前行的 R 最小/ 之后行的 L 的最大值，和当前区间是否已经有不合法的。

802O

首先有个裸的最小费用最大流建图，不过显然过不去。
毕竟都可以网络流了，所以一定是个凸函数。
考虑 wqs 二分，二分完之后 $a,b$ 可能变成负的。
考虑负的怎么做，可以用带悔贪心，从后往前，要么选择后面 $b$ 最小的配对，要么替换掉 $a$ 最大的匹配中的 $a$，要么不做操作。如果现在 $a$ 选了把 $a$ 加入优先队列，$b$ 没配对把 $b$ 加入优先队列。每次选最优决策即可。

504D

直接 bitset 优化维护线性基，其实难点在于大整数转化为二进制（可能先转 $2^k$ 进制再转过来）。
询问就一位一位问，记录一下哪些异或过了。
设 $V$ 为读入的数字在二进制表示下的位数（$V\leq 2000$），时间复杂度为 $O(\frac{nV^2}w)$。

1152F1

这个两两不同不好处理，因为毕竟也不能开 $2^n$ 状态记录。
一般有几种处理方法：每次加入的时候给比它大的加 1；容斥；不按照常规下标顺序，按照值域顺序。
前两种不太可行，考虑第三种，从小到大加。那么第二个条件就变成最后一个数 $\leq n$，后面一个元素和它的限制不需要考虑，需要考虑前面的数和它的限制，它不能比前面的数超过 $>m$。假如加入数字 $x$，前一个数必须在 $[x-m,x-1]$，二进制状态维护每种是否出现过。
再记录一下当前的 $x$ 和选的数个数就可以做了。由于转移对于不同的 $x$ 都相同，所以可以把 $x$ 这一维矩阵快速幂。时间复杂度 $O(\left(k2^m\right)^3\log n)$。

687E

TOF 就是让你每个点选择一条出边。
如果到了一个环，那么这个环必须花将近 $999\times tot+1$ 次才能走完，所以一定会让在环上的点数尽量少。
所以总步数是 $998\times tot_1+n+tot_2$，$tot_1$ 是在环上的点数，$tot_2$ 是环的数量，和访问顺序无关。
如果一个点没有出边，所有能到达它的点都可以不在环上（都往它方向指，或者以这个点建反图跑 dfs 再每个点选父亲）。
先缩点，有出边的 SCC 可以通过别的解决，没有出边的只能自己解决，找一个最小环把其它都指向最小环。数据范围很小，直接暴力即可。

273E

首先这个 $l,r$ 具体的值并没有用，只需要知道 $r-l$，假设 $r-l=x$，每次可以变成 $\frac x3$ 或 $x-\frac x3$（除法向下取整）。
由于只能从两个转移过来，所以 sg 值不超过 2。直接打表，发现段数不超过 100 段。
然后就可以直接 dp，每次选一种异或一下，记录当前异或值即可。

1291F

不同元素的个数，考虑对每种第一次出现计数。
把所有的数按照 $k/2$（$k=1$ 时为 $1$）个分一块，两个块之间都做一次。
这样需要的次数是 ${\frac{n}{k/2}\choose 2}\times k$，在同样的步长时没必要重置。

1146H

每个凸五边形和五角星是一一对应的。
凸包要求极角是递增的，先把 $O(n^2)$ 条边拿出来，按照极角排序，然后 dp。
dp 记录一下起始点、当前点和选的边数，枚举每条边，从边的起点转移到终点。
最后的答案是其中起点等于当前点，边数为 5 的方案数之和。

1012D

相邻相同的可以只保留一个，因为从中间分开没有必要。
现在就是交替的了，如果两个开头不同就是各取一个长度为奇数的前缀交换，长度减少 2；开头相同就是分别取长度为偶数/奇数的前缀交换，长度减少 2。
在一个串长度为 $1$ 或两个串开头相同且长度为 $2$ 时只能减 $1$。所以尽量要让两个串长相差尽可能小。
两种基本情况短串就取开头一个，长串长度判断一下。特殊的情况也是交换长度近似。
读入的时候压缩一下，链表维护字符串，分类讨论即可。

1359F

先二分答案，然后就变成求是否有线段相交。
类似扫描线扫过去，分成插入和删除。用 set 来维护，插入的时候看上一条和下一条线段是否相交。
因为 set 任何时候相邻两个都没有交点，所以相对顺序不会变。

612F

要权值从小到大，可以设 $dp[u]$ 表示 $u$ 经过权值不超过它的点全部走完，到它的最小答案。
权值比它小的走完了，停在 $v$。由于权值和 $u$ 权值相同的点都必须经过，且最后到达 $u$。一定先往左右走到某一个权值相同的，然后再考虑是否每条边都经过，如果是，额外需要的就是两点最短路的距离；否则假设 $x$ 边未经过，则额外增加两点到 $x$ 的距离，减少 $x$ 边的距离。只需要考虑 $x$ 在哪个弧，删去弧上最大的边即可。
时间复杂度 $O(n^2)$。

1279E

重新排列之后还是一样，所以每个环所在的位置是连续的，且第一个位置就是环上最大的位置。
先求出一个长度为 $n$ 的环的方案数，首先 $n$ 和 $1$ 一定连接（也就是要求 $1$ 的位置是 $n$），剩下的可以是任意排列（$(n-2)!$，特判 $n=1$），排列的前一个的下标的值是后一个。
然后就可以用 dp 合并若干个，由于位置连续，枚举一下这一段的长度即可转移，这部分的复杂度是 $O(n^2)$。
怎么求第 $k$ 大？枚举第一段长度 $x$（对应着第一个数），后面的总方案数和第一段内部的方案没有关系，所以就可以确定第一段的值，然后再考虑第二段（递归），所以关键在于处理第一段。
第一段就是只要不成小环就行，还是一位一位确定，就会有若干条链，除了 $1\rightarrow n$ 所在的链其它的链顺序还是随意，方案数是 $(tot-1)!$（$tot$ 是链的数量）。

60E

下一秒会长出 $a_1+a_2,a_2+a_3,\cdots,a_{m-1}+a_m$。设原先总和为 $s$，则现在总和为 $3s-a_1-a_m$，且 $a_1,a_m$ 不变。
前 $x$ 秒后的值号算，然后就是要重新排序，最小值显然不变，变的是最大值。
手推一下相邻两个之间产生的最大值，列出来就可以发现应该为 $fib_xp+fib_{x-1}q$，算出最大值再算后 $y$ 秒的即可。

1455G

把一对 if-end 当作一个块，是一个嵌套结构。
设 $dp(i,j)$ 表示从第 $i$ 个块出来是 $j$ 的最小花费（初值是固定的，否则不会进入 if）。
线段树维护区间加，合并，区间最小值即可（map 启发式合并也可以）。

1505G

愚人节赛题。第二个样例可以看出每个字母的表示法应该是一样的。
是一个 3*2 的矩阵，每行中 1 的个数和每列中 1 的个数。这个矩阵是数字的盲文。

513F1

二分答案，然后使用网络流经典建图。
原点向男人连 1，男人向在时间内能走到的房子连 1，房子向在时间内能走到它的女人连 1，女人向汇点连 1。
房子只能住一个人，所以要把房子拆成两个点，之间连 1。变性人其实只能和一种匹配，如果和两种都能匹配则一定矛盾。所以就看哪种人少一个，认为变性人就是那种人即可。

1109C

这个题意好奇怪，我还以为我看错题了。
容易发现可以用线段树维护修改操作和区间最小前缀和、区间和、区间最后一次操作的值。
询问的时候可以在线段树上二分。

241D

看上去不太能做。
假设你从 1 开始保留 $m$ 个数字，然后再从里面选，这样不同的异或和个数分布应该是比较均匀的，可以近似为 $2^m/m$。
保留前 $25$ 个，则异或和为 $0$ 方案数是最大的 $p$ 的 $25$ 倍多，不出现 $\bmod p$ 值为 $0$ 的概率极小。

303D

这个 142857 循环在十进制下等于 $\frac 1 7$，想到可以把别的数也表示成 $\frac p q$ 的形式。
假设这个整数在 $b$ 进制下是 $\overline{a_1a_2\cdots a_n}$，不妨设它等于 $\frac p q(\gcd (p,q)=1)$。无限纯循环小数一定有 $\gcd(b,q)=1$（一定可以表示成 $\frac x {b^n-1}$ 的形式，而 $\gcd (b^n-1,b)=1$ 一定成立。其实反过来也是成立的，可以设循环前长度最小的数然后反证矛盾）。
设 ${x}$ 表示 $x$ 的实数部分，则要求 ${{\frac p q},{\frac {2p} q},\cdots,{\frac {np} q}}={{\frac p q},{\frac {bp} q},\cdots,{\frac {b^{n-1}p} q}}$，这是两个无序集合。${x/q}={y/q}$ 等价于 $x/q-y/q\in \mathcal{Z}$，也就是 $x\equiv y\pmod q$。
现在就变成 ${p,2p,\cdots,np}={p,bp,\cdots,b^{n-1}p}$（都是 $\bmod q$ 意义下），而 $\gcd(p,q)=1$，所以 ${1,2,\cdots,n}={1,b,\cdots,b^{n-1}}$。又 $b,q$ 互质，可以推出 $q>n$（否则 $n\bmod p=0$，而右边不存在）。进一步可以扩展到 ${1,2,\cdots,n}={b^i,b^{i+1},\cdots,b^{i+n-1}}$，而一定存在 $b_i=2$，所以等价于 ${2,2b,\cdots,2b^{n-2}}={2,4,\cdots,2n}$。
如果 $n$ 是奇数，去掉相同项可得 ${1,3,\cdots,n}={n+1,n+3,\cdots,2n}$，也就是 $0<n+1\bmod q\leq n$，所以 $q<n+1$，矛盾。
如果 $n$ 是偶数，去掉相同项可得 ${1,3,\cdots,n-1}={n+2,n+4,\cdots,2n}$，也就是 $0<n+2\bmod q\leq n-1$，所以 $q<n+2$，所以 $q=n+1$，此时 ${1,2,\cdots,q-1}={1,b,\cdots,b^{q-2}}$，所以 $q$ 是质数，求出 $x$ 内最大的 $q$ 的原根，$q$ 不是质数直接输出 -1，从大到小枚举 $x$，枚举次数显然不会超过 $q$（$\bmod q$ 只有 $q$ 种）。

1425B

这是个大讨论题。首先可以发现它是花瓣状的，若干个环，1 是公共点。
讨论结束的时候两人的位置。
都在 1。说明他们经过了所有环且步数相同，把所有环分成两部分且长度相等。
都在某个环的同一节点（非节点 1）。设这个环的长度为 $l$，红色走了 $x$（$1\leq x\lt l$），另一个走了 $l-x$。两个的步数差为 $(l-x)-x=l-2x$。在剩下的环选出两个不交的子集，使得差为 $l-2x$。
都在某个环上且隔了一条边。
两人都不在 1。设这个环的长度为 $l$，红色走了 $x$（$1\leq x\lt l$），另一个走了 $l-1-x$（$1\leq x\lt l-1$）。两个的步数差为 $(l-1-x)-x=l-1-2x$。在剩下的环选出两个不交的子集，使得差为 $l-1-2x$。
其中有一个在 1。此时 $x=0$ 或 $x=l-1$。除了步数差的限制，还要保证其它所有环都走过了。
可以 dp，记录考虑到第几个环，当前两者之差，之前是否有环没选。转移就考虑当前环是谁走或都不走。
情况 1 必须所有都走完，情况 2,3 枚举一下环也好做（注意最后一个环也可从两个方向进入）。
本质不同环长只有 $\sqrt n$ 种，且方案只和环长有关，直接暴力是 $O(n^2\sqrt n)$ 的。
不过也可以分治，到叶子节点的时候所有剩下的都加入了，也可以求出要的 dp 值。

145D

先找出所有幸运数字的位置。
枚举第一个区间（端点都是幸运数字），那么第二个区间就一定不包含若干个数，被分成若干个小区间。
第一个区间加入数的时候，给对应的后面相同的位置标记（对于值已经标记过的不标记），set 维护方案数即可。

1654F

倍增长度。
设 $r(l,x)$ 表示所有下标异或 $x$ 的 xoration 的前 $2^l$ 个字符是什么，容易发现 $r(l,x)=r(l-1,x)+r(l-1,x\oplus 2^{l-1})$（+ 表示字符串拼接）。
设 $k(l,x)$ 表示所有下标异或 $x$ 的 xoration 的前 $2^l$ 个字符的字典序排名（排名指同一个 $l$，不同的 $x$ 的 $r(l,x)$ 中排到字典序第几小，相同的 $r(l,x)$ 排名相同）。
不需要真正记录 $r(l,x)$。类似 SA 那样双关键字排序，每次更新维护 $k(l,x)$ 即可。

1601E

你只需要 $l,l+k,l+2k,l+3k,\cdots$ 天激活一张。
当天激活的一张，可以是之前任何一天买的，显然最优策略是在之前费用最低的一天买。
考虑 $k=1$ 的情况，要求的就是前缀最小值之和。直接每个点向之后比它小的第一个连边，每次倍增跳。
其它情况也是类似 $\bmod k$ 分类，每个值变成了前 $k$ 天价格的最小值（第一天特殊考虑）。

1051G

操作可逆，先变成一个比较好看的形式。
对于一个连续段，可以先把它合并到开头，再平摊出来。
如果平摊的时候又碰到了另一个，那么继续合并。
维护每个连续段，连续段里加入一个数就把 $r$ 往右移动 $1$。
现在需要合并两个连续段的权值，然后再按照大小顺序，第 $i$ 小的乘上 $i-1$ 加起来。
这个一种是手写平衡树，然后启发式合并；还有一种可以写权值线段树维护。
权值线段树维护时记录区间数的个数和区间和，区间答案，合并使用线段树合并即可。

1654G

最多能增加多少势能是固定的，也就是当前点的高度。
如果能移动到有高度相同的点，你可以反复横跳一会儿。
如果有多个可以横跳的点，那么你一定在经过的最后一个可以横跳的点再横跳。
枚举一个能走到的横跳点 $x$，那么操作数是 $2(h_i-h_x)+h_x=2h_i-h_x$。
有一个结论是横跳点高度之和是 $\leq 2n$ 的，因为每新增一个旁边有同样高度的点，一定会新增一条完整的长度为它的高度的路径。
因为总和是 $O(n)$ 的，所以本质不同的高度就是 $O(\sqrt n)$ 的。
求出所有横跳点的高度，对每种高度再求出能到这些横跳点的有哪些点。
使用 bfs，时间复杂度 $O(n\sqrt n)$。

1442D

如果有两个数组都只选了一部分但没选完，一定可以调整使得一个数组选完（考虑两个数组最后一个选的数的大小关系）。
现在就是一大堆完整的数组和一个不完整的数组，分治，到最后一层留下的是不完整的数组，其它完整的在分治时用背包加入/撤销维护。
时间复杂度 $O(nk\log n)$。

625E

相对顺序不会变，只是会少一些点。每个点只有可能弹出下一个点。
找出最早的能弹出下一个点的点和时刻，把下一个点弹出。
更新的时候不仅要更新当前点和新的下一个点，还得更新上一个点和当前点（因为当前点的 $a$ 发生了改变，注意同时也要改变 $p$，之前的是每步走 $a$ 而不是 $a-1$）。

30E

容易想到两种枚举法：枚举 prefix 开头或 middle 中间位置。
考虑枚举 middle 中间位置，那么两侧的回文一定延伸越长越好，因为即使方案不是这样，你额外占据了属于 prefix/suffix 的位置，则新增长度 2，最多减少长度 2（一个在 prefix 一个在 suffix），所以一定不亏。
剩下的就是求出某个位置左边是否有和 suffix 对称且长度 $\geq x$，这个可以把原串反过来当文本串，原先的原串当模式串跑 kmp。

1137E

记录斜率。每次 3 操作后面的数都比前面的数加的多，且所有加的数非负。每个新加入的段只需要考虑第一个位置。
1 操作可以直接把当前记录的斜率清空，因为后面的数非负且之后会越来越大。
3 操作就是加上 $b$（相对大小关系不影响），每个斜率加上 $s$。显然斜率 $>0$ 的位置就可以删了，后面的数比前面大则之后一定越来越大。
维护一个单调栈，表示 $i$ 和斜率，每次如果栈尾斜率 $>0$ 则弹出。

1635F

枚举 $i$，考虑它和 $w_j\leq w_i$ 对答案的贡献 $|x_i-x_j|\cdot (w_i+w_j)$。
如果存在另一个 $w_k\leq w_i$ 且 $|x_i-x_j|\leq |x_k-x_j|$ 则 $(i,j)$ 没有意义。
则只有 $w_i$ 左右的第一个 $w_j\leq w_i$ 是有用的，$w_i$ 与其它的 $w_k$ 形成的 $(i,k)$ 一定不如 $(j,k)$。
现在可能为答案的数量很少，所以可以直接先求出它们的答案，询问的时候区间询问。
现在问题变为有若干个带权区间，每次询问一个区间，问被完全包含的带权区间最小值是多少。
把所有区间按照 $r$ 排序，插入就更新位置 $l$，询问就查询后缀最小值。

1238G

这题挺有意思。拿个 set/map 维护当前能额外购买水的价格和量（注意容量限制）。
从 $i$ 移动到 $i+1$，需要从 ds 里拿出一个代价最小的买。
对于一个能买水的位置，先假设全部都能买，丢到 ds 里。但是因为有容量限制，所以一直丢价格最大的直到容量不超过 $c$。
显然对于不能买水的位置不需要一个一个跳，中间的一段直接跳过去即可。

1452G

显然 Bob 的策略固定，所有的都往 Alice 方向移动。
Alice 要选择一个终点，使得往那个方向走，Bob 到过程中的所有点的时间都比 Alice 的时间长。
先处理出 Bob 到每个点的距离，记作 $d[u]$。
问题就变成对于每个根，找到一条路径，使得每个点距离减去深度必须大于 0。
假设最后到的节点 $u$，和它距离不超过 $d[u]-1$ 的起始节点 $s$ 都可以用 $d[u]$ 来更新。
考虑用点分树，每个点往上跳所有分治重心，更新分治重心对应的数组。最后每个点再往上跳分治重心求出自己的答案。
事实上没必要点分树，上面说点分树只是为了描述直观，可以在点分的时候直接处理。

367E

前缀左端点个数 $\geq$ 右端点个数。
dp，四种决策：
不放（当这个位置不为 $x$ 时）；
放一个左端点；
放一个右端点（当这个位置不为 $x$ 时）；
放一个左端点和右端点

878C

如果 $A$ 可能赢 $B$ 且 $B$ 可能赢 $A$，则认为它们等价。
或者直接将 $A$ 可能赢 $B$ 连一条边，缩强连通分量。
不过这题比较牛逼，可以用 set，把 $A$ 可能赢 $B$ 且 $B$ 可能赢 $A$ 的当作相等，其它的就有大小关系。
插入的时候直接 find 找相同的合并即可。

827D

对图中每条边进行讨论
非树边，把这条边的权值最大改为路径上边权最大值 $-1$ 即可；
树边，最大边权使得这条边依然是树边，非树边的路径经过这条边的边权最小值 $-1$。
直接树剖预处理一下每条边即可。

1437F

大于前面最大值的，不会超过 log 次。
考虑如果固定了前面的最大值，那么之后所有比它的一半要小的可以任意放。
直接 dp 记录最大值填到 $a_i$，转移枚举上一个最大值 $a_j$，则比 $a_i$ 的一半要小且比 $a_j$ 的一半要大的都可以填，序列长度也一定固定，就是比 $a_i$ 一半要小的 +1，转移系数是个排列数。

351D

如果刚开始就能重排，答案就是颜色数量。
但是现在第一次不重排，如果初始存在某种颜色的位置是等差数列那么答案还是颜色数量，否则要 +1。
直接用 deque 存每种颜色的所有相邻位置差值，看是否完全相同。存 deque 里相邻不同的位置数量即可。

338D

如果是 $a_l\mid \gcd(i,j+l-1)$，就可以直接拆开，变成 $a_l\mid i$ 和 $a_l\mid j+l-1$。推一下可得 $lcm{a}\mid i$，而一个最小正整数解 $j_0$ 可以用扩展 CRT 求出。
则 $i$ 取 $lcm{a}$ 就是最优的，它是最小的可能取值，且取它的倍数只可能使得 $\gcd$ 更大。
而 $j$ 的所有合法取值形如 $j_0+k\cdot lcm{a}(k\geq 0)$，由于 $i=lcm{a}$，根据欧几里得算法的理论，$k$ 取 $>0$ 和 $k=0$ 得到的 $\gcd$ 是相同的。
故综上所述 $i=lcm{a},j=j_0$，再回代判断一下是否满足所有题目要求的条件即可。

1270F

这种倍数关系的，没啥思路可以考虑根号分治。
$k(s_r-s_{l-1})=r-(l-1)$，说明 $k$ 和 $s_r-s_{l-1}$ 必有一个 $\leq \sqrt n$。
当 $k\leq \sqrt n$ 时，变成 $ks_r-r=ks_{l-1}-(l-1)$，直接枚举 $k$，搞个桶计算一下方案；
当 $k>\sqrt n$ 时，此时 $s_r-s_{l-1}<\sqrt n$，枚举它的值，双指针对于每个 $l$ 求出满足条件的最小/最大的 $r$，计算一下方案数。

1566F

先去掉一些没用的线段，比如包含其它线段的线段。
现在就可以排序，左端点递增且右端点递增。则初始每个点最终会访问一个区间的点。
容易想到一个二维 dp，记录之前访问了前多少个区间，现在到哪个点。
转移就枚举新覆盖到了哪个区间，计算一下。但这样显然复杂度太高。
考虑优化一下，覆盖需要的代价还是容易算的，你只要知道是先往左还是先往右，先往左的话就是左边要算两遍，否则是右边要算两遍。把往右的在 $i+1$ 计算，这样第二维就只有 $0/1$ 了。
新的转移要考虑 $i-1$ 往右，$i$ 往左走多少是最优的。可以发现能直接暴力枚举中间的区间，因为区间总数是 $O(m)$ 的。

本文永久更新地址:

https://blog.hydd.cf/p/codeforces_2600-2900/