线性递推小结

问题

给定$n,k,f_0\dots f_{k-1},a_1\dots a_{k}$,定义$f_n=\sum_{i=1}^k f_{n-i}a_i$,求$f_n$。

子集卷积

子集卷积是这样的问题:

$$f_S=\sum_{T\subset S} g_Th_{S-T}$$

给定$g,h$求$f$。

上午模拟赛考了这个trick,然后我不会,学会了来写一波博客。

考虑一类求最短区间的问题,满足单调性(可以two-pointers),插入很快,但是删除很慢,不过可以快速的判断两段的信息合并能否满足条件。

这时普通的尺取法就没法用了。

怎么解决呢?

斜率优化dp复习

发现自己几乎忘记斜率优化怎么写了,就来复习了一下。

参考了hihoCoder上的内容..题目也都是hihoCoder的。

FFT NTT小结

一个问题

给定$a_i,b_i$,定义$c_n=\sum_{i=0}^n a_ib_{n-i}$,求$c$序列。

还没写完…..

拉格朗日插值法是干啥的

用来合理的解释你按规律填数乱填的答案

给定n个点$(x_i,y_i)$,求一个n-1次多项式经过这n个点。

多项式小结

未完待续……

Orz great_influence

树套树每套一层就多一个log,但是多项式可以倍增随便套都可以分析得$O(n\log n)$,瑟瑟发抖

次小生成树问题

次小生成树是这样的一个问题:给定一个图,求它生成树中第二小的。

其中生成树的大小为生成树中边权之和。

这个问题有非严格次小和严格次小两种。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×