retep

笔记

题解(2)

/ 注册

全部文章 / 笔记（共6篇）

莫比乌斯反演

运用莫比乌斯反演，我们可以将一些函数转化，从而降低计算难度。在一些于 gcd 相关的算法问题中，莫比乌斯反演非常重要。狄利克雷卷积英文名为 Dirichlet 卷积，以下用符号 ∗*∗ 表示。 (f∗g)(n)=∑d∣nf(d)×g(nd)(f*g)(n)=\sum_{d|n}f(d)\time...

数论

2022-06-28

0 265

快速傅里叶变换（后）

单位根有了幅角和模长，怎么具体的把这个复数写出来呢？三角函数是个很有用的公式，高中知识告诉我们 sinθsin\thetasinθ 表示当幅角为 θ\thetaθ，模长为 111 时的 yyy 坐标，cosθcos\thetacosθ 表示 xxx 坐标。复平面中 xxx 和 yyy 分别表示 ...

C++ 快速傅里叶变换

2022-06-17

0 434

快速傅里叶变换（前）

快速傅里叶变换 FFT，也就是 Fast Fourier Transform，是利用离散傅里叶变换（DFT）的高效、快速计算方法的算法统称。对于一个 OIer，FFT 最大的用处是用来加速多项式乘法。其本质是以 O(nlgn)O(nlgn)O(nlgn) 的时间复杂度将点值表示法与系数表示法相互转换...

C++ 快速傅里叶变换

2022-06-17

0 298

分配问题——线性规划模型

题目简述 nnn 个人分配给 mmm 个工作岗位 (n⩾m)(n \geqslant m)(n⩾m)，每个岗位 111 个人。已知第每个人在每个岗位上的效率，求最佳分配方案使得所有人的效率总和最大。设立变量设立变量 xi,jx_{i,j}xi,j，1⩽i⩽n1\leqslant i \leqs...

2022-05-28

0 593

二分队列，用于优化决策单调性动态规划的方法之一

若有方程 f[i]=min{f[j]+cost(j,i)∣j<i}f[i]=min\left\{f[j]+cost(j , i) | j<i\right\}f[i]=min{f[j]+cost(j,i)∣j<i}，这种方程一般是经典的切割问题，如果 f[i]f[i]f[i] 的最...

动态规划队列

2022-05-12

0 432

插头dp学习笔记

插头DP是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。本文以P5056【模板】插头dp为例进行分析。一个格子有四个插头，上下左右，就像拼图凸出来和凹进去的地方。一个格子会选出两个插头，形成一条经过此格的路径。当两个左右在一起的格子，左边的格子选了右插头，右边的格子选了左插...

动态规划状态压缩

2022-05-12

0 501