『初丶晴』的小窝

解忧杂货店 [日]东野圭吾 2023.07.30 记 最意味深长的一句话，莫过于作者在小说结尾处写下的，一份对『无名氏朋友』的寄语： 地图是一张白纸，这当然很伤脑筋。任何人都会不知所措。 可是换个角度来看，正因为是一张白纸，才可以随心所欲地描绘地图。一切全在你自己。对你来说，一切都是自由的，在你面前是无限的可能。这可是很棒的事啊。我由衷祈祷你可以相信自己，无悔地燃烧自己的人生。 回顾整本书，情节错综，人物也有很多。但是越往后读越能感受到不同人的情节间的交叉、错综，甚至是对人生有着相互的影响。 整本书主要讲述浪矢雄治先生开的『解忧杂货店』的形形色色的小故事，其中暗线是杂货店和各位人物与孤儿院『丸光园』之间的联系。通过办理解忧业务，浪矢先生曾在儿子面前一再坚持，而最终因病去世。 但这间杂货店仿佛有魔法一般。杂货店仿佛能沟通今昔，相互来信。情节部分就不过多赘述了，总而言之写得非常圆润，给人一种即在情理之中，又在意料之外的感觉。 要说起能从书中读到什么，还要从那个寄语说起。 最近心烦意乱，总觉得有种莫名的压力，抑或是恐慌，故找到这本书，想让杂货店也为我“解解忧” ...

Problem.1 等比数列求和 题目标签：分治、数学 题目大意 对于有 \(x+1\) 项的等比数列 \(A=a^0+a^1+\cdots+a^x\)，求 \[ (\sum\limits_{i-1}^xa^i)\bmod p \] 数据范围 \(1\leq a_i,x\leq 10^{18},1\leq p\leq 10^9\)。 解题思路 考虑分治。 对于指数区间 \([0,m]\)，令 \(m'=\dfrac{m+1}{2}-1\)。考虑对 \([0,m']\) 和 \([m'+1,m]\) 分治进行处理。 对于区间 \([0,m']\)，求得 \(U=\sum\limits_{i=0}^{m'}a^i\)。 对于区间 \([m'+1,m]\)，可以同时通过分治计算 \(V=a^{m'+1}\)，然后进行分类讨论： 若 \(m\) 为奇数，则有偶数项，此时区间和为 \[ U+UV \] 若 \(m\) 为偶数，则有奇数项，考虑先处理前 \(m-1\) 项，最后加上第 \( ...

线性代数基础 线性代数是OI中常用的一部分数学知识。本篇主要记录高斯消元法和基础矩阵变换。 一、矩阵 矩阵是数学中常用的代数工具。当然，信息代数中的重点也许与数学不同，但大体思路相仿。 1.1\(\quad\) 矩阵的定义 矩阵\(\quad\)对于一个由 \(n\times m\) 个数根据某些性质、关系组成的向量表 \[ \begin{bmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,m}\\ \end{bmatrix} \] 称为 \(n\times m\) 的矩阵，记作矩阵 \(\mathbf{A}\)。 若矩阵 \(\mathbf{A}\) 和矩阵 \(\mathbf{B}\) 都是 \(n\times m\) 的矩阵，则称 \(\mat ...

8dfed501bcaa90b15714e3bdc993ce4cd992d53dfa3b2cc635d9ae939003f1ddcc424989075bdf424c5cb8f31000e57a9db4b0b97597d7d935821682bf3633fffd00d5c963e68ad05871d197e65a01321f85019fd432b205f717ff68148ebc12c0b49a072407ab0677d01a937dfceb2e0a2e14a4984b60038ff67269d4921698512bf2c771ae7bcd71038c80bee8545adc71622332fbe3847f4be15490d5d6026b95a1bd83f5f8a92d20f21e7611929dc818dc3198c2a62c85a6f3104ab0c940e4e2f06a2d537f321bc84189b6ce308efc4b670e4207fd2c181973dab3024b8722245d5b1b12d92ce8152e6db968c59d67266e22b2f3116a0 ...

树链剖分 树链剖分，就是将树剖分为若干条链，用来维护树上信息，常搭配树上值域线段树，如： 修改树上两点间的最短路径上的节点权值 查询树上两点间的最短路径上的点权和 修改以某个点为根的子树的每个节点的点权 查询以某个点为根的子树的节点权值和 其中，操作3和4可以直接建立树上值域线段树解决，操作1和2需要进行树链剖分。 树链剖分有三种方法：重链剖分（复杂度 \(O(\log n)\)）、长链剖分（复杂度 \(O(\sqrt n)\)）和实链剖分（常用于LCT维护）。其中，重链剖分最为常见，因此本节主要记录重链剖分的学习笔记。 一、基础定义 重儿子：一个节点的所有儿子中，子树大小最大的那一个儿子。如有多种选择，就只选一个儿子。 轻儿子：一个节点的所有儿子中，不是重儿子的节点。根节点也是轻儿子。 重链：从一个轻儿子开始，沿着重儿子走，连出的极大子链。 轻链：不是重链的子链。 重链定理\(\quad\) 除了根节点以外的任何一个节点的父亲一定在一条重链上。 二、重链剖分 重链剖分，需要我们维护一下内容： fa[MAXN]，即节点的父节点。 dep ...

组合计数 本章主要记录基础组合数学的有关知识，包括加法原理、乘法原理、排列组合、二项式定理、卢卡斯定理等基本知识。 一、计数原理 基础的计数原理包括加法原理和乘法原理，是组合数学的基础。 1.1\(\quad\)加法原理 若完成一件事情的方法有 \(n\) 类，其中第 \(i\) 类方法有 \(a_i\) 种不同的方法，且这些方法互补重合，则完成这件事一共有 \(\sum_{i=1}^na_i\) 种不同的方法。这样的计数原理称为加法原理。 例\(\qquad\)中午可以去A、B、C三个街区吃饭，三个街区分别有 \(6\)、\(5\)、\(8\) 家餐厅，那么中午吃饭有 \(6+5+8=19\) 家餐厅可选。 1.2\(\quad\)乘法原理 若完成一件事情需要 \(n\) 个步骤，其中第 \(i\) 个步骤有 \(a_i\) 种不同的完成方法，且这些步骤互不干扰，则完成这件事一共有 \(\prod_{i=1}^na_i\) 种不同的方法。这样的计数原理成为乘法原理。 例\(\quad\)餐厅有 \(4\) 种主食，\(2\) 种配菜，\(5\) ...

同余 本章主要记录有关同余、费马小定理、欧拉定理、扩展欧几里得算法、裴蜀定理、乘法逆元、威尔逊定理、线性同余方程、中国剩余定理、扩展中国剩余定理、BSGS以及扩展BSGS的学习笔记。 由于内容复杂且关联较少，建议配备 ctrl+F 进行快乐食用。 正在继更ing 一、基础知识 这个板块着重介绍同余的基本知识，虽然多为数学竞赛内容，但也对信息学竞赛有不少帮助，定理和性质为拓展内容。 本部分参考《初等数论》进行撰写。 1.1\(\quad\)基本定义、定理与性质 定义1（同余）\(\quad\) 设 \(m\neq0\)。若 \(m\mid a-b\)，即 \(a-b=km\)，则称 \(m\) 为模，\(a\) 同于与 \(b\) 模 \(m\) 以及 \(b\) 是 \(a\) 对模 \(m\) 的剩余，记作 \[ a\equiv b\pmod{m} \tag{1} \] 不然，则称 \(a\) 不同余于 \(b\) 模 \(m\)，\(b\) 不是 \(a\) 对模 \(m\) 的剩余，记作 \(a\not\equiv b\pmod{m}\) 式 \((1 ...

基环树 一、基本概念 如果一张无向连通图包含恰好一个环，则称它是一棵基环树(Pseudotree)。 如果一张有向弱连通图每个点的入度都为 ，则称它是一棵 基环外向树。 如果一张有向弱连通图每个点的出度都为 ，则称它是一棵 基环内向树。 多棵树可以组成一个森林(Forest) ，多棵基环树可以组成基环森林(Pseudoforest) ，多棵基环外向树可以组成基环外向树森林，多棵基环内向树可以组成基环内向森林(Functional graph) 。 二、算法实现 在基环树中，有许多独一无二的性质，这也就成为良心出题人增加题目难度的一种措施。通常会结合树的直径进行考察。 下面就一些例题进行分析 下面以 [IOI2008] Island 举例。 题目大意：现有一个基环森林，求出森林中每颗基环树的直径的和。 基环树直径，就是图中最长链的长度。因为基环树的一些特性，这也成为常考点。 显然，基环树的最长链可能有两种情况： 在去掉“环”的某棵子树中。 经过“环”，其两端分别在去掉“环”上所有边之后的两颗不同子树中。 我们可以先用一次dfs找出基环树中 ...

欧拉回路 2023.09 updated 一、基本概念 欧拉路径：从图中一个结点出发走出一条道路，每条边恰好经过一次的路径。 欧拉回路：从图中任意一个顶点出发走出一条道路，每条边恰好经过一次，并最终回到起点。这样的路径称为“欧拉回路”。（类似于一笔画问题） 欧拉图：具有欧拉回路的图。 半欧拉图：具有欧拉路径但不具有欧拉回路的图 二、算法实现 对于求欧拉回路，我们可以分为两种情况解决： 无向图的欧拉回路(图a、b)：对于无向图，只要是一个连通图并且每个点的度是偶数，那么这个图就能构成欧拉回路。 有向图的欧拉回路(图c、d)：对于有向图，只要是一个连通图并且每个点的入度等于出度，那么这个图就能构成欧拉回路。 对于求欧拉路径，我们也可以分为两种情况解决： 无向图的欧拉路径：对于无向图，只有是一个连通图，并且两个点的度为奇数，剩余为偶数是，那么这个图就能有欧拉路径。 有向图的欧拉路径：对于有向图，只要是一个连通图，并且一个点的入度等于出度加一，一个点的入度等于出度减一，其余点入度等于出度时，这个图就有欧拉路径。 一个欧拉图一定有欧拉路径。 ...

有向图的连通性 一、基本概念 强连通：在有向图 \(G\) 中，如果两点 \(u\) , \(v\) 是互相可达的，则称 \(u\) 和 \(v\) 是强连通的。如果 \(G\) 中的任意两个点都是互相可达的，那么 \(G\) 就是强连通图。 强连通分量：如果一个有向图 \(G\) 不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任一点强连通，像这样的一个“极大强连通”子图是\(G\)的一个强连通分量( \(\text{Strongly Connected Component}\)，\(\text{SCC}\) ). \(Tarjan\)算法能在一次DFS中吧所有点都按 \(\text{SCC}\) 分开。这并不是不可思议的，它利用了 \(\text{SCC}\) 的特点。 定理：一个 \(\text{SCC}\)，从其中任何一个点出发。都至少有一条路径能绕回到自己。 二、算法实现 在讲解之前，先了解\(low\)和\(num\)操作。 下面是一个例子，下图有三个 \(\text{SCC}\)， ...