FLYlai

摘要： 若网格图面积为 \(S\)，取短边分治，令分治层的复杂度和短边相关（一般是从短边上每个点出发对整个网格图 DP/搜索 之类的）。 因为短边长度 \(O(\sqrt S)\)（一般）一层复杂度是 \(O(S\sqrt S)\)，总复杂度 \(T(S)=2T(S/2)+O(S\sqrt S)=O(S\s 阅读全文

摘要： 介绍一种升级版的 BSGS 科技，若在模 \(P=p_1^{e_1}\cdots p_k^{e_K}+1\) 意义下求离散对数，可以做到 \(O(\sum \sqrt{p_i^{e_i}})\) 以及 \(O(\sum e_i\sqrt {p_i})\) 的复杂度。 先看怎么做前者。 考虑怎么求出 阅读全文

摘要： 有时需要质因数分解，但是数据范围做不了质因数分解，但是实际上并不需要真正分解为质因数，可以用这种方法代替质因数分解。 例题：CF1656H【法二】 【题意】 给定两个集合 \(A,B\)，要求各选出一个子集使得它们的 LCM 相等。 \(|A|,|B|\le 1000,a_i,b_i\le 4\ti 阅读全文

摘要： 因为 \(det(A+xB)\) 和 \(det(A-\lambda I)\) 很像，所以可以考虑相互转化。 例：ABC323G。 【题意】 给定一个长度为 \(N\) 的排列 \(P=(P_1,P_2,\ldots,P_N)\)，其中 \(P\) 是 \(1\) 到 \(N\) 的一个排列。 请你 阅读全文

摘要： band-matrix（带状矩阵）是指只有两条对角线之间有值、其余全是 \(0\) 的矩阵。记两条对角线的距离为 \(d\)，这种矩阵高斯消元可以做到 \(O(nd^2)\)。普通的高斯消元是 \(O(n^3)\) 的。 优化的点在于有很多位置不需要消元：从 \((i,i)\) 向右、向下走，至多 阅读全文

摘要： DFS 序 DP：与合并子树的树形背包相对。 状态设计通常为 \(dp(i,S)\) 表示考虑了 dfs 序的前 \(i\) 个点，各种状态为 \(S\) 的某种属性。 优势：每次只新加入一个点。 劣势：要处理往回跳的情况（dfs 序增加 \(1\)，可能是切换子树了）。 常用优化技巧：重链剖分，在 阅读全文

摘要： 有的时候线段树还是太慢了（需要 \(\log\) 次合并得出答案）。使用猫树可以空间换时间：\(O(n\log n)\) 空间，\(O(1)\) 时间。但是猫树不支持修改。 应用条件：静态，卡时间死/合并复杂度很高。 【构建】 先建出一颗正常的线段树。同时对于 \([l,r]\)，我们预处理 \([ 阅读全文

摘要： 【前置知识】 泰勒展开。设 \(g\) 是一个光滑的函数，\(g(y)=\sum_{n\ge 0} \frac{g^{n}(y_0)}{n!}(y-y_0)^n\). 多项式 exp。 给定多项式 \(a(x)\) 满足 \(a_0=0\)，求 \(\exp a(x)\bmod x^n\)。 设 \ 阅读全文

摘要： 【定义】 对两多项式 \(f,g\)，无常数项且一次项系数非 \(0\)，有：\(f(g(x))=x\iff g(f(x))=x\)。（这个结论需要用到高深的群论知识，不会） 如果 \(f(g(x))=x\)，称 \(f,g\) 互为复合逆。记 \(f^{-1}\) 为 \(f\) 的复合逆。同时可 阅读全文