RainAir

学习笔记

题解(9)

/ 注册

全部文章 / 学习笔记（共12篇）

FFT 学习笔记

快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种的时间复杂度内完成离散傅里叶变换 (DFT) 的算法，OI 中通常用来优化多项式乘法。常见题目类型链接：给定一个次多项式和一个次多项式。求出它们的卷积。 FFT 就可以在的时间复杂度内解决该类...

FFT

2020-02-28

2 1059

多项式相关简单入门

多项式算法学习笔记定义形如的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项，定义多项式的次数为项的最高次数。显然个点可以唯一确定一个次数为的多项式。接下来我们首先来看一下多项式的基本运算怎么实现（要不然谁用啊）多项式加减直接对齐相同次数然后系数直接加减就可以了吧。。。...

多项式

2020-02-28

1 791

KDTree 学习笔记

K-D Tree，全名k-dimensional Tree，是一种分割k维数据空间的数据结构。主要应用于***空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D Tree是二进制空间分割树的特殊的情况，以下是一棵二维空间上的 k-d tree：建树 K-D Tree 的建树过程类似于平衡树：对...

KD-Tree

2020-02-28

0 1104

斐波那契数列初探

定义一些小性质一些 simple 的运算运算 1 证明：拆开算就可以了运算2 证明：数学归纳法一下就可以了。咕咕咕~ 运算3 我们如果把斐波那契数列扩展到负数，那么有公式运算4 证明：首先验证小范围的 k 发现是正确的。那么我们设是正确的，现在尝试证明是正确的。一些正常...

斐波那契数列

2020-02-28

0 796

一种最小割建模方法

网络流题目中，如果一种物品有两种状态（选或不选），告诉你每一种状态产生的收益/代价，我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了种，我们就需要用一种新的建图方法。我们拿两道题目举例： RatingProgressAward *TCO2017 Semifinal题目链接如...

最小割

2020-02-28

0 909

轮廓线 dp 学习笔记

轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。我们来从一道经典例题入手：求的骨牌填满的矩形的方案数。如果那么当然可以轻松状压了，但是如果，我们就要考虑使用轮廓线 dp 了。设表示我们填到第行，我们在状压的状态中记录下图红线上的格子的状态。（圆圈为现在要...

轮廓线dp

2020-02-28

0 2033

2-SAT 学习笔记

定义 SAT 维基百科——Boolean_satisfiability_problem 2-SAT SAT 的简化版本：每个等式中只有两个变量参与。有个变量和个等式，每个等式形如，其中是一个位运算。你要求出一组可行解。求解将每个拆成两个点和表示取值情况。每个限制...

2-SAT

2020-02-28

0 847

SAM 学习笔记

作为菜鸡 OIer，本文尽量用通俗的语言去讲解后缀自动机。当然学习后缀自动机前是有一点点前置知识的，我一块给说了。有限状态自动机（DFA）定义确定优先状态自动机是由：一个非空有限的状态集合一个输入字母表（非空有限的字符集合）一个转移函数（例如：）一个开始状态一个接受状态的...

后缀自动机

2020-02-28

0 759

DDP 学习笔记

DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。NOIP2018 Day2T3 - 保卫王国考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。我们来找一道简...

动态DP

2019-07-19

0 670

数论公式

记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑整除与不定方程证明：存在整数解。证明：从右往左推：令 ,则有从左往右推：考虑构造，这样就可以构造出所有的解了。令,证明现在我们尝试解显然 ,考虑设。如果有解即可。递归出口是 ,显然有解。现...

数论

2019-07-19

0 683