运用莫比乌斯反演，我们可以将一些函数转化，从而降低计算难度。在一些于 gcd 相关的算法问题中，莫比乌斯反演非常重要。 狄利克雷卷积 英文名为 Dirichlet 卷积，以下用符号 ∗*∗ 表示。 (f∗g)(n)=∑d∣nf(d)×g(nd)(f*g)(n)=\sum_{d|n}f(d)\times g(\frac{n}{d})(f∗g)(n)=∑d∣n​f(d)×g(dn​) 狄利克雷卷积单位元记做 e(n)=[n=1]e(n)=[n=1]e(n)=[n=1]，方括号中的等式成立则值为 111，否则为 000。 单位元的意义为：(f∗e)(n)=f(n)(f*e)(n)=f(n)(f∗e)...

单位根 有了幅角和模长，怎么具体的把这个复数写出来呢？三角函数是个很有用的公式，高中知识告诉我们 sinθsin\thetasinθ 表示当幅角为 θ\thetaθ， 模长为 111 时的 yyy 坐标，cosθcos\thetacosθ 表示 xxx 坐标。复平面中 xxx 和 yyy 分别表示 aaa 和 bbb 的值，所以我们就可以用三角函数将 nnn 次单位根表示出来，ωn1=cos360∘n+i×sin360∘n\omega_n^1=cos\frac{360^\circ}{n}+i\times sin\frac{360^\circ}{n}ωn1​=cosn360∘​+i×sinn36...

快速傅里叶变换 FFT，也就是 Fast Fourier Transform，是利用离散傅里叶变换（DFT）的高效、快速计算方法的算法统称。对于一个 OIer，FFT 最大的用处是用来加速多项式乘法。其本质是以 O(nlgn)O(nlgn)O(nlgn) 的时间复杂度将点值表示法与系数表示法相互转换。 这篇文章没有成堆的空洞乏味的公式推导，以简洁易懂的数形结合思想解释 FFT 算法。当然，没有严格的证明也是缺点之一。 多项式的表示 多项式的表示主要有两种，第一种是最常见的系数表示法。将每个项的系数写在一起组成一个向量，缺少的项就补 000，顺序最好按照次数的大小从小到大，因为这样可以与数组的下...

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

若有方程 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] 的最佳转移点（也就是那个让 f[j]+cost(j,i)f[j]+cost(j , i)f[j]+cost(j,i) 最小的 j）随 i 的增加单调递增，那么此方程就是决策单调的。这个方程本身的时间复杂度是 o(n2)o(n^2)o(n2)，我们可以利用决策单调性的特性优化到 o(nlgn)o(nlgn...

插头DP是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。本文以P5056【模板】插头dp为例进行分析。 一个格子有四个插头，上下左右，就像拼图凸出来和凹进去的地方。一个格子会选出两个插头，形成一条经过此格的路径。当两个左右在一起的格子，左边的格子选了右插头，右边的格子选了左插头，那么这两个格子就是联通的了。 压缩的状态表示的是一条轮廓线上方格子选择的插头的信息。这条轮廓线是已决策的格子与未决策的格子间形成的边界线，当前要转移的格子正好在这条边界线的弯折处。状态则描述的是这条轮廓线上方的格子的插头与轮廓线相交的信息，用三进制表示向下、向上和无。必须要记录向上和向下的方向信...

题意 可以对 nnn 条 010101 字符串进行任意排序，排好序后的代价为从前往后每次加入新 010101 串后多出 111 位置数的平方的累加。 解法 本体是经典的状态压缩，状态表示的是m块内存哪些已经访问过了。 用记忆化搜索实现非常方便。函数传递的参数为已经访问过几块内存了、n个位置中哪些位置已经访问过了、当然还有m块内存的状态（如开头所写）。虽然前两者可以通过最后一个计算得到，但是记录下来可以加快程序速度，并且大大减少代码量。 因为只要有最后一个参数我们就能确定一个唯一的状态了，所以记忆化搜索的数组只需要开一维来表示最后一个参数的映射即可。 我来挑战一波最短题解代码 code #inc...