矩阵快速幂广泛应用于将线性递推关系（如斐波那契数列）、图论中的路径计数、带固定状态的动态规划问题（如铺砖或字符串构造）等场景，转化为矩阵的高次幂运算，从而在 [latex] O (\log n)[/latex] 时间内高效求解第 [latex] n [/latex] 项或长度为 [latex] n [/latex] 的方案数。 矩阵快速幂 由于矩阵…

本文介绍线性代数中一个非常重要的内容——矩阵（[latex]Matrix[/latex]），主要讲解矩阵的性质、运算，以及矩阵乘法，只讲解一些基础内容，非原创。 定义 由 [latex]m × n[/latex] 个数 [latex]a_{ij}[/latex] 排成的 [latex]m[/latex] 行 [latex]n[/latex] 列的数…

置换环 置换环是用来求解将乱序排列变成有序排列所需最小交换次数这一类的问题。 思想：每个元素都向其下标建一条边，最终每个元素都会在一个环中，这个环就是置换环，可知最优情况下元素之间的交换都只会在一个环内进行，一个环最小的交换次数就为 [latex]size[/latex]（环中元素数量）[latex]- 1[/latex]。 例如，对于 [late…

概述 二分法是一种非常常用的优化技巧，它可以分为二分查找、二分答案、浮点数二分和三分法等。 先从一个猜数字游戏来引入二分，猜一个 [latex]1[/latex] ~ [latex]100[/latex] 的数字： 有些聪明的小朋友肯定是先从 [latex]50[/latex] 开始猜； 为什么从 [latex]50[/latex] 开始猜呢？因为…

二进制 二进制（[latex]Binary System[/latex]）是一种以 [latex]2[/latex] 为基数的数制，只使用两个数字符号：[latex]0[/latex] 和 [latex]1[/latex]， 每个数字称为一个比特（[latex]Bit[/latex]，[latex]Binary digit[/latex]…

字典树简介         字典树（[latex]Trie[/latex]，又叫前缀树）是一种 树形数据结构，常用于高效地存储和查找字符串集合。它的核心思想是：公共前缀只存储一次，不同字符串在前缀相同的部分共享路径。 定义 数据结构约定： [latex]tr[u][c]…

    背包问题（Knapsack Problem）是经典的动态规划问题之一。它描述的是在容量有限的背包中，选择若干物品放入，使得总价值最大化。 01背包     01背包问题，就是给定 n 种物品，每种物品都有重量和价值，每种物品都只有一个。 求最大价值 题目链接：2. 01背包问题 - AcWing题库 …

1.Vacations 链接：https://codeforces.com/problemset/problem/698/A 思路：     定义 [latex]dp[i][j][/latex] 为第 [latex]i[/latex] 天为 [latex]j[/latex] 时前 [latex]i[/late…

ranges 和 views 简介 ranges     std::ranges 是 C++20 引入的一个新库，它将“范围（range）”作为一等公民。一个 range 是任何可以迭代的对象，比如数组、容器、生成器等。     它提供了类型安全、更简洁的算法接口，例如…

概念    数学期望（Mathematical Expectation），也叫均值（Mean）、期望值（Expected Value），是概率论中的一个核心概念。它描述的是在大量重复试验下，随机变量的平均值。    生活中我们经常无意中用到期望的思想。比如你每天上班的路程可能遇到两种情况： 不堵车：[latex]20[…