数论——中国剩余定理、扩展中国剩余定理 中国剩余定理 定义 中国剩余定理（ChineseRemainderTheorem，CRT） 求解如下形式的一元线性同余方程组（其中\(m\)两两互质）： $\left\{\begin{matrix}x\equiva_1\pmod{m_1}\\x\equiva_2\pmod{m_2}\\\dots\\x\equiva_k\pmod{m_k}\end{matrix}\right.$ 过程 计算所有模数的积\(M=\prodm_i\)； 对于第\(i\)个方程： 计算：\(M_i=\dfrac{M}{m_i}\)； 计算：\(v_i={M_i}^{-1...

动态规划——区间DP学习笔记 不含四边形不等式优化。 定义 线性动态规划的局限性在于，它只能顺推或倒退，而不能有子区间依赖的问题。 区间动态规划是线性动态规划的扩展，它将问题划分为若干个子区间，并通过定义状态和状态转移方程来求解每个子区间的最优解，最终得到整个区间的最优解。 区间动态规划常用于解决一些涉及区间操作的问题，是一种高效的求解区间最优值的方法，可以有效地解决各种区间问题。 性质 子区间可拆分：即能将问题分解为能两两合并的形式； 子区间独立性：即将区间\([l,r]\)拆分为两个区间后，这两个区间内无论怎么变化，都不应影响到另一区间的最优值； 子区间可合并：即能将两个或多个部分进行整...

动态规划——数位DP学习笔记 定义 引入 数位DP往往都是这样的题型：给定一个区间\([l,r]\)，求这个区间中满足某种条件的数的总数。 简单的暴力代码如下： intans=0; for(inti=l;i<=r;i) if(check(i))ans; 而当数据规模过大，暴力枚举就\(\mathbbT\)飞了，因此引入数位DP： 概念 数位（digit）：对于十进制，即把一个数字按照个位、十位、百位等，一位一位地拆开，它每一位上的数字，也就是\(0\sim9\)；其他进制可类比十进制。 数位DP：一种按照数位暴力枚举的方式，用来解决一类特定问题；这种问题比较好辨认，一般具有这几个特征：...

动态规划——状压DP学习笔记 引入 前置知识：位运算 动态规划的过程是随着阶段的增长，在每个状态维度上不断扩展的。 在任意时刻，已经求出最优解的状态与尚未求出最优解的状态在各维度上的分界点组成了DP扩展的“轮廓”。对于某些问题，我们需要在动态规划的“状态”中记录一个集合，保存这个“轮廓”的详细信息，以便进行状态转移。 若集合大小不超过\(N\)，集合中每个元素都是小于\(K\)的自然数，则我们可以把这个集合看作一个\(N\)位\(K\)进制数，以一个\([0,K^{N1}]\)之间的十进制整数的形式作为DP状态的一维。这种把集合转化为整数记录在DO状态中的一类算法，就被称为状态压缩的动态规...

动态规划——矩阵优化DP学习笔记 前置知识：矩阵、矩阵乘法。 矩阵乘法优化线性递推 斐波那契数列 在斐波那契数列当中，\(f_1=f_2=1\)，\(f_i=f_{i1}+f_{i2}\)，求\(f_n\)。 而分析式子可以知道，求\(f_k\)仅与\(f_{k1}\)和\(f_{k2}\)有关；所以我们设矩阵\(F_i=\begin{bmatrix}f_{i1}&f_{i2}\end{bmatrix}\)。 设矩阵\(\text{Base}\)，使得\(F_{i1}\times\text{Base}=F_i\)，接下来考虑\(\text{Base}\)是什么；带入可得\(\begin...

基本技巧——根号分治学习笔记 根号分治与其说是一个算法，更不如说是一种思想（trick）。 定义 根号分治，是一种对数据进行点分治的分治方式，它的作用是优化暴力算法；类似于分块，但应用范围比分块更广。 具体来说，对于所进行的操作，按照某个点\(B\)划分，分为大于\(B\)及小于\(B\)两个部分，两部分使用不同的方式处理。（一般以根号为分界，即\(B=\sqrtn\)，因为这样复杂度最平衡） 简而言之，根号分治就是：对数据范围分块处理，将多个暴力算法“拼接在一起”，实现优化复杂度的作用。 算法思路 理论基础 具体思路如下： 对于数据的种类少的部分，可以全部维护； 对于另一部分，不方便维护的...

动态规划——斜率优化DP 适用情况 适用于求解最优解（最大、最小）问题。 可以将转移方程可以化为\(\left[\begin{array}{rl}仅与\spacei\space有关&是我们想要最大/最小化的\\仅与\spacej\space有关&是已知的\\与\spacei\space和\spacej\space都有关&是两项相乘\end{array}\right]\)三部分的，都可以考虑用斜率优化。 形式化的：原式可化为\(dp_i=\min\limits_{j\in[l,r]}\{\mathrmy_jk_ix_j\}a_i\)，其中\(y\)、\(k\)、\(x\)...

WSL创建记录 操作步骤 本文适用于Windows10版本2004及更高版本或Windows11。即内部版本19041及更高版本. 如果你正在使用2004以下版本或你的电脑不支持虚拟化，请阅读：https://oi-wiki.org/tools/wsl/手动安装4. 如果你正在使用1607以下版本的Windows10，你的系统不支持WSL。欢迎关闭这个页面. 0x01启用WSL wsl--install wsl--set-default-version2 第一次运行Ubuntu，需要完成初始化。等待一两分钟时间，系统会提示创建新的用户帐户。输入完用户名以后会提示输入密码。在Linux中，...

CSP-J/S初赛冲刺 对于咱们信奥选手来说，会做的题要坚决不丢分，不会做的题要学会尽量多拿分，这样你的竞赛之路才能一路亨通！ Linux基础操作 文件（文件夹）操作 列出文件：ls 列出隐藏文件：ls-a 列出文件及大小：ls-l 重命名文件：mvold.cppnew.cpp 创建备份：cpfile.cppfile.cpp.bak 查看目录地址：pwd 切换上级目录：cd.. 切换目录：cddirx 创建目录：mkdirdirx 删除目录：rm-rdirx 点击查看代码 运行程序：./test 计时运行：time./test 重定向输入输出：test<in.txt>out.t...