冷滟泽的个人博客

2020-01-07 lengyanze 阅读(39) 评论(0)

冬令营的时候完全不会生成函数，听这块的时候全程掉线。。现在洛谷有了这两个模板，于是来总结一下自己的理解。 参考资料：WC2019 课件《生成函数，多项式算法与图的计数》 本文中图的计数均指有标号图的计数。 前置知识 ...

2019-11-23 lengyanze 阅读(39) 评论(0)

约定和记号 S1+S2 表示字符串 S1 和字符串 S2 顺次拼接得到的字符串 S[L,R] 表示字符串 S 下标从 L 到 R 的字串 字符串哈希 Hash 是一种常用的字符串算法，可以不需要逐位比较判断两个...

2019-11-20 lengyanze 阅读(92) 评论(0)

前言 本文总结了一些与 OI 有关的简单数论内容。 由于作者水平有限，部分结论的证明过程省略。 一. 公约数/扩展欧几里得算法 这里将正整数 a,b 的最大公约数记作 gcd(a,b) . 根据欧几里得算法，有 gc...

2019-11-15 lengyanze 阅读(49) 评论(0)

设 DP 方程为 f(i,j)=\min f(i,k)+f(k+1,j)+w(i,j) 并满足四边形不等式，状态 f(i,j) 的最优决策点为 s(i,j). 证明：s(i,j-1)\leq s(i,j)\leq s...

2019-01-22 lengyanze 阅读(53) 评论(0)

[树套树学习笔记]() 一、线段树/树状数组套平衡树 既然是“线段树套平衡树” ，就先建一颗线段树： 它的每个结点都是一颗平衡树，这颗平衡树就维护该节点所表示的区间： 但是线段树的每个结点都套一颗平衡树，空间会不...