[思维+后缀数组+调和级数]LOJ2083【「NOI2016」优秀的拆分】题解
题目概述LOJ2083解题报告想了很久匹配做法，不会做，实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$ 表示以 $i$ 开头的 $BB$ ...
[后缀自动机+线段树合并+后缀数组]LOJ2720【「NOI2018」你的名字】题解
题目概述LOJ2720解题报告毒瘤字符串题……这题的关键在于，给出串 $T$ ，在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。倒着考虑 $T$ 的每个后缀 $i$ ，求出在 ...
[多项式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$ 大的方案数，转移方程很显然是前缀和、后缀和的形式，但是前缀和后缀和是没有办法加速的，复杂度...
[单位根反演+Bluestein套路]LOJ3058【「HNOI2019」白兔之舞】题解
题目概述LOJ3058解题报告这个 $m\bmod k=t$ 以及 $k$ 是 $MOD-1$ 因子显然是单位根反演，所以考虑用生成函数表示答案。令转移矩阵为 $M$ ，定义 $F_i(x)$ ...
[容斥+分治NTT]LOJ2541【「PKUWC2018」猎人杀】题解
题目概述LOJ2541解题报告可以把题目转化为，有一个外人向 $n$ 个人开枪，打到第 $i$ 个人的概率是 $w_i\over \sum w$ ，并且可以对死人开枪（但没有效果），问最后才打死...
[链分治+分治NTT]LOJ6289【花朵】题解
题目概述LOJ6289解题报告这题显然是一个树形背包 $f_{x,j,0},f_{x,j,1}$ 表示 $x$ 没选 / 选了，子树里选了 $j$ 个的方案数。这个背包可以写成多项式形式，$B_...
[后缀自动机+拓扑]LOJ3049【「十二省联考 2019」字符串问题】题解
题目概述LOJ3049解题报告把串反过来，那么 $B$ 是 $A$ 前缀就变成 $B$ 是 $A$ 后缀，也就是 $B$ 是 $A$ 在SAM上的parent树祖先，或者B和A在SAM同一个节点...
[DP套DP+期望]LOJ3042(ZJOI2019)【麻将】题解
题目概述解题报告考试的时候看到这种题只能想不到+打不出来……一道SB剪枝我没加然后就只有暴力分 $20$ 了……一副牌怎么样能胡？1.选出一种牌当对子，剩下的牌求出最大的面子 $\ge 4$ 。...
[线段树]LOJ3043(ZJOI2019)【线段树】题解
解题报告ZJOI又双叒叕出线段树，我又双叒叕没做出来。Orz%%%zhouzhendong。定义 $f_{i,0}$ 表示线段树节点 $i$ 没有标记，但是祖先有标记的概率，$f_{i,1}...
