lnw143

摘要： here 主要是需要换根统计某些信息的时候，有时候节点之间本质不同在于根的不同子树，于是考虑对不同子树染色后统计信息，这个算法提供了 \(O(n \log n)\) 次修改点颜色以使得每个节点都有一刻把不同子树染成不同颜色，同一子树染成同一颜色，方便维护某些信息。 主要思想是保留重儿子颜色，将轻儿子 阅读全文

摘要： 参考 设全集 \(U=\{1 \cdots n\}\)，规定集合幂级数 \(f : 2 ^ U \to R\) 为从 \(U\) 的子集到 \(R\) 上的映射，其中 \(R\) 为交换环。 \(f_S \in R\) 是 \(S\) 映射到的值。 规定集合幂级数的并卷积，交卷积，对称差卷积，子集卷 阅读全文

摘要： 之前总结的时候写了一堆引理导致写的时候想不起来要干啥了，遂重新写一篇总结。 主要思想是逆用一下费马小定理，\(\forall x \in [1,p), x^{p-1} \equiv 1 \pmod p\)。 一个 naive 的想法是随机 \(x\)，直到 \(\text{gcd}(x,p) \gt 阅读全文

该文被密码保护。 阅读全文

摘要： 主要理解全局平衡的思想就好了，代码其实并不难，调了比较久 P4211 是因为细节没写好以及没有正确处理标记，要注意。 虚实边的处理方式类似 LCT，感觉静态 LCT 名副其实。 阅读全文

摘要： 大概是处理这样一个问题： 给定 \(n\) 个长为 \(m\) 的序列 \(a_1,a_2,\cdots,a_n\)，询问一个点 \(x\) 在所有序列中的前驱 / 后继，要求单次 \(O(n + \log m)\)，预处理 \(O(nm)\)，空间 \(O(nm)\)。 预处理 \(b\)，\(b 阅读全文

摘要： 常见形式为从 \((0,0)\) 出发可以向右上和右下走，求走到 \((n,m)\) 且不碰到 \(y=a\) 与 \(y=b\) （\(a \lt 0 \lt b\)）的方案。 记事件 \(A\) 为触碰到 \(y=a\)，\(B\) 同理，那么大概就是要把一个触碰事件非空的给容斥掉。 考虑记形如 阅读全文

摘要： 总结 FFT ＆ NTT 阅读全文

摘要： 设点 \(A(x,y)\) 绕原点 \(O(0,0)\) 逆时针旋转 \(\beta\)，则设在极坐标系下 \(A\) 的坐标为 \((r,\alpha)\) 这意味着 \(x=r \cos \alpha, y=r \sin \alpha\) 目标点 \(A'(x',y')\) 的极坐标即为 \(( 阅读全文

摘要： 图 \[\begin{aligned} \cos(α+β) &= OB \\ & = OD - BD \\ & = OD - EC \\ & = OC \cos \beta - AC \sin \beta \\ & = OA \cos \alpha \cos \beta - OA \sin \alp 阅读全文