博客园 我的博客 快速沃尔什变换解决的卷积问题 快速沃尔什变换（FWT）是解决这样一类卷积问题： \[c_i=\sum_{i=j\odotk}a_jb_k\] 其中，\(\odot\)是位运算的一种。举个例子，给定数列\(a,b\)，求： \[c_i=\sum_{j\oplusk=i}a_jb_k\] FWT的思想 看到FWT的名字，我们可以联想到之前学过的FFT（很可惜，我没有写过FFT的笔记，所以没有链接），先看看FFT的原理： 把\(a,b\)变换为\(A,B\)，\(O(n\logn)\)； 通过\(C_i=A_iB_i\)计算，\(O(n)\); 把\(C\)变...

目录 阅读本文你将会知道 线性规划简介 线性规划的标准形 一般型转标准型 <与≤ 线性规划的松弛形 标准型转松弛形 单纯形算法 基本可行解 如何判断最优 旋转操作 如何通过旋转更新解？ 退化与布兰德规则 基本不可行解 单纯形算法的几何意义 单纯形算法的时间复杂度分析 线性规划问题有更优的做法吗？ 对偶定理 全幺模矩阵 例题 「UOJ179」线性规划 「NOI2008」志愿者招募 「ABC231H」MinimumColoring 「SHOI2004」最小生成树 「CF1430G」YetAnotherDAGProblem 参考资料 阅读本文你将会知道 线性规...