JamhusTao の Blog

建站提交历史文章，原文写作时间 2023 年 2 月前后。 回到文章目录 Linux 开发环境搭建 安装虚拟机（或云服务器）：VMware 自行获取，付费。 安装Linux系统：Ubuntu https://releases.ubuntu.com/bionic/ 下载并在VMware按照向导完成Linux虚拟机配置与安装。 你可能会关注到系统界面尺寸与屏幕尺寸不匹配，有如下解决方案： Settings →\to→ Displays →\to→ 配置参数 →\to→ Apply 参数： Resolution：（选择与你的电脑相近的分辨率） Scale： 200% 安装 VMware-Tools，将自适应屏幕尺寸，还有一些其他功能。（我不会） 后续使用中，很少直接操作虚拟机界面，所以无需过于关注分辨率问题（多关注下面的内容吧）。 安装XSHELL、XFTP https://www.netsarang.com/zh/free-for-home-school/ 经邮箱认证，提供免费家庭与学校版本。 XSHELL用于命令行控制远程主机，XFTP用于与远程主机交互文 ...

建站提交历史文章，原文写作时间 2023 年 2 月前后。 前言 这是我在学习 Linux 系列时做的笔记。最近在学习青训营相关课程时想起来上传到个人博客。 整理自牛客网的一个课程：课程列表_牛客网 ，课程的全名叫做 Linux 高并发服务器开发。 目前这部分课程我还没有学完，想起来被我搁置半年了。 前置知识 Linux 系统常用命令，这一块我也有相关整理，虽然不适合小白：Linux 入门笔记 - Ubuntu vim基本使用。 VSCode 基本使用。 C/C++ 基本语法。 目录 Linux 系统入门 1.1 Linux 开发环境搭建 1.2 GCC/G++ 基本使用 1.3 静态库与动态库制作 1.4 Makefile 基本使用 1.5 GDB 基本使用 1.6 文件操作与目录操作 1.7 虚拟内存地址 Linux 多进程开发 2.1 进程概述 2.2 进程基本控制 2.3 进程通信 2.4 守护进程 Linux 多线程开发 3.1 线程概述 3.2 线程基本操作 3.3 锁与线程同步 网络编程 ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 本文包括：费马小定理求逆元、扩展欧几里得算法求逆元、线性递推求逆元。 三者的区别 费马小定理求逆元：要求模是质数，复杂度 O(log⁡2n)O(\log_2{n})O(log2​n)，最常用。 扩展欧几里得算法求逆元：不要求模是质数，复杂度 O(log⁡n)O(\log{n})O(logn)。 线性递推求逆元：线性求出所有逆元，复杂度 O(n)O(n)O(n)。 模板题链接 下方模板自取，相关证明见下方链接相关题解。 洛谷 P3811 【模板】乘法逆元 费马小定理求逆元 123456789101112131415161718// 费小求逆元. 要求模是质数. 依赖: quick_pow. 复杂度: O(log(MOD)).const int MOD = 1000000007;// 快速幂int quick_pow(int base, int exponent) { int res = 1 % MOD; base %= MOD; while (exponent) { if (e ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 本文将介绍：快速幂、龟速乘、矩阵快速幂、欧拉降幂、光速幂。 快速幂在众多数论中有非常重要的地位，也是其中最频繁用到的部分，朴素地求 aba^bab 时我们可以做到 O(n)O(n)O(n) 的时间复杂度，而快速幂将其提升到 O(log⁡2n)O(\log_2{n})O(log2​n)。 本文除了介绍快速幂还会介绍相关拓展，如上面列出。 快速幂 其实快速幂的思想很简单，我们可以求出 a, a2, a4, a8 …a,~a^2,~a^4,~a^8~\dotsa, a2, a4, a8 …，而任意所求的 aba^bab 一定可以表示成若干个 a2na^{2^n}a2n 的乘积，而这个数量级一定是 O(log⁡2n)O(\log_2{n})O(log2​n) 的。 ​链接： 洛谷 P1226 【模板】快速幂 123456789101112131415161718192021222324// 不带模数的快速幂, 基本不用int quick_pow(int base, int exponent) { int res = 1 ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 LucasLucasLucas 定理用于处理带模数排列数的计算，O(n)O(n)O(n) 预处理，O(log⁡n)O(\log{n})O(logn) 询问。 LucasLucasLucas 定理要求模数 ppp 为质数，而扩展 LucasLucasLucas 算法不要求，后者时间复杂度略高于前者，为 O(log⁡plog⁡m)O(\log{p}\log{m})O(logplogm)。 模板题链接 下方模板自取，相关证明见下方链接相关题解。 前置：各种求逆元、逆元求组合数、中国剩余定理、WilsonWilsonWilson 定理。 洛谷 P3807 【模板】Lucas 定理 洛谷 P4720 【模板】exLucas Lucas 定理 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354// Lucas 定理求排列组合// 时间: O(log_MOD(n)) + 预处理: O(MOD)/ ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 在开始这篇文章前你一定对如何分解质因数有所了解，我们可以枚举 n\sqrt{n}n​ 个数进行试除，最坏时间复杂度为 O(n)O(\sqrt{n})O(n​)，如果使用素数筛优化，可以将复杂度降到 O(nln⁡n)O(\frac{\sqrt{n}}{\ln{n}})O(lnnn​​)。 而这里介绍的 Miller RabinMiller~RabinMiller Rabin 和 Pollard RhoPollard~RhoPollard Rho 算法是两种概率算法。Miller RabinMiller~RabinMiller Rabin 可以在 O(klog⁡2n)O(k\log_2n)O(klog2​n) 的时间内判断 nnn 是否为素数，其中 kkk 表示测试次数，测试次数越多，算法正确率越高。Pollard RhoPollard~RhoPollard Rho 在 nnn 不为素数时，可在 O(n1/4)O(n^{1/4})O(n1/4) 的时间内找到 nnn 的一个因数（111 除外），注意不一定是质因数。 这两种算法都有随 ...

本文为笔记，分为前章和正文两部分。全文介绍简略，适合有基础速通。 前章 Ubuntu 系统安装 下面提供三种安装方式，自行选择。 WSL (Windows Subsystem for Linux)，Windows 官方支持的 Linux 子系统，可以参考 我的文章 。 虚拟机安装 Linux，传统的比较重量级的方式，可以参考 我的文章。 双系统安装 Linux，获取完备的计算机性能，但无法同时运行两个系统，可以参考 Windows 和 Ubuntu 双系统的安装和卸载 - Bilibili。 图形界面 虽然一般不会将 Linux 作为日用机，而是作为远程开发平台。但如果你打算将 Ubuntu 作为你的日用机的话，下面为你使用 Ubuntu 图形界面提供一些建议。 安装应用 应用程序安装方式主要有三种：apt、dpkg、snap、appimage。 其中 apt 可以直接从网络获取并完成安装，是 Ubuntu 上最常用的安装方式，正文会有介绍。 snap 提供沙盒化的软件安装，提供隔离的软件环境。 appimage 是一个可以直接运行的单体文件，无需安装过程，直接运行即可。 dpk ...

Semi-Puzzle: Brain Storm 前往 算竞题解 分类 || 前往 算竞模板 分类 原题链接 B-Semi-Puzzle: Brain Storm 2023牛客暑期多校训练营9 简明题意 给定 a(1≤a≤109)a(1 \le a \le 10^9)a(1≤a≤109) 和 m(1≤m≤109)m(1 \le m \le 10^9)m(1≤m≤109)，求 uuu 使得 au≡u(modm)a^u \equiv u \pmod{m}au≡u(modm)，要求 1≤u≤10181 \le u \le 10^{18}1≤u≤1018。 多组测试数据，T≤1000T \le 1000T≤1000。 前置芝士 在开始之前你必须要知道以下三个知识点，否则就别想按着题解思路做了。会的应该也不需要此题解了。 我也是边学边写的这道题，过程可以说很艰辛，所以作此文整理一下。 扩展欧拉定理 这个东西通常用于给快速幂降幂，但是确是下一个知识点的前置。 欧拉函数​定义： 在区间 [1,x)[1, x)[1,x) 中与 xxx 互质的数的个数，记作 ϕ(x)\phi(x)ϕ(x)。 ​计算 ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 FFT / NTT / MTT 均基于傅里叶变换从而实现了对于多项式乘法的加速，它将多项式乘法的时间复杂度从 O(n2)O(n^2)O(n2) 降到了 O(nlog⁡n)O(n\log{n})O(nlogn)。 三者的区别 FFT：快速傅里叶变换，用于浮点数多项式卷积。 NTT：快速数论变换，用于带模数多项式卷积，要求模数必须为 NTT 模数。 MTT：任意模数快速数论变换，基于 NTT，小范围内允许任意模数。 模板题链接 下方模板自取，相关证明见下方链接相关题解。 洛谷 P3803 【模板】多项式乘法 洛谷 P4245 【模板】任意模数多项式乘法 FFT 快速傅里叶变换 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758// 快速傅里叶变换(FFT). 时间: O(nlogn)const int MAX = 100005;const double PI = aco ...

PermuTree (Hard Version) 前往 算竞题解 分类 || 前往 算竞模板 分类 原题链接 E2-PermuTree (Hard Version) Codeforces Round 890 (Div. 2) supported by Constructor Institute 简明题意 给定一棵 nnn 个节点的有根的树，每个节点有一个点权 aia_iai​，aaa 是一个 1..n1 .. n1..n 的排列。定义 f(a)f(a)f(a) 为 ai<lca(ai,aj)<aja_i < lca(a_i, a_j) < a_jai​<lca(ai​,aj​)<aj​ 的计数，问对于所有排列，f(a)f(a)f(a) 最大为多少？ Easy Version： n≤5000n \le 5000n≤5000 Hard Version： n≤1000000n \le 1000000n≤1000000 Easy Version 思路 Easy Version 赛时有个看着很正的猜想，最后是正确的。至于为什么正确，我也没再研究，可以参考其 ...