【专题】多项式 发表于 2021-12-17 更新于 2022-01-25 分类于 专题 【专题】多项式主要为$FFT$，$NTT$，多项式求逆等变换，可以和生成函数结合起来考计数题。这篇题解中有对多项式乘法的较详细证明过程。 对于使用生成函数判断方案是否合法（而不是统计方案的数量），使用单模数容易被卡，建议在$998244353$，$1004535809$和$469762049$中选取两个，其原根都为$3$。 若题目中要求对奇怪的数取模，一定记得计算模数的原根，有可能不是$3$！ 阅读全文 »
【专题】虚树 发表于 2021-12-17 更新于 2022-05-16 分类于 专题 【专题】虚树这种东西想到要用很容易，关键是建完虚树后怎么做。 虚树题的特征为多次询问且出现$\sum M \le 10^5$一类的数据范围。 如果题目给出的是一张图而不是一棵树，可以思考是否能够结合圆方树等算法转化为虚树。 对于每次询问，将询问的节点和其在原树上的$LCA$单独建出来$dp$即可。 阅读全文 »
【专题】网络流 发表于 2021-12-17 更新于 2022-03-23 分类于 专题 【专题】网络流网络流的话，先口糊好怎么建图，然后复制默写一下板子就好了。 难点其实有两个，一个是如何建图，另一个是输出路径。 如果一道题有许多奇怪的限制，并且$n$和$m$很小，导致$O(n^2m)$可以通过，就可以往网络流方面去想。 其实网络流24题的全称叫网络流和线性规划24题？ 阅读全文 »
【专题】后缀数组 SA 发表于 2021-12-17 更新于 2022-02-05 分类于 专题 【专题】后缀数组 SA警告：SA多次使用一定要清空，我也不知道为什么。 虽然有不少此类题目可以用字符串hash瞎搞 记住代码中每个数组的含义： 数组 含义 $sa_i$ 排名为$i$的后缀的起始位置 $rk_i$ 后缀$s_{i \cdots n}$的排名 $tp_i$ 临时数组，用来在基数排序中记录临时排名 $ht_i$ 第$rki$个后缀和第$rk{i-1}$个后缀的$LCP$ 阅读全文 »