JamhusTao の Blog

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 赛时有个看着很正的猜想，最后是正确的。至于为什么正确，我也没再研究，可以参考其 ...

前往 小工具指北 分类 首先声明本文仅预览 MyKeymap，更多内容请 前往 咸鱼阿康 主页 嗯，首先是官方支持，作者是国人。支持 QQ 群交流、Github 反馈、Bilibili 视频教学，自己去上面的链接取吧。 MyKeymap 的键位非常友好，触发热键的键位分别有 Caps、Tab、3、9、F、J、, 等。 同时支持的快捷操作不仅包括键盘、鼠标操作，还支持窗口操作和系统调用，你甚至可以自编程序使用它来调用。 文档很友好，我就不重复了。

前往 小工具指北 分类 首先声明本文仅介绍该工具的部分内容，更多内容请 前往 FFmpeg 官网 前言 FFmpeg 是一个简单的视频编辑命令行工具，可以实现简单的视频编辑工作。相比于大型的视频剪辑软件，其优势是轻量。 我认为 FFmpeg 最大的优势莫过于其便捷的视频格式转换，在这种场景下图形界面显得多余。本文也将重点介绍这一部分的功能。 你还可以将它嵌入到代码中，可以使用命令行接口，也可以使用库支持，如 python 的 ffmpy 。 优化 在正文开始之前，我一定要将 优化 放在前面，否则你的 ffmpeg 会跑得非常慢。 在你的所有命令最后加上 -vsync 2，例如： 1ffmpeg -i example.webm -vsync 2 example.mp4 打开前后效率对比（数据仅供参考）： 状态 转换倍率 CPU 占用 None ≈1.5×\approx 1.5 \times≈1.5× ≈40%\approx 40\%≈40% -vsync 2 ≈15×\approx 15 \times≈15× ≈25%\approx 25\%≈25% 常用命 ...

回到文章目录 Hexo 标签外挂仅适用于 Hexo 框架内，在其他应用、平台均不适用，如果您没有使用 Hexo 标签外挂的需求请绕道。另外，不要在任何标签外挂中使用标题，不要在标签外挂的声明中使用英文逗号。 本文参考官方文档 Butterfly 安裝文檔(三) 主題配置-1，更多标签外挂相关内容见文档。本文仅介绍几种比较常用的。 Note 提示框 Note 提示框支持所有行级语法，不支持块级语法。 我是 Note 提示框 配置文件 配置位于 _config.butterfly.yml ，实际上通常只修改 note.style 。 12345678910111213# Note (Bootstrap Callout)note: # Note tag style values: # - simple bs-callout old alert style. Default. # - modern bs-callout new (v2-v3) alert style. # - flat flat callout style with backgroun ...

Alice and Bob 前往 算竞题解 分类 || 前往 算竞模板 分类 原题链接 Alice and Bob 2023“钉耙编程”中国大学生算法设计超级联赛（6） Alice and Bob 2023杭电多校 补题 Alice and Bob 2023杭电多校 Virtual Judge 简明题意 Alice 和 Bob 玩游戏，给定一个长度为 nnn 的数组 aaa。每次操作，将数组截断分为两部分，并且保留求和较大的部分；如果两部分求和相等，保留左半部分。Alice 先手，双方轮流对数组操作，最终无法操作者败，双方都想获胜。不仅如此，必胜者想要最后留下最大的数字，必败者想要最后留下最小的数字。问：两者足够聪明，Alice 和 Bob 谁将获胜，并且最终剩下的数字是什么？ 多组测试数据，n≤3000n \le 3000n≤3000 ，∑n≤10000\sum{n} \le 10000∑n≤10000 。 解题思路 状态转移方程 博弈论通常可以分为三种：dpdpdp 胜负态转移，SGSGSG 函数转移，SGSGSG 函数推结论，以及各种奇奇怪怪的博弈题。这道题不仅要我们求出胜负态 ...

回到文章目录 建站提交历史文章，原文写作时间 2023 年 1 月 11 日前后。 目前最常用的 git 代码仓库非 github 莫属，本文将以 github 为例，介绍远程仓库的使用。 创建远程仓库 使用远程仓库前，你需要在 github 上注册一个用户，并创建一个 repository ，当然你也可以使用自己搭建的 Git服务器 。 创建你的第一个仓库，建议将它命名为 test。 按照 Quick setup 指示，在本地的一个空目录下使用命令行完成下面的命令，以自己该界面的命令为准。操作成功后刷新当前界面，将会发现出现一个 README.md 文件，至此完成远程仓库的基本测试。 操作远程仓库 123456789101112131415# 连接git remote add {origin} {url} # 与远程仓库建立连接，命名为 origingit remote # 打印标识的远程仓库目录git remote -v # 打印远程仓库信息gi ...

回到文章目录 建站提交历史文章，原文写作时间 2023 年 1 月 11 日前后。 储藏库 储藏库用于在临时切换工作时，不上传工作区到版本库，对工作区的临时存储。 12345678git stash # 向储藏库推入工作区git stash list # 打印储藏库目录git stash apply # 从储藏库拉取 0 号工作区git stash apply stash@{id} # 从储藏库拉取 id 号工作区git stash apply --quiet # 无反馈地拉取 0 号工作区git stash drop # 从储藏库删除 0 号工作区git stash drop stash@{id} # 从储藏库删除 id 号工作区git stash pop # 从储藏库拉取并删除 0 号工作区 apply 命令会返回一段文字，如不存在 Aborting ，为正 ...

回到文章目录 建站提交历史文章，原文写作时间 2023 年 1 月 11 日前后。 标签管理 tag 可以视为静态的分支，不能移动，除此之外具有与分支相似的功能。 12345git tag {tag} # 给当前分支附加标签 taggit tag {tag} {id} # 给 id 的提交附加标签 taggit tag # 打印标签目录git tag -d <tag> # 删除标签git show <tag> # 打印标签详细信息, 包括标签与其上一版本差异