输入： ```plain 1 1000000007 1 ``` 输出： ```plain 1 1000000005 ``` --- 略微注意一下 $a\geq mod$ 的题目。

输入 ``` 2 1 2 5 2 1 2 12 ``` 输出 ``` 8 ``` # 我已急哭 我的错因：不小心把扩展欧拉定理中 $a\geq \varphi(p)$ 写成了 $a\geq p$，逆天。

**输入** ``` 2 1 2 5 2 1 2 12 ``` **输出** ``` 8 ``` 我不小心把扩展欧拉定理的 $a\geq \varphi(p)$ 条件写成了 $a\geq p$。 ### 我已急哭

在文章《NOIP 2025 游记》发表评论：

sto orz

在文章《题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）》发表评论：

抱歉把 $k\in [0,n]$ 写成了 $k\leq [0,n]$

置换：**位置**调换。 |1|2|3| |-|-|-| |2|3|1| **理解A**：位置 $2$ 的值换到 $1$ 位置，位置 $3$ 的值换到 $2$ 位置，位置 $3$ 的值换到 $1$ 位置。 **理解B**：位置 $1$ 的值换到 $2$ 位置，位置 $2$ 的值换到 $3$ 位置，位置 $1$ 的值换到…

# 简化问题 先思考简化的问题，再推广到原问题，可以根据数据特殊性质来简化。 ## $x_i = y_i$ 买多少个都是一样的，所以直接全买最小的即可。 ## $x_i \geq y_i$ 可以理解为“第二份降价”，那么肯定两个两个买，两个两个买谁呢？就买 $x_i+y_i$ 最小的，买到买不起为止。 然后手上还会剩钱…

常见问题。 1. 最优化问题 2. 计数题 3. 字典序最小（如构造） 字典序第 $k$ 小。 # 例1 ## 题意 输入 $n$，$k$。 $1\leq k \leq n\leq10^9$ 求 $[1,n]$ 中所有整数中字典序排名第 $k$ 名的。 ::::success[题解] 对于每一位分别找。 ::::::i…

在讨论《简单题挂难题不会怎么办》回复：

（暂无内容）

对于后缀数组 SA 的倍增做法，建议 $10$ 分钟写完。 因为这是最稳妥的 # 后缀树 将所有后缀放入字典树，得到后缀树。 把两个后缀，得到的就是它们的 LCP。 $height$ 就是 SA 数组中相邻的两个串在树中 LCA 的深度。 理解可以理解为如果这棵树是自然生长的树，height 就是数论的深度。 # he…

[**T1** 洛谷B4273 **最大的矩形纸片**](https://www.luogu.com.cn/problem/B4273) [**T2** 洛谷P5854 **笛卡尔树**](https://www.luogu.com.cn/problem/P5854) [**T3** 洛谷P2171 **Hz 吐泡泡*…

# 铺垫 ## 简单语法基础 ```cpp memset(x,0,sizeof(int) * M); memcpy(x,y,sizeof(int) * M); ``` 理解为 $x=0$ 或者 $x=y$。 ## 计数排序（Counting Sort） 非比较型，有**稳定性**。 给出一种较短的实现（$x[]$排序到…

文本串 $T$ext 模式串 $P$attern # 字符串匹配 KMP 在 $T$ 中找到所有 $P$ 的出现位置。 ::::info[KMP 算法] 使用双指针法预处理出 $P$ 的 $nxt[]$。（即 $P$ 匹配 $P$） 再使用相似的方法进行匹配。（即 $P$ 匹配 $T$） ::::::success[代…

[简化问题](https://www.luogu.com.cn/article/8zam2e78) [线性同余方程组](https://www.luogu.com.cn/article/44nhk5cp) [next_permutaion与Gosper's Hack](https://www.luogu.com.cn/…

# 引入 给定一个排列，每次可以交换两个数，问最少交换几次可以将序列排序。 由于每个数唯一出现一次，所以序列本质上是一个 **排列**。 ::::info[题解] 建立有向边 $i \to a[i]$，每个大小为 $x$ 的环对答案贡献 $x - 1$。 :::: ::::info[编新题] 我：如果题目改为「只能交换…

|快捷键|功能| |:-:|:-:| |`F9`|编译| |`F5`|运行| |`F6`|文件读写运行| |`F2`|在右侧创建输入输出文件窗口| 无论如何，错误流重定向到`.log`文件 ```vim lines=2-2 line-numbers set ar ai si nu rnu ts=4 sw=4 mouse…

本节为思维上的基本功，算法较杂。 # 例题 英雄辈出 ## 题目描述 给你一个排列，你需要输出每个元素后第一个比其大的元素下标，若不存在输出 $-1$。 ## 思路形成 序列转为二维平面点。 上下左右，四个方向，每个方向还能有多解。 序列问题，先用三个特殊序列过脑子： 1. 升序 2. 降序 3. 全部相同的序列 ##…

# 最小生成树专题 ## 基本算法 1. **路径压缩**：优化并查集查找操作 2. **Kruskal算法**：按边权从小到大排序，贪心选择不形成环的边 3. **Prim算法**：从单点出发，逐步扩展最小生成树 4. **Dijkstra算法**：解决单源最短路径问题，与Prim算法类似 ## 练习：自编MST问题…

[整理前的笔记](https://www.luogu.com.cn/paste/5ahykibs) # 区间处理专题 ## 无效区间剔除规则 在处理区间问题时，我们常需要剔除无效区间，主要分为两种情况： 1. **被包含的区间（留大不留小）**：当一个小区间完全被一个大区间包含时，我们保留大的区间 2. **包含别的区…

# 题目大意 给你 $n$ 个数字 $a_1,a_2,\ldots,a_n$。 有 $q$ 个问询，每次询问区间 $[l,r]$，询问将区间内的数字作为边长能否构建出两个非退化三角形（不能重复使用一个数字）。 $n,q\leq10^5, a_i\leq10^9$。 # 入手 先简化问题，如果只要一个三角形，并且只有一次…

本题可能卡 `unordered_map`，请使用 `map`

# 入手 如果两条道路被放在同一侧（同为环内或环外）且它们的端点区间相互交叉，就会产生冲突，此时必须将它们分配到不同侧，这是一个约束关系。 我们需要枚举每对有约束的边对并尝试满足全部的约束。 # 解法 将所有有约束的两条边的边号连上，然后通过染色的方法匹配二分图即可。 复杂度为 $O(m^2)$ # 程序设计 我使用了…

# 约定 本文约定 $\circ$ 运算符表示将若干个整数依次拼接。 例如 $12 \circ 34 \circ 0 = 12340$。 显然有 $f(a\circ b)=f(a)+f(b)$。 # 方法 因为 $k\leq9$，所以 $x$ 在进位的时候至多进一位。 再观察样例，就不难想出将答案表示成这样。 $$x=…

# Dirichlet Convolution 数学题的好东西，很多时候会用它来解题，比如快速判断一个函数是否为积性，很方便。 ## 定义 $$ (f * g)(x) = \sum_{d \mid x} f(d) \cdot g\left(\frac{x}{d}\right) $$ ## 性质 ### 交换律 / 结合…

# CF1037E ## 入手 先考虑将问题简化， 如果只要求一天晚上的人数怎么做？ 答案：重复将所有度数小于 $k$ 的点去掉，并删除相邻的边，直到没有这样的点为止。 不难看出这是一个改版的拓扑排序。 ## 解法 通过这样的方法，我们就可以先求出最后一天的旅行人数。 考虑从 $m$ 天到第 $1$ 天倒着求，第 $i…

# next_permutation 的实现 ```cpp bool nxtp(){ int i=n-1; for(;i>=1;i--)if(a[i] =1;j--)if(a[i]<a[j])break; std::swap(a[i],a[j]); std::reverse(a+1+i,a+1+n); return 1…

# CF1389E ## 入手 因为星期几有周期性，可以转化为同余问题。 $$(x-1)d+(y-1) \equiv (y-1)d+(x-1) \pmod{w}$$ 移项并因式分解得： $$(x-y)(d-1)\equiv 0 \pmod{w}$$ 我们将 $x-y$ 改为 $y-x$，因为题目中 $y>x$： $$(…

WA #14 #15 因为会删除，使用 `set` 会导致你多删。 请使用 `multiset`

# exgcd 本质：**为了求得大系数的解，算小系数方程的解，并推上去**。 $$ \boxed{\text{思考问题时刻记住目标}} $$ ## exgcd验证方法 写一个程序，枚举 $a$ 和 $b$，判断算出来的解 $(x,y)$ 能否满足 $ax+by=\gcd(x,y)$。 ## 思维扩展 很多式子可以转化…

# CF1467D Sum of Paths ## 切入 操作会变更元素的值，十分麻烦，但发现每个元素的贡献次数是固定的。 这么说，对于第 $i$ 个元素存在贡献值 $c_i$，代表 $i$ 在所有路径上被经过的次数总和，这样答案总为 $ans=\sum a_i\times c_i$。 我们仅需算出数组 $c$ 即可算…