zhangxixi的博客

根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于 每种 数的计数问题 考虑对每种数的出现次数进行根号分治 如果出现次数很少，直接平方暴力即可 如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式

范德蒙德卷积选数相同的合并 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132863313 对于 ： ∑i(ni)(mi)\sum_{i}\binom{n}{i}\binom{m}{i} i∑​(in​)(im​) 可以通过下面方法变形： ∑i(ni)(mm−i)=(n+mm)=(n+mn)\sum_{i}\binom{n}{i}\binom{m}{m-i}\\=\binom{n+m}{m}=\binom{n+m}{n} i∑​(in​)(m−im​)=(...

善于运用期望可加性+维护增量+DAG上dp：0912T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132857701 CP0912T4 首先看到无环，也就是DAG，显然拓扑 然后看到题目求类似期望和砍边的东西，就要考虑dp 然后有两个Trick 期望具有可加性 对于只有一次的操作，考虑增量 好了，现在我们考虑增量，假设已经知道不操作的答案，现在求恰好操作一次的增量 然后可以手玩一下，发现哪些边对哪些点会有哪些影响。 然后加起来就行了 ...

二进制、数位dp：0912T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132840291 考虑题目转化，二进制下满足 i⊆j,(i+x)⊆(j+y)i\subseteq j,(i+x)\subseteq (j+y)i⊆j,(i+x)⊆(j+y) 这显然是个数位dp形式 考虑枚举每一位与进位， dpk,p1,p2dp_{k,p_1,p_2}dpk,p1​,p2​​ 表示第 k−1k-1k−1 位向第 kkk 位，分别进位 p1,p2p_1,p_2p1​...

判定转状态+序列问题上树形dp：0909T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132796834 考虑没有括号怎么做。 对于这类+*表达式求值问题，正常思考的dp是状态 O(n)O(n)O(n) ，总共为 O(n2)O(n^2)O(n2) 的 但其实可以对于每个dp记录两个值，分别为答案dp，和后面的乘积和g 如果接乘号，就是 [j](dp,g)→[j](dp+g(i−1),gi)[j](dp,g)\to[j](dp+g(i-1),gi)[j]...

生成树、Prufer序列的计数问题：0912T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132839073 看到生成树计数，很容易想到生成树计数 然后发现每个点有度数限制，我们可以先考虑枚举每个点的度数（也可以是Prufer 序列中的出现次数） 假设出现次数为 aaa ，可以得出其生成树方案为 n!∏(ai−1)!\frac{n!}{\prod {(a_i-1)!}}∏(ai​−1)!n!​ 然后后面是个组合数的形式，然后需要推一堆式子 巧拆阶乘...

Cayley 公式 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132832172 nnn 个点的完全图生成树个数为 nn−2n^{n-2}nn−2 如何理解 一个生成树和其prufer序列是唯一对应的 所有生成树和所有Prufer序列形成一个双射关系 而Prufer序列长度为 n−2n-2n−2 ，值域为 nnn ，所以方案为 nn−2n^{n-2}nn−2

Prüfer / Prufer 序列 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132090250 ​ 快速跳转 P6086 【模板】Prüfer 序列 OI-wiki 结论：一个完全图的生成树个数为 nn−2n^{n-2}nn−2 注意，生成树是指无根树 构造过程 从小到大枚举叶子节点（指度数为1的点），记录其父亲。 最终为｛2，2，3，3，2｝ 考虑树如何线性建。 12345678910111213141516void sol1() ...

AC自动机小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818609 AC自动机是一种多模匹配算法。 常见操作 查询一个串的子串 任何一个串的子串都可以表示成他的一个前缀的后缀 他的前缀可以在Trie树上查询 后缀相当于其在fail树上的所有祖先 例1 ： HDU4117 接上。首先AC自动机要学会离线。 对于每个点查询祖先复杂度很大。但其实可以每个祖先计算其对子树的贡献。 而这个过程可以对fail树的dfn序建线段树维护 例2 ：HDU4787...

Kruskal重构树+AC自动机+树状数组：Gym - 104542F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818179 https://vjudge.net/contest/579844#problem/F 看到连边和没有强制在线，考虑Kruskal重构树 看到判断子串，考虑AC自动机+线段树 然后要非常大胆地把两个结合起来。 然后就是大码量了。 具体总结一下流程： 先建出Kruskal重构树 对Kruskal重构树处理...