离散傅里叶
前言
本文仅作为简单的离散傅里叶的简单推导
点值表示法
设 f(x)=∑aixif(x)=\sum a_ix^if(x)=∑aixi
如何快速计算卷积?
下面的证明写得不好, 只是简单写写…
考虑将这个多项式用点值表示
{vi,f(vi)}\{v_i, f(v_i)\}
{vi,f(vi)}
只需要证明这种表示方法是 充分必要 的
感性证明: 多项式函数由 n−1n-1n−1 个方程即可 充分必要 地表示
我们带值其实就是列了 n−1n-1n−1 个系数方程, 最终可以求出 nnn 个系数
那么 {vi,f(vi)⋅g(vi)}\{v_i, f(v_i)\cdot g(v_i)\}{vi,f(vi)⋅g(vi)} 可以反推回 f∗gf\ast gf∗g 吗?
其实就是要证明 f(vi)⋅g(vi)=(f∗g)(vi)f(v_i)\cdot g(v_i)=(f\ast g)(v_i)f(vi)⋅g(vi)=(f∗g)(vi)
走到这一步其实就呼之欲出了, AB=CAB=CAB=C 这种结构的多项式计算, 分开来先算 AAA 和 BBB 或者是直接算 CCC 不只有顺序的 ...
初等数论
初等数论的魔力
初等数论以接近纯粹理性的思考(同时又可以与现实挂钩)使我深深沉醉
欧拉线性筛
这是普通筛法的改良版本, 可以保证筛且仅筛一次
设 a=Πpiqi,pi<pi+1a=\Pi p_i^{q_i}, p_i<p_{i+1}a=Πpiqi,pi<pi+1
核心就是遍历素数表的时候, 一旦搜索到 p0p_0p0 (最小的那个组成素数) 就退出
伪代码
for i in range(2,n):
if not_prime[i]:
primes.push(i)
for j in prime:
not_prime[i*j]=true
if i%j==0:
break
举例说明
我所想到的证明方法都太复杂(或者说属实是 abstract )所以不写出来了
let i=2⋅3⋅5i=2\cdot 3\cdot 5i=2⋅3⋅5
首先我们考虑搜索的顺序, 根据筛法, 不难得出 iii 的推导过程是 5⇒3⋅5⇒2⋅3⋅55\Rightarrow3\cdot 5\Rightarrow 2\cdot 3\cdot 55⇒3⋅ ...
zig debug
Preface
It’s likely to cpp.
configure
via launch.json
{
"version": "0.2.0",
"configurations": [
{
"name": "Launch",
"type": "cppdbg",
"request": "launch",
"program": "${workspaceFolder}/zig-out/bin/build",
"preLaunchTask": "build",
"cwd": "${workspaceFolder}"
}
]
}
via tasks.json
{
"version": "2.0.0",
"tasks": [
{
"label": "build",
"type": "shell",
"command": "zig build"
...
sudoku
Preface
使用了 dancing links 算法, 算法讲义请参考 dancing links
以下默认大家已经会 dancing links 了
Start up
其实 dancing links 最难就是数学建模了
首先我们列举出数独的规则
每一行有且只有一次 [1,9][1,9][1,9]
每一列有且只有一次 [1,9][1,9][1,9]
每一块(宫)有且只有一次 [1,9][1,9][1,9]
还有个隐藏规则
4. 不能有空位, 每一个位置都得有数(真是不显然的显然呢)
然后我们考虑将这些规则转化为一个枚举矩阵, 每一行代表一个状态(一个格子中的状态), 那么最终取 81 格子即可生成答案
类似于 dp 的 状态压缩, 我们将每个状态用一串 01 串表示, 1 则代表选择这个状态, 那么题目的规则就可以抽象为 r 行 c 列的 枚举矩阵, 最终答案就是找到 1 个有 81 行且满足精确覆盖的最终矩阵
我们用行来表示一个格子的状态, 则需要 O(9∗9∗9)=O(729)O(9*9*9)=O(729)O(9∗9∗9)=O(729) 的空间
解释: 因为是 01 枚举 ...
dancing links
Preface
dancing links 是一个简单而复杂的东西
简单: 思路很简单, 和最原始的暴力没什么区别
复杂:
十字指针以及写成代码后很难调试
遇到题目时, 数学建模较为复杂
参考: OI-wiki
Start up
Definition
dancing links 是用来解决精确覆盖问题的!
思路就是枚举每个元素, 同时删除冲突, 最终检查是否枚举了所有元素(删除冲突的操作已经保证了仅被枚举一次)
X算法
前置思路(X算法)不做过多说明, 具体请参阅 OI-wiki
Implementation
X算法中要大量删除行(恢复行), 删除列(恢复列)的操作, 不好直接处理
而且我们发现删除后, 问题规模在变小, 那么考虑 递归 求解(因为我们只需要一个解即可)
又因为是二维问题, 所以我们考虑十字指针(双向链表), 不难发现, 用下图这种存储方式是最优的!
而我们需要怎么维护这个双向链表呢?
在X算法中, 我们考虑每次选一行, 同时处理这一行与其他行/列的冲突
前置说明
相关变量的定义
class DancingLinks{
private:
st ...
线性代数笔记
Preface
线性代数是一个实用而方便的东西!
张成空间
v⃗,w⃗\vec{v}, \vec{w}v,w 通过线性组合可以覆盖的空间范围
线性变换
基于只有乘法和加法运算的群
简单来说, 就是 保持网格线平行且等距分布 的变换
矩阵乘法
代表着基向量的线性变换(也可以看成目标矩阵乘单位矩阵得到一个新的线性空间)
[1001]⇒[vxwxvywy]\begin{bmatrix}
1&0\\
0&1
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
v_x&w_x\\
v_y&w_y
\end{bmatrix}
[1001]⇒[vxvywxwy]
行列式
计算空间积缩放比例
二维证明可以参考 Matrix67 的 经典证明:向量叉积的几何意义
这里放出他和3b1b给出的证明图片(经典的无字证明)
行列式看似简单, 但是在后面的内容中有着很重要的作用
比如, 可以用来求逆矩阵
值得说明的是,
当行列式等于 000 的时候, 几何意义是 线性变换 使得空间的面积变换比例为 000, 那么就说明这个矩阵 ...
浅谈多项式算法
Preface
多项式算法可以延伸出很多重要的定理, 无论实在 OI 界 还是 数学 界 都有着十分重要的地位
Start up
设两个多项式
f(x)=a0+a1x+a2x2+⋯+anxng(x)=b0+b1x+b2x2+⋯+bnxn\begin{split}
f(x)&=a_0+a_1x+a_2x^2+\cdots+a_nx^n\\
g(x)&=b_0+b_1x+b_2x^2+\cdots+b_nx^n
\end{split}
f(x)g(x)=a0+a1x+a2x2+⋯+anxn=b0+b1x+b2x2+⋯+bnxn
首先我们要引入几个基本定理
系数表示
我们主要研究的是多项式的系数, 所以要引入系数表示法
显然易得, 我们可以直接拿系数来表示一个多项式: f(x)={a0,a1,a2,⋯ ,an}f(x)=\{a_0,a_1,a_2,\cdots,a_n\}f(x)={a0,a1,a2,⋯,an}
点值表示
那么能否转化为点值表示呢, 毕竟点值有很多优良性质可以用
我们用 n+1n+1n+1 个点 {x0,x1,⋯ ,xn}\{x_0 ...
矩阵取数
Preface
这是一道独特的 dp 题
Start up
读题其实还是可以联想到 区间dp 的(我一直没想到)
但是, 显而易见, 这和平常打的 区间dp 有点不同
分析题面可知, 他的状态转移是从边缘到中间的, 这点就和 平常的 区间dp 合并子区间 不一样
但毕竟还是区间问题, 除了 区间dp 好像也没有什么其他办法, 就只能从这里下手了…
那状态就很简单 dpl,rdp_{l,r}dpl,r
剩下就是如何转移的问题了
目前在 dpl,rdp_{l,r}dpl,r, 为了方便, 我们思考如何转移到这
并没有区间合并的操作
根据题意, 我可以从左边选一块, 也可以从右边选一块, 取最大值即可
如此这般, 方程就出来了 dpl,r=max{dpl−1,r+al−1⋅2t,dpl,r+1+ar+1⋅2t}dp_{l,r}=\max \{dp_{l-1,r}+a_{l-1}\cdot 2^t, dp_{l,r+1}+a_{r+1}\cdot 2^t\}dpl,r=max{dpl−1,r+al−1⋅2t,dpl,r+1+ar+1⋅2t}
此时, ttt 为当前状态的取数次数 ...
butterfly
Preface
API 文档上有的, 这里不一定有
API 文档上没有的, 这里也不一定有
Copyright
多作者?
./layout/includes/post/post-copyright.pug
./layout/includes/post/post-copyright.pugif theme.post_copyright.enable && page.copyright !== false
- let author = page.copyright_author || config.author
- let authorHref = page.copyright_author_href || theme.post_copyright.author_href || config.url
- let url = page.copyright_url || page.permalink
- let info = page.copyright_info || _p('post.copyright.copyright_content', theme. ...
组合数学初步
Preface
组合数学真是有趣
排列数
单看一个元素, 他可以排在任意 nnn 个位置上
第二个元素: 排在除第一个之外的 n−1n-1n−1 个位置
如此这般
Ann=n!A_n^n=n!
Ann=n!
任取 kkk 个元素: 那就是减去其余 n−kn-kn−k 个元素的全排列
在此, 我们算出全部的排列, 除去蓝色的重复的情况, 剩下的就是红色的了
■■■■■\textcolor{red}{\blacksquare\blacksquare}\textcolor{blue}{\blacksquare\blacksquare\blacksquare}■■■■■
Ank=n!(n−k)!A_n^k=\frac{n!}{(n-k)!}
Ank=(n−k)!n!
组合数
同理
■■■■■\textcolor{red}{\blacksquare\blacksquare}\textcolor{blue}{\blacksquare\blacksquare\blacksquare}■■■■■
我们把蓝色减掉之后还不够, 红色部分重复了, 那就再把红色部分除一下, 把多余的合并为一个即可
(n ...