mygr main()

定义： 长度为 $2n$ 的合法括号序列数量 二维平面上只能向右或向上走，不经过直线 $y=x+1$ 的方案数 有递推式 $$C_n=\begin{cases}1& (n=0) \ \sum\limits_{i=0}^{n-1}C_iC_{n-i-1} &otherwise\ \end{cases}$$ 这个式子可以理解为在后方新增一个括号，形成类似 ...(...) 的结构 有通项公式 $$C_n=C_{2n}^{n}-C_{2n}^{n-1}$$ 可以用 [[反射容斥]] 来搞 进阶：卡特兰数的自卷积 设 $F$ 表示卡特兰数生成函数 那么根据上边的递推式有 $$\begin{eqnarray}F&=&1+xF^2\ F&=&\frac{1-\sqrt{1-4x}}{2x}\ \end{eqnarray}$$ 对于 $[x^n]F^m$ ，我们可以考虑他的组合意义：在 $m$ 个有序箱子中，存储 $m$ 个合法括号串，使得括号串的总左括号数为 $n$ 我们可以考虑他的组合意义，先构造一个大括号串 ((())) ，满足共有...

可用于求 [[卡特兰数]] 只能向右或向上，求不能经过两条直线到达某点的方案数 #under_construction

Trick 统计不同的子串数量，可以用每个后缀的长度减去每个 h[i] 求得 . LCP有两种求法，你知道嘛 SA/SAM 朴素求 前缀[[哈希]]+二分(可搭配主席树)

子串定位 当已知其为原字符串的一部分时，可以在建图的同时得出 $S[1;r]$ 在SAM上的对应节点，求 $S[l;r]$ 时就在 $S[1;r]$ 的基础上向上跳 $fail$ ，直到跳到长度对应为止，用倍增优化此过程 另外可以使用 [[DAG链剖分]] 求解

相关链接：[[线段树合并]] 常见于只有合并没有撤销的题目 Trick 树上启发式合并从下往上求解答案 # 人员调度 # 春节十二响 注：树上用启发式合并合并堆是 $O(nlogn)$ 的

伟大的Oi-eR zyb 曾言：“万物皆可哈希” 相关链接 [[字符串]]，[[集合]] 字符串哈希 可用来判断字符串相等，寻找LCP用于比较字符串等等操作 # 星战 - 异或哈希经典例题 # 字符串比较上树 集合哈希 万物皆可哈希，集合也不例外 # NOI2024 集合 利用数列转某种类型数出现次数的 Trick ，可以将有序序列转化为无序集合并哈希，当需要进行区间加操作时，不妨设哈希函数为 $M(A)=x^A$ ，那么区间加操作可以等效的视作区间乘 $x^v$ ，并继续使用上述方法维护集合 # same sum 数列哈希 不一定只有字符串才会用到哈希，具体要看这个数列是否需要满足字符串的某些形式(如字典序等) 例如 系统设计，可以将与字符串相类似的数列等价的视作字符串，用字符串的方法去解决

[[树上问题]]： [[欧拉回路]]： [[连通性相关]]： [[网络流]]： [[最短路]]： [[建图技巧]]： [[最小生成树]]： [[差分约束]]： Trick 对于两个位置只能选一个，选完后会产生不同贡献的问题，或者说两种决策选择一种，可以考虑转化为两点之间有一条边，变成 “给边定向” 的问题,然后分析图的性质或转化为 [[欧拉回路]] 问题给边定向

对于用堆+[[启发式合并]] 用于树从下往上查询的题目 # 人员调度 # 春节十二响

调和级数：$\sum_{i=1}^{n}\frac{n}{i}= nlogn$ 遇见倍数或者整除的问题时，若每个数唯一出现，考虑枚举倍数 $O(nlogn)$ 若每个数不唯一出现，考虑枚举因数 $O(nlog^2n)$ $\sum_{d \mid n}d=nloglogn$ 随机数列最长上升子序列的期望长度为 $O(\sqrt n)$ 好像只能计算机近似计算

普通多项式 当发现求解过程中出现了单单一个自变量的式子时，可以考虑将其拆分为一个多项式，然后在求解时在外部调用即可 # 传染病研究 生成函数 多项式科技