[后缀自动机+线段树合并]HydroH1079【‘Minami Kotori’ Pantw 和他的召唤物二元葡萄】题解
题目概述HydroH1079解题报告建出SAM，找到 $[A,B]$ 对应节点 $p$ ，然后在 $p$ 的 $Right$ 集合上考虑。$[C,D]$ 中出现 $[A,B]$ 的子串比较难算，...
[离线+线段树+堆]洛谷4747(CERC2017)【Intrinsic Interval】题解
题目概述Luogu4747解题报告找性质题过于困难……首先很明显，如果两个合法区间有重叠部分，那重叠部分一定也是合法的。更进一步，根据这个性质可以得知答案一定是唯一的，否则两个答案区间的重叠部分...
[离线+ODT+扫描线+线段树]2022 CCPC 广州 B【Ayano and sequences】题解
题目概述Ayano and sequences解题报告其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发现涉及到时间和区间两个维度，并不是很好...
[思维+后缀数组+调和级数]LOJ2083【「NOI2016」优秀的拆分】题解
题目概述LOJ2083解题报告想了很久匹配做法，不会做，实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$ 表示以 $i$ 开头的 $BB$ ...
[后缀自动机+线段树合并+后缀数组]LOJ2720【「NOI2018」你的名字】题解
题目概述LOJ2720解题报告毒瘤字符串题……这题的关键在于，给出串 $T$ ，在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。倒着考虑 $T$ 的每个后缀 $i$ ，求出在 ...
[NTT]Codeforces528D【Fuzzy Search】题解
题目概述CF528D解题报告奇怪的字符串匹配，并且字符集很小，考虑卷积。对于字符 $ch$ ，如果 $S$ 的 $i$ 位置是 $ch$ ，说明 $[i-K,i+K]$ 这些位置都可以匹配。令 ...
[离线+线段树套单调栈+线段树二分]2019 ICPC 香港 H【Hold the Line】题解
题目概述Hold the Line解题报告直接线段树套set是过不了的，我们需要一个小常数的做法。考虑离线，这样第 $i$ 次事件插入 $x$ 位置时，就可以认为是 $i$ 时刻 $x$ 才出现...
[多项式ln+多项式exp+分治NTT]LOJ2320【「清华集训 2017」生成树计数】题解
题目概述LOJ2320解题报告学到了好多多项式套路。如果 $i$ 连通块度数是 $d_i$ ，则每条边都有 $a_i$ 个选择，把 $a_i$ 放进答案式子里，答案式子就是：$$
\sum_T(...
[容斥+分治NTT]LOJ575【「LibreOJ NOI Round #2」不等关系】题解
题目概述LOJ575解题报告有个比较好想的想法是 $f_{i,j}$ 表示前 $i$ 末尾放第 $j$ 大的方案数，转移方程很显然是前缀和、后缀和的形式，但是前缀和后缀和是没有办法加速的，复杂度...
[分治NTT+倍增]2022 CCPC 桂林 D【Alice's Dolls】题解
题目概述Alice's Dolls解题报告定义 $f_{n,k}$ 表示要得到 $n$ 个物品，$x^k$ 的期望。$n>1$ 的情况十分复杂，但是根据期望的线性性，$n>1$ 的情...
