第二类斯特林数学习笔记 置顶 | Posted on 2019-03-07 | In 学习笔记 第二类斯特林数定义第二类斯特林数S(n,m)定义为把n个球放入m个盒子中,所有盒子均不为空的方案数,其中球不带标号,而盒子是带标号的。 递推求法根据定义,就能得到第二类斯特林数的递推求法,只需要枚举最后一个球放在哪个集合里即可。 S(n,m)=S(n−1,m−1)+m∗S(n−1,m) Read more »
prufer序列学习笔记 置顶 | Posted on 2019-02-22 | In 学习笔记 简介prufer序列,是讲一棵树唯一转化为一个序列,在解决无根树的计数问题时十分有用。 Read more »
拉格朗日插值学习笔记 置顶 | Posted on 2019-01-25 | Edited on 2019-02-27 | In 学习笔记 前言我们都知道两点确定一条直线,三个点确定一个二次函数,现在给你n个点,让你求出一个n−1次函数怎么做。 Read more »
Min-25筛学习笔记 置顶 | Posted on 2019-01-16 | Edited on 2019-01-21 | In 学习笔记 前言在yx大佬不厌其烦的帮助下终于还是学会了Min-25筛。其实不算特别难理解,主要是原先没人给讲解自己瞎走了许多弯路,代码实现也相对容易,听说可以代替杜教筛来求积性函数前缀和,名字好奇怪啊,不知道怎么来的复杂度O(n34logn)求单点时略优于杜教筛。update: Min-25是一位日本选手,精通数论,目前SPOJ rank10 orz,感谢daniel14311531 Read more »
二项式反演学习笔记 置顶 | Posted on 2019-01-06 | Edited on 2019-01-16 | In 学习笔记 二项式反演如果我们现在有一个式子fn=n∑i=0(ni)gi告诉我们所有的f,让我们求g这时候就要用到二项式反演了。 Read more »
Min-Max容斥学习笔记 置顶 | Posted on 2019-01-05 | Edited on 2019-01-25 | In 学习笔记 前言PKUWC2018的D2T3好像是个Min-Max容斥板子题,还是要学习一下的。 用途给定一个集合S,告诉你其中每个元素单位时间出现的概率,问你每个元素至少出现一次的期望时间。 Read more »
动态DP及全局平衡二叉树学习笔记 置顶 | Posted on 2019-01-04 | Edited on 2019-01-16 | In 学习笔记 前言受到NOIP的影响,大家都开始学习动态dp,博主比较菜,学的比较晚,以下的学习笔记主要是配合例题和代码讲解。 例题例题一 【模板】动态dpLuogu P4719【模板】动态dp 题目大意给定一个n个点的树,每个点有点权a[i]。有m次修改操作,每次操作给定x,y表示将a[x]修改为y你需要每次修改后找出若干个点,使得这些点互不相邻,并且点权和最大。n,m≤1e5 Read more »