【清华集训2014】玛里苟斯

【清华集训2014】玛里苟斯

线性基模板题 首先是个结论: 所有出现过的数出现的概率是相等的 很容易感性理解 然后,我们考虑k==1的情况 显然这比较简单,找到所有有1的位并起来直接求除以2就好了 然后...

Berlekamp-Massey学习

Berlekamp-Massey学习

刚刚学习了BM算法,用来求解一个数列所对应的最小次数递推式 它的复杂度是O(n^2)的 它的思路并不复杂 首先,我们有一个数列 接下来,我们要构造一个可以符合这个数列的递推式...

Fwt学习

Fwt学习

fwt主要是用来处理一类卷积问题的 首先说明一下集合幂级数 这就是一个用集合作为下标的函数 而fwt可以处理一类与集合幂级数相关的卷积问题 我们考虑\circ是一个关于集合的...

Lct学习

Lct学习

终于还是学习了一下lct(然而我还是不会证复杂度) 讲道理,这东西比想象的要来的简单 概述首先,这个东西是用来维护树的信息的 可以支持link和cut操作(所以叫做link-...

(CC 2018AugestLong)Interactive Matrix

(CC 2018AugestLong)Interactive Matrix

这真是一道神奇的乱搞题 首先限制说明,询问次数可以达到4n我们发现,每次询问四个顶点,当一边的两个值都大于V时,可以除去这一边如果这样走完整个矩阵,答案刚好4n但是这里就出现...

Min_25筛

Min_25筛

这个东西续了我好长时间,并且让我意识到状态真的不太对 Min_25筛这个东西,感觉对于不同题,思路上还是有些不同的,只是大致方向一致,所以也没有很多具体模板这种东西吧 大致思...

Stirling学习

Stirling学习

昨天学习了一发Stirling数哒哒哒,感觉很有用 首先,Stirling数哒哒哒分两类 第一类Stirling数\begin{bmatrix} n \\ k \end{bm...