前言 本文仅作为简单的离散傅里叶的简单推导 点值表示法 设 f(x)=∑aixif(x)=\sum a_ix^if(x)=∑ai​xi 如何快速计算卷积? 下面的证明写得不好, 只是简单写写… 考虑将这个多项式用点值表示 {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⋅ ...

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" ...

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 枚举 ...

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} [10​01​]⇒[vx​vy​​wx​wy​​] 行列式 计算空间积缩放比例 二维证明可以参考 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​+a1​x+a2​x2+⋯+an​xn=b0​+b1​x+b2​x2+⋯+bn​xn​ 首先我们要引入几个基本定理 系数表示 我们主要研究的是多项式的系数, 所以要引入系数表示法 显然易得, 我们可以直接拿系数来表示一个多项式: 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 为当前状态的取数次数 ...

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 ...