基础知识简介线段树是一颗不那么完全的二叉树。 设线段树有 $h$ 层，则第 $1\sim h-1$ 层是满的，而第 $h$ 层并不一定是满的，而是由第 $h-1$ 层的非叶子节点伸出两个儿子。 维护区间序列信息； 所有非叶子节点都有两个儿子 树...

省流：本文将介绍用指针实现线段树，并介绍如何在题目中运用线段树解决问题。 线段树 の 实现线段树一般用于维护区间信息。 题目示例要求维护一个序列 $\{a_n\}$，实现两种操作： 给定 $l,r$ 和 $x$，让 $a$ 中 $[l,r]...

题目给定 $n,m,p$，求$$ {n\choose m}\bmod p $$ 杨辉三角递推 PS：该做法适用于 $p$ 恒定时的做法。 $\textbf{Solution}$根据组合恒等式$$ {n\choose m}={n-1\choose m...

基础知识矩阵定义晚点写。 矩阵加法/矩阵减法晚点写 矩阵乘法前置条件矩阵乘法有意义，当且仅当第一个矩阵的列数和第二个矩阵的行数相同时。 则此时两个矩阵相乘的行数为第一个矩阵的行数，列数为第二个矩阵的列数。 可以记为将两个矩阵相同的一个边长...

定义若 $c\mid a$ 且 $c\mid b$，那么称 $c$ 为 $a$ 和 $b$ 的公约数。 在 $a$ 与 $b$ 的所有公约数中，最大的那一个称为最大公约数，记为 $\gcd(a,b)$，在不混淆的情况下亦可记为 $(a,b)$。 性质...

费马小定理定理如果$$ p\in \mathbb{P}\,\, \operatorname{and}\,\, p\not\mid a $$那么有$$ a^{p-1}\equiv 1\pmod p $$ 证明 引理 1若 $a\cdot c\equiv...

$\textbf{Solution}$$\textbf{F}_{\textbf{1}}$观察 $n$ 的范围，由于 $1\le n\le10^6$，足以开下一个完整的数组，所以可以直接进行模拟。 对于每一个输入的 $a$，枚举 $\max\{a-2,...

$\textbf{Solution}$ 选择与扶苏本轮打出的牌花色相同且点数大于扶苏打出的牌中点数最小的一张打出。 上面这句话是题目的核心。 首先，必然要开题目描述中的 $4$ 个数组 $f_1,p_1,f_2,p_2$，然后由于已经打出的牌无法...

算法分析首先，由于要求最大化下面的式子：$$ \sum\limits_{i=1}^{n-1}(b_{i}^{b_{i+1}}\bmod998244353) $$容易想到使用 DP。 其次，由于双端队列需要控制两端的位置，所以显然要使用区间 DP。 状...

$\textbf{Description}$给定一张 $n$ 个点的带权无向完全图，求出从 $0$ 到 $n-1$ 经过每个点恰好一次的最短路径。 $\textbf{Solution}$$\textbf{Brute Force}$考虑最朴素的做法。 ...