字符串

能够被分为两个回文串的回文串周期一定整除长度。

如果一个字符串有长度为 $d_1, d_2$ 的周期，那么 $\gcd(d_1, d_2)$ 也是它的一个周期

随机生成的字符串，后缀树树高是 log 的

ds

区间问题可以右端点扫描线，也可以枚举最小值

如果三维偏序问题出现了 $\forall i, x_i<y_i$ 的情况，可以把这个看成区间，用莫队维护，当完全包含区间的时候再计入贡献，剩下一维用分块维护。

众数一般来说都是根号分治

如果所有数出现次数 $\le \sqrt n$ ，可以这样求所有区间众数出现次数：扫描右端点 $r$ ，记 $s_l$ 为 $[l, r]$ 区间内众数出现次数，考虑每次让 $r$ 加一，扫描 $a[r+1]$ 之前出现的所有位置，能把区间划分成一些段，每段从右往左对 $a[r+1]$ 出现次数取 max，如果取不了就立刻 break。复杂度是 $n\sqrt n$ ，因为最终 $s$ 之和小于 $n\sqrt n$ ，并且 $s$ 单调不增，每次取 max 成功都会至少 +1。[ZJOI2022] 众数

dp

发现某个量很难刻画的时候可以在状态里面多加几维，实在不行全放上

转移顺序的问题不用特别担心，一般来说没问题

如果转移的复杂度很高其实可以考虑贪心的转移，比如什么对集合权值取 $\max$ 之类的就可以直接贪心选一段前缀

图论

带边权树的重心和无边权树重心相同（有无点权不影响），带边权树重心定义：让 $\sum_{u=1}^ndis(u, x)\times w(u)$ 最小的 $x$ 。[ZJOI2015] 幻想乡战略游戏

求带点权树的重心：先树剖，然后线段树维护区间内点的 $siz$ 的最大值，然后线段树二分，尽可能取靠右的点使得 $siz_x\times 2\ge all$ 。[ZJOI2015] 幻想乡战略游戏

DAG 容斥系数是 $(-1)^{|T-S|+1}$

数学

计数题如果出现了一些操作让你求最终得到的东西个数，一定要从最后得到的东西下手，不要从操作下手，因为会重复。或者强制规定一种唯一的构造方案。

记 $S(x)$ 为 $x$ 数位和，那么不存在 $n\ge 10, x$ 满足 $S(nx)=nS(x)$

一堆元素，选最少个或起来是全集的方案数。枚举最少次数，然后做这么多次 FWT 理解理解就可以了，最后答案要除以阶乘。

$\varphi(n)$ 不仅可以写成 $\sum_{d|n}\mu(d)\times \frac{n}{d}$ ，也能写成 $n\times \sum_{p\in \mathbb{P}}[p|n]\frac{p-1}{p}$ ，不要只在前面那种形式上卡死。

遇到数论题值域在 $3000$ 左右的时候要考虑根号分治了，小于 $\sqrt M$ 的部分可以状压，大于 $\sqrt M$ 的质因子一个数里面只会有一个，所以按照这个质因子排序就会形成一堆连续段，在段结尾单独计算大质数的贡献就可以。[CCPC 2024 重庆站] 乘积，欧拉函数，求和

如果值域很小并且有异或问题，可以考虑直接搜出来所有线性基的状态，大小为 $5$ 的线性基只有 374 个，完全可以存状态里面。

杂项

旋转偶数边长的矩阵不会改变逆序对数量，旋转奇数边长的矩阵不会改变每个数 $x+y$ 的奇偶性。