水题乱做

CodeForces-1017G

简单转化之后用树剖维护最大后缀和即可，2 操作需要把多余的值减掉。

CodeForces-1017H

对于每个 $k$ 都跑一遍莫队，时间复杂度是 $O(n\sqrt q\sqrt m)$ 的（$m$ 是 $k$ 的种类数），记得每次跑都要重新算块长。

CodeForces-1152F1

考虑从小到大插入数，发现能 $v$ 加入的位置只有开头和 $v-m\sim m$ 之后，状压即可。

CodeForces-1152F2

在 F1 的基础上用矩阵快速幂优化即可。

CodeForces-1630E

考虑 Burnside。因为每个间隙的贡献都一样，所以只要算一个间隙的贡献即可。

LibreOJ-10092

直接缩点然后 DAG 上 DP。

LibreOJ-3714

考虑将条件转化为：对于所有 $k$，$[1,k]$ 中的数之和 $>k$。然后考虑第一个相等的位置，进行背包。
考虑把背包两维互换，考虑 $\ge k$ 的数有几个，然后把个数当成物品进行完全背包，因为数互不相同，所以个数最多有 $\sqrt n$ 个。
最后考虑容斥掉不合法位置在前面的情况，类似 CQD 算贡献即可。

HDU-4997

直接状压 DP，对于所有子集算出构成连通块的方案，然后类似的就可以算出构成边双的方案，时间复杂度 $O(4^n)$。

HDU-7380

直接拟阵交即可，被卡常了所以没过。

洛谷-P6672

先把所有数 $-1$，然后在最后加上一个 $-1$，然后全部取反并翻转，就可以用以上引理计算。

洛谷-P4548

使用概率生成函数或者直接 DP 推式子，结论题。

CodeForces-960G

考虑枚举 $n$ 所在的位置，那么就变成两个独立的问题，然后答案就是第一类斯特林数，求一个第一类斯特林数·列即可。

LibreOJ-3097

直接 CDQ 优化建图跑流。

LibreOJ-3696

发现每条边存在的时间一定是一个区间，然后并查集找到第一个矛盾的另一条边即可。

CodeForces-838C

假设每种数分别有 $a_1,\dots,a_k$ 种，发现如果当前局面数 $f=\binom{n}{a_1,\dots,a_k}\equiv 0\pmod 2$，那么先手可以随意换先后手，那么就是先手必胜。
否则根据 Lucas，为了保持 $f$ 是奇数，只能选择 $\operatorname{lowbit}(n)$ 所在的那种数，所以是否必胜之和 $n$ 的奇偶有关，然后方案数子集卷积优化即可。

CodeForces-1361E

因为 $\ge 20$，所以考虑随机出一个合法点，然后以这个点为根，建出 DFS 树，然后根据一些性质即可求出所有合法点。

洛谷-P5068

考虑每一种伤害的贡献，每种伤害的贡献会变化 $O(\frac n i)$ 次，所以一共是 $O(n\log n)$ 次，然后用树状数组维护即可，时间复杂度 $O(n\log^2 n)$。

洛谷-P5631

直接线段树分治然后并查集即可。

洛谷-P6097

在或卷积的基础上加一维 $\operatorname{popcount}$，然后做背包即可。

洛谷-P6442

直接高维前缀和（FMT）即可。

洛谷-P3704

考虑莫反，然后现枚举 $g\cdot d$（$g,d$ 分别为 $\mu$ 的下标和 $\gcd$），即可整除分块计算答案。

洛谷-P3312

与上面一题的思路基本相同。

洛谷-P4366

可以把 $\operatorname{xor}$ 拆成 $\log$ 条边拼起来，这样边数就只有 $n\log n$ 条，就可以跑 Dijkstra 了。