mygr main()

[[Kmp]]： [[Trie]]： [[AC自动机]]： [[后缀数组]]： [[后缀自动机]]： [[哈希]]：

相关链接：[[组合数学]]，[[卢卡斯定理]] 考虑这个式子： $$\begin{eqnarray}&& C_{n}^{m} \pmod{2}\ &=&C_{\lfloor \frac{n}{2} \rfloor}^{\lfloor \frac{m}{2} \rfloor} \cdot C_{n \mod 2}^{m \mod 2} \pmod{2}\ \end{eqnarray} $$ 发现这个下取整可以无限递归下去，直至 $n,m$ 皆为 $0$ 发现当 $m$ 存在一位二进制位使得 $m$ 为 $1$ 且 $n$ 不为 $1$ 时，则此时的组合数为 $0$ 也就意味着整个 $C_{n}^{m} \pmod{2}$ 都为 $0$ 所以就能得到等式 $$C_{n}^{m} \pmod{2}= [m &n=m]$$ 或者说 $$C_{n}^{m} \pmod{2}= [m \subseteq n]$$ 当遇到方案数对 $2$ 取模的问题时，考虑能不能构造双射使得其去除掉某些计算过程，或将不满足条件的方案剔除 对于方案数对 $2$...

不常考的算法，但得会 本质是通过最短路的思路求解出一个 $n$ 元一次方程组的解 # 矩阵游戏 # 糖果 Trick 当差分约束中所有边都为等价关系时，设所有关系皆为 $x_i+y_i=c_i$，$x,y$ 内部之间没有连边，问 $\sum \mid x_i\mid +\mid y_i\mid$ 的最小值 考虑将这个图画出来，得到一个图，因为内部之间都没有连边，所以最后面一定能够构造出来一个二分图 成为一个二分图，也就意味着当我们对其求解得到一个生成树后，深度为奇数的点一定向偶数点连边，假设有这么一个环 ![[Pasted image 20250122221308.png]] 其中 c4 为非树边，那么我们发现就有等式 $$\begin{eqnarray}x_1+y_1 &=& c_1 \ x_2+y_1 &=& c_2 \ x_2+y_2 &=& c_3 \ \end{eqnarray} \Rightarrow x_1+y_2=c_1+c_3-c_2=c_4$$ 所以我们发现，这个 $c_4$...

[[函数复合问题]]：

序列分段问题 形式：一个序列分成多段，每一段按照一定方式计算权值，使总权值取最值。 基本方法：使用 $f_i$ 表示到 $i$ 的最值，根据题目加入其他维度，从 $f_{i-1}$ 或 $f_j$ 转移（$f_{i-1}\to f_i$ 即决策 $i$ 是否为断点，$f_j\to f_i$ 即决策断点为 $j$），经典形式如 $f_i=\max f_j+c(j+1,i)$。 根据两个区间之间的关系，有时需要决策本区间左端点，有时需要决策上一个区间右端点，有时二者皆可。 技巧：当每一段贡献同时与左右两端位置都有关，不妨直接在设置 $f_i$ 时令 $i$ 为区间右端点，这样枚举 $f_j$ 转移时就可以轻松计算。 P3628：最经典形式，设 $f_i$ 表示考虑到 $i$ 的最大权值，则 $f_i=\max_{j=1}^{i-1}f_j+a(s_i-s_j)^2+b(s_i-s_j)+c$，其中 $s$ 为 $x$ 的前缀和。 P3195：同样的最经典形式，状态同上，$f_i=\min_{j=1}^{i-1}f_j+(i-j-1+s_i-s_j-L)^2$，其中 $s$ 为...

对于区间加边，考虑线段树优化建图 如果建图中只有前缀加边，可以考虑不使用线段树优化建图而使用前缀优化建图

相关链接：[[二进制]]，[[线性基]] 用于判断元素个数是否为偶数 随机权值+异或判断是否为 $0$ 即可 # 星战 - 异或哈希经典例题 区间找两个数异或的最大值有三种求法，你知道吗？ 主席树上二分 可持久化trie树上寻找 找每个数所拥有的 $O(logn)$ 个支配数，具体看 [[二进制]] 的 Trick 对于一个数 $v$ 构造序列 $a_i=v \oplus i$ ，那么 $a_i$ 的区间 $[1,n]$ 能够被分解为 $logn$ 段等差数列

[[扫描线模型.pptx]] 本质是通过离线将某些询问的 side(自由度) 缩减一维 区间判断是否可重排为 $k=1$ 的等差数列有三种方法，你知道吗？ 若并不保证为一个排列，则可以取平方+哈希计算等方数列 大母神 若保证为一个排列，则可以 $max-min=r-l$ 计算 若保证为一个排列，则可以计算其与数轴上相邻两项重合的部分，区间加重合部分表示相邻段的个数，根据鸽巢原理可得联通块数量，为 0 则连续 常见的搭配有: 对一区间的所有子区间查询，转化为上三角矩阵查询，搭配历史线段树解决，例 区间操作+单点查询，换维进行扫描线，书虫 [[函数复合问题]]，搭配平衡树 最值分治转化为多个矩形的求和，例 判断为空/与0取max可以考虑根据上一次被清空位置分段 美食家

当 $n$ 很小却以幂次或阶乘的形式存在时，可以考虑折半双向搜索

配合dp 一般而言，先将dp式子列出，后面再考虑拉格朗日插值优化 训练时不要刻意的往拉差方面去想，或者结束后去想“为什么要使用拉格朗日插值！” # 机器人 # 填数 # Sum of k-th powers