文章

//好吧标题是扯蛋的 本文全文 9624 个字（不包含这句声明），全都是 XZY 一个字一个字码出来的 QAQ 如果需要转载非常欢迎，但请注明出处：集合卷积——从 FMT 到 FWT —— MiNa! 谢谢！=￣ω￣= 1. 啥是集合卷积 先看看多项式乘法卷积： $C _ k = \sum _ {i 阅读更多…

抛出问题 题目来源：洛谷一位大佬的比赛的第一题。 题目大意：求下面式子的值： $$\sum^{B} _ {i=A}\sum^{i} _ {j=1}\left \lfloor \frac{i}{j} \right \rfloor \times \left ( -1\right )^j$$ 题目解答 比 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 OvO 翻前几天的代码发现了这个千年大坑 QwQ 咕咕咕了好几天了 做法还比较简单（然而我还是推了好久），可以说是多项式求逆开根模板了 OvO 首先不难想到，对 $C _ i$搞个生成函数 $P$ $P[C _ i]=1$ 设多项式 $F$，$F _ i$表 阅读更多…

Berlekamp Massey 算法 一些定义 $F,G$：这样的大写字母一般代表一个数列 $deg(f)$：数列 f 的长度，下标从 1 开始 功能 为一个序列，求一个非平凡的齐次线性递推方程。 解释 非平凡的齐次线性递推方程，即找到一种规律，使这个序列满足这个规律。同时这个规律必然是通过前 $ 阅读更多…

原问题 给定一个数列前 k 项，并给出其 k 阶递推关系 $h_n=\sum_{i=1}^k a_ih_{n-i}$，求 $h_n$。 矩阵快速幂 大家都会矩阵快速幂的方法。 构造一个转移矩阵 $A$ $$ A=\left[ \begin{matrix} a_1 & a_2 & a_3 阅读更多…

orz myy and ZZQ (其实在今天之前我从来没有听说过这玩意儿只是翻阅论文的时候有毛爷爷引进过一个没有中文资料的黑科技的印象) 其实也确实是一个黑科技…… 哪位神仙脑子一拍想出了这么神奇的算法…….(其实我更感兴趣怎么证明 QAQ) Berl 阅读更多…

首先我们有一些函数推收敛式的套路。比如对于 $y=1+x+x^2$ ，我们知道 $xy=x+x^2+x^3$，所以有 $xy-x^3=y-1$，即 $y=\frac{1-x^3}{1-x}$。用类似的方法，我们还可以知道 $\sum_{i=0}^{inf}=\frac{1}{1-x}$等。 然后我们 阅读更多…

一、左偏树是什么 左偏树的基础——堆 我们曾经学习过基础数据结构之一——堆（heap）堆支持三种操作（以小根堆为例）1、查询（query）：查询堆中最小的元素 2、删除（del）：删除堆中的任意一个元素 3、插入（insert）：插入一个新元素 4、维护（modify）：维护堆的性质：任何非叶子 阅读更多…

1. 题目 传送门=￣ω￣= 题意：给你一颗树，问你有多少条路径长度为素数。 点数 $\leq 50000$ 2. 题解 emmmm… 路径条数显然点分治 然后对于每个点 $p$弄个向量，向量的维度是 $p$的子树大小，向量的第 $i$维的值等于 $p$的子树中到 $p$的深度为 $i$ 阅读更多…