一种搜索&动态规划的形式化框架的构建尝试-Ver.1

Piwry · 2026-06-13 00:13:10 · 算法·理论

0. 前言鲜花

虽然最近在了解了一些凸优化领域的定理和概念后，其实对自己先前写的这篇文章颇有微词，感觉改进的空间可能比较大；但又想到短时间内大概率也不太会有时间二次整理概括这块内容，所以就想着干脆先把已经完成的部分整理一下发出来；姑且也可作为抛砖引玉之用...

大部分内容完成于 26.03.24。文章整理于 26.6.13。

（另外，在部分单行出现的“补充阅读：ref. ...”的意思是，后面紧接着的会涉及一些笔者感觉会有歧义的概念（虽然也可能是笔者使用的不太规范...），于是建议可以先去引用的对应附录章节查询、以消歧义。）

1. 搜索

1.1. 搜索的定义

（p.s. 另一种理解路径，是先定义 \mathcal{K, V, R}，然后才得出 \mathcal{S}，该路径是“从总体思考得到状态空间”；而下文更接近 “从部分状态出发推测整体值空间、状态空间”。）

状态空间（解空间）\mathcal{S} 是一个元组的集合，且包含的所有元组长度都为给定值 \mathcal{K}（状态维度）；状态 s\in \mathcal{S} 是一个元组；值空间 \mathcal{V}=(\mathcal{V}_1, \mathcal{V}_2, \cdots, \mathcal{V}_\mathcal{K}) 是一系列集合，\mathcal{V}_i 包含 s 元组中第 i 个位置的所有可能取值（从实际应用出发，我们默认 \mathcal{V}_i 一定是有限集）、即 \mathcal{V_i}=\{a \mid \exist s\in \mathcal{S}, a=s_i\}。

（补充阅读：ref. 3.4. \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i} 符号定义。）

考虑集合 \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}，（注意到 \mathcal{S}\subseteq \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}），规则集 \mathcal{R}=\{\rho:\prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}\to \{0, 1\}\} 满足 |\mathcal{R}|<\infty 且 \forall \rho\in \mathcal{R}: \rho(s)=1 \lrArr s\in \mathcal{S}，是用于从 \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i} 生成 \mathcal{S} 的，体现了题目的限制条件（同时也能帮助优化搜索）。

另外，我们还有一个目标函数 f:\mathcal{S}\to Y=f(s)=f(s_1, s_2, \cdots, s_{\mathcal{K}})，陪域 Y（返回值类型）可以是例如实数、或 bool（\{0, 1\} 是否满足条件）等等。

目标可以是求 f 最值、或求满足 f 条件的个数（即计数；即 |\{s\mid f(s)=1 \land s\in \mathcal{S}\}|；另外对于 “计算 \mathcal{S} 大小” 可认为是 f:\mathcal{S}\to \{1\}）、或其它更复杂的对 f 的统计。

枚举是指（至多）枚举集合 \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}，（因注意到 \mathcal{S}\subseteq \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}），从而遍历状态空间集合 \mathcal{S} 的每一个元素至少一次，最终达成目标。

而搜索是指以特定策略（顺序）进行枚举；当无序/没有特定顺序时也可直接称为枚举。搜索的顺序往往和目标强相关；例如，目标函数 f(s) 的定义可能是递归的（如 f(i)=f(i-1)+g(i)），从而在计算某一状态的目标函数时、会有 “前置状态” 要求，于是这就决定了搜索的顺序。（有时候特殊设计的规则集 \mathcal{R} 也会使得特定策略（顺序）的枚举更方便；但这个限制不如目标那么强。）值得一提的是，存在策略（顺序）要求的搜索算法，某种程度上（形式上）也可以就认为是一种简单的 dp。

（补充阅读：ref. 3.1. 关于多重集、幂集的定义。）

（补充阅读：ref. 3.2. 关于元组/函数的定义。）

1.2. 优化搜索（枚举）

1.2.1. 无优化

确定 \mathcal{K}、确定 \mathcal{V}，同时确定 s 的规则集 \mathcal{R}（“共性”）。

（\mathcal{R} 在题干中通常表现为某种限制。比如，\mathcal{K}=1, \mathcal{V}=\{\{A\mid A\subseteq B\}\}，要求 s_1 至少包含 3 个元素，对应 \rho(s)=[|s_1|=3]；或者，\mathcal{K}=1, \mathcal{V}=\{\{A\mid A\subseteq B\}\}，要求指定的元素 x\in B 不能和另一指定的元素 y\in B 同时出现在 s_1 中，对应\rho(s)=1-[x\in s_1\land y\in s_1]；等等。）

然后直接进行对集合 \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i} 内元素的枚举，从而遍历到 \mathcal{S} 每个元素至少一次。

具体来说。可以类似直接从左往右逐个填、从左往右枚举元组的每一个空位的每一种情况；这里直接给出一个基于递归的方法：

const int K =...;
const vector<set<T> > V(K, ...);
vector<T> x(K, null);

void dfs(int i){
    if(i == K){
        ...
    }
    else{
        for(T a: V[i]){
            x[i] =a;
            dfs(i+1);
            x[i] =null;
        }
    }
}

为了方便，这里认为 vector 的每个位置的类型可以不同；T 是指任意类型。

需要指出，这个递归也可以展开为循环：递归/循环的层数就是元组的长度 \mathcal{K}。

1.2.1.1. 关于嵌套递归的枚举元组

如果提前计算 V[i] 即 \mathcal{V}_i 比较麻烦，也可以采用嵌套递归：将 for(T a: V[i]) 替换为某种遍历 \mathcal{V}_i 的（递归）算法，并且在每次得到一个 \mathcal{V}_i 成员的时候把控制流交给 dfs(i+1)。

例如对于 \mathcal{V}=\{\{1, 2, \cdots, N\}, \{A\mid A\subseteq \{1, 2, \cdots, M\}\}\}，元组第二个空位是在枚举子集；我们可以不预处理所有子集（因为会很占空间）、而是如此实现：

const int K =2;
int x1 =0;
set<int> x2 =set<int>();
int cnt_ans =0;

int N =..., M =...;

void calcV2(int i, int j){
    if(j > M){
        dfs(i+1); //
    }
    else{
        x2.insert(j);
        calcV2(i, j+1);
        x2.erase(j);
        calcV2(i, j+1);
    }
}

void dfs(int i){
    if(i == K){
        printf("(%d, {", x1);
        for(int it: x2)
            printf("%d ", it);
        puts("})");
        cnt_ans++;
        return;
    }
    else{
        if(i == 0){
            for(int a =1; a <= N; ++a){ // V_1=[1, N]
                x1 =a;
                dfs(i+1);
                x1 =0;
            }
        }
        else if(i == 1){
            calcV2(i, 1);
        }
    }
}

int main(){
    dfs(0);
}

1.2.2. 优化其一

通常是根据规则集 \mathcal{R} 优化枚举元组的过程（即“把这个 dfs 剪枝”）。具体地讲，这里的规则的形式其实有很多、无法一概而论，但基本都是对状态的某种限制，最终是能够缩减状态空间 \mathcal{S} 的大小的。

（补充阅读. ref. 3.3. A^n, A^* 符号定义（笛卡尔积ver）。）

例如，为有向图 \{V, E\} 枚举路径，有 \mathcal{V}=\{V^*\}，但是由于 E 的约束，我们其实有规则 \rho(s)=\left[\;\forall 1\leq i<|s_1|: (s_{1, i}, s_{1, i+1})\in E\;\right] （简单来说就是路径相邻节点必须存在边连接），于是就可以借此排除很多状态。（不过注意，这里枚举的实际上并非是简单路径；如果想要枚举简单路径还要加上节点不重复出现的限制。）

1.2.3. 优化其二

通常是根据统计目标、以及对状态的限制规则，来优化。通常此时我们是在提炼 \mathcal{S} 子集的共性，从而构造 \mathcal{S}, \mathcal{V} 的一个划分，接着转而遍历/枚举这个划分从而指数级优化时间复杂度。

例如求 \{1, 2, 3, 4\} 的所有子集，但是有规则 \rho(s)=[\;(1\in s_1\lrArr 2\in s_1) \land (3\in s_1 \lrArr 4\in s_1)\;]（即要求 1, 2 or 3, 4 必须同时出现）。原本的值空间是 \mathcal{V} =\{\{A\mid A\subseteq\{1, 2, 3, 4\}\}\}，而根据规则我们可以得到优化后的、结果等价的、值空间 \mathcal{V} =\{\{A\mid A\subseteq\{(1, 2), (3, 4)\}\}\}，从而极大缩小 \prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i} 的大小。

~~另外，结合一些问题（通常是 dp 问题...）会有的目标函数 f:\mathcal{S}\to Y，再稍微拓展，即可进入 dp 的领域。~~

1.3. 优化搜索（一般）

和上一节最大的不同是，这里指的搜索都是有策略/顺序要求的。其核心不同在于，无策略要求的、可以认为是枚举元组、可以认为是在 2^n 满二叉树上 dfs；而有策略要求的、可以认为是 f 为递归函数的、可以认为是在以拓扑序遍历某 DAG（递归函数 f 的依赖关系图）。

1.3.1. 无优化

暂时略。

1.3.2. 优化其一

其实就是指一般理解下的 "搜索剪枝"，也是根据规则 \mathcal{R} 来的，在 “移动”/“递归” 到新状态时根据 \mathcal{R} 进行剪枝（不移动）。

1.3.3 优化其二

在此时已经完全是 dp 领域了，请见 dp 章节。

1.4. *关于子集（幂集）枚举

（补充阅读：ref. 3.1. 关于多重集、幂集的定义。）

出于一般化，这里直接讨论 “多重集子集”（是多重集修饰子集）意义下的/“多重集意义” 下的幂集；但要注意，此时即使原集合为有限集，其幂集也为无限集，因此通常我们都会限制枚举的子集的最大大小，记为 N。

1.4.1. 朴素

对于求 B 的 “多重集意义” 下的幂集 \mathcal{M}(B)=\left\{\mu: B \to \mathbb{N}\;\mid\;|\{a\in B \mid \mu(a)\neq 0\}|<\infty\right\}，我们可以先把 A\in \mathcal{M}(B) “视为元组”枚举、记录出现情况，然后再去重。

具体来说，比如可以：先枚举 A 大小 1 ~ N ；然后先把 A 视为元组，于是就可以从左到右逐个给元组的空位填空枚举，例如 |A|=2, B =\{x, y, z\}，即我们要给元组 (\underline{}, \underline{}) 填空，那么就得到 (x, x), (x, y), (x, z), (y, x), (y, y), (y, z), (z, x), (z, y), (z, z)；最后因为集合无序，我们还得去重（可以开 vis 数组之类处理；重复的例子比如说 (x, y), (y, x)）。

1.4.2. 优化

要确定一个子集 A 集合内的次序。

形式化地说，我们要构造一个 B 上的全序关系 \leq，从而为每个 A 确定一个唯一的集合内顺序；接着就可以建立一个双射 \operatorname{sort}:\mathcal{M}( B)\to B^*，具体来说 sort 的定义是：

（补充阅读：ref. 3.3. A^n, A^* 符号定义（笛卡尔积ver）。）

给定一个全序关系 \leq 在集合 B 上，以及一个有限多重集 A \subseteq_{\text{mult}} B（即 A 可表示为函数 \mu_s: B \to \mathbb{N}，且仅有限个 a \in B 满足 \mu_s(a) > 0），定义函数 \operatorname{sort}: \mathcal{M}(B) \to B^*（其中 \mathcal{M}(B) 是 B 上所有有限多重集的集合、先前已经定义过，B^* 是 B 上所有有限元组的集合、即 B^*:=\bigcup_{n\in \mathbb{N}} B^n（其中 B^n=\{(a_1, a_2, \cdots, a_n)|a_i\in B\}））如下：

\operatorname{sort}(s) = (a_1, a_2, \ldots, a_n)
其中 n = \sum_{a \in \mathcal{V}} \mu_s(a) 为 s 中元素的总个数，且该元组满足：

对每个 a \in B，a 在元组中出现的次数恰好等于 \mu_s(a)；

元组中的元素关于全序 \leq 是非递减的，即 a_1 \leq a_2 \leq \cdots \leq a_n。

由全序的性质和有限性可知，这样的元组存在且唯一。

于是我们就可以转而枚举 B^* 即可，此时已经是复杂度下限了。

例如，对 B =\{x, y, z\} 我们可以规定 x\leq y, y\leq z，这样枚举的时候我们强制要求相邻下一个空位填的元素 \geq 相邻上一个填的元素（如，对于 (y, \underline{/})，下一个空位就只能填 y or z 而不能填 x）；最后我们枚举到的就只有 (x, x), (x, y), (x, z), (y, y), (y, z), (z, z) 。

1.5. 关于“有序状态/序列”的枚举

建议直接视为在枚举元组。

相关的详细解释暂时略。

1.6. 关于变长元组的枚举

对于变长元组的枚举（如图路径、区间等）；变长元组可以视为填所有元组中、长度最长的那个元组、的空，不过允许后面留空（或者可以把 “留空” 视为填了一个特殊元素）。

相关的详细解释暂时略。

2. Dp（动态规划）

2.1. Dp（动态规划）的定义

（前大半部分基本完全和搜索相同。）

状态空间（解空间）\mathcal{S} 是一个元组的集合，且包含的所有元组长度都为给定值 \mathcal{K}（状态维度）；状态 s\in \mathcal{S} 是一个元组；值空间 \mathcal{V}=(\mathcal{V}_1, \mathcal{V}_2, \cdots, \mathcal{V}_\mathcal{K}) 是一系列集合，\mathcal{V}_i 包含 s 元组中第 i 个位置的所有可能取值（从实际应用出发，我们默认 \mathcal{V}_i 一定是有限集）、即 \mathcal{V_i}=\{a \mid \exist s\in \mathcal{S}, a=s_i\}。

而搜索是指以特定策略（顺序）进行枚举；当无序/没有特定顺序时也可直接称为枚举。搜索的顺序往往和目标强相关；例如，目标函数 f(s) 的定义可能是递归的（如 f(i)=f(i-1)+g(i)），从而在计算某一状态的统计目的函数时、会有前置状态要求，于是这就决定了搜索的顺序。（有时候特殊设计的规则集 \mathcal{R} 也会使得特定策略（顺序）的枚举更方便；但这个限制不如目标那么强。）值得一提的是，存在策略（顺序）要求的搜索算法，某种程度上（形式上）也可以就认为是一种简单的 dp。

而 Dp（动态规划）是一种对状态空间 \mathcal{S}、及其上面的 f，进行分析、提取共性、再抽象，从而优化算法总复杂度的思维范式。经过 dp 范式分析后，得到的最终算法从形式上也可认为是一个搜索算法。

（不过如果思路足够巧妙，有时候不通过 dp 范式，也能构造出不错的（搜索）算法，并且可能本质和别人用 dp 范式优化了几轮的算法完全一样。但掌握 dp 范式能让读者不受注意力限制，总是能够构造出比较优秀的算法。~~（题外话，对于这种现象，总的来说我个人持接近帕拉图主义的观点。）~~）

2.2. 方法概述

2.2.1. 其一，预处理/状态抽象

转换问题、形式化问题，提炼出状态空间 \mathcal{S}，状态维度 \mathcal{K}，值空间 \mathcal{V}，目标函数 f(s):\mathcal{S}\to Y。

构造时，最好可以保证 f(s) 可以仅由自变量 s 计算出（即不是递归函数；即无需其它 s'\in\mathcal{S}, s'\not=s 来计算值；形式化的话，即对当前 \mathcal{S} 的每一个 s 满足 \exist ! c\in Y, \forall \mathcal{S}, s\in \mathcal{S}: f(s)=c（注意式子里我们是固定 s、变化 \mathcal{S}）），这样会让后续设计状态转移更加容易些。

（为什么说 “最好”：是因为理论上也许确实对任何问题都能设计出不递归的 f，但从那样的 f 出发进行优化，往往会因为证明链条/思维链条过长、过复杂而没有实际价值。）

通常，我们也要尽可能减小状态维度 \mathcal{K}（也是在减少状态空间 \mathcal{S} 的大小、\prod\limits_{i=1}^{\mathcal{K}}{V_i} 的大小、f “形参”/自变量的数量）。

本质上这一步其实就是在构造一个暴力搜索的思路。

2.2.2. 其二，设计状态转移

接下来我们要构造一系列映射规则 \phi_j: \mathcal{S} \to \mathcal{V}_j', 1\leq j\leq \mathcal{K}'（通常是一个“特征映射”），从而从原状态元组的集合（原状态空间） \mathcal{S}，得到一个简化的新状态元组的集合（新状态空间） \mathcal{S}'=\{s'=(\phi_1(s), \cdots, \phi_{\mathcal{K}'}(s))\mid s\in\mathcal{S}\}，简写为 \mathcal{S}'=\phi(\mathcal{S})。

（补充阅读：ref. 3.5. 像集、原像的定义。）

可以发现新集合的每个元素 s'=(\phi_1(s), \cdots, \phi_{\mathcal{K}'}(s))（简写为 s'=\phi(s)）都对应着原集合的某些状态。形式化地讲，定义原像 \phi^{-1}(s') = \{\, s \in \mathcal{S} \mid \phi_j(s) = s', 1\leq j\leq \mathcal{K}' \,\}，是指所有映射到 s' 的输入值 s 构成的集合。另外，从设计状态转移思路指导的角度来讲，s'=\phi(s) 也可以视为是提取出的原状态的 “等价类”，且最终算法遍历/搜索的就是这些等价类。（另外，如此提取后的等价类还隐含以下性质：设两个等价类 A, B，再设 \{(a, b)\mid a\in A, b\in B\} 表示所有可能的分别被 A, B 对应的原状态、两两之间产生的 f 的 “转移关系”；固定 A, B，这些 “转移关系” 之间往往都会存在许多相似性，且对任意 A, B 都满足这个结论。正是这 “相似性” 才让后文构造定义完备封闭的 f' 变得有可能。）

（补充阅读：ref. 3.6. 覆盖、划分的定义。）

最重要的，得到的新状态空间 \mathcal{S}' 必须满足：

（注意：其中 1. 是对计数类目标特有的。）

注意到原像集合 \mathcal{I}=\{\phi^{-1}(s')\mid s'\in \mathcal{S}'\} 一定构成了 \mathcal{S'} 的一个覆盖。对于计数目标，通常我们还要求覆盖集满足 \exist s': \phi^{-1}(s') = \mathcal{S}（即存在一个元素等于 \mathcal{S}；其实就是下一个条件的弱化/特定情况）、或 \exist \mathcal{Q}\subseteq \mathcal{S}': \left(\bigcup\limits_{q\in \mathcal{Q}}\phi^{-1}(q) = \mathcal{S}\right) \;\land\; \left(\forall q\in \mathcal{Q}, p\in \mathcal{Q}, q\not=p: \phi^{-1}(q)\cap\phi^{-1}(p)=\empty\right)（即存在多个不交元素的并是 \mathcal{S}）。
要求可以 “聚合” f 为自变量仅包含 s' 的函数；具体来说，要求可以构造 f'(s'):\mathcal{S}' \to Y=g(\{f(s)\mid s\in\phi^{-1}(s')\})，这里 g 根据目标的不同、可以是对 f(s) 求极值（如 g(\{f(s)\mid s\in\phi^{-1}(s')\})=\max\limits_{s\in\phi^{-1}(s')}(f(s))）、也可以是对 f(s) 求和（如 g(\{f(s)\mid s\in\phi^{-1}(s')\})=\sum\limits_{s\in\phi^{-1}(s')}(f(s))）、也可以是其它对 f(s) 的统计（任意关于 \{f(s)\mid s\in\phi^{-1}(s')\} 的函数）。同时，这里的 f' 的定义可以是递归的，并且通常就自然地会是递归的。值得一提的是，这里 f' 的递归性质就决定了动态规划的 “转移顺序”。（还有一点也值得一提，就是递归化有时候也顺带优化了每个具体的 f'(x') 的值的计算。）
通常会尽可能减小 \mathcal{S}' 的大小 |\mathcal{S}'|。不过，在一些情况下，为了在后续优化有更好的性质，可能也不会取最小的那个 \mathcal{S}'。

关于 1.，值得一提的是，我们得到的覆盖集 \mathcal{I}=\{\phi^{-1}(s')\mid s'\in \mathcal{S}'\}，往往要么是 \mathcal{S} 的一个划分；要么是一个“嵌套覆盖”，具体来说即要求 \forall s'_1 \in \mathcal{S}', s'_2 \in \mathcal{S}': \left(\phi^{-1}(s'_1) \cap \phi^{-1}(s'_2)=\empty\right) \lor \left(\phi^{-1}(s'_1)\subseteq \phi^{-1}(s'_2)\right) \lor \left(\phi^{-1}(s'_2) \subseteq \phi^{-1}(s'_1)\right)（交集为空或者一方被另一方包含）。（划分的例子有：简单路径，图结点，...；“嵌套覆盖” 的例子有：区间，树子树，DAG，...）。不满足以上两个条件，单纯 “只是” 一个覆盖的情况很少见（一时半会没想到例子... 不过至少从本文的描述框架来说是自然地允许这种情况的）。

得指出，所谓常听到的 “转移之间是存在前置要求的关系的”/“某个转移必须在另一个转移前完成”，其实就是来源于 f' 的递归定义和其递归性质。

最后，在这一步构造出的 \mathcal{S}', f' 深刻影响最终 dp 算法的复杂度，并且直接决定了当前思路的 “暴力 dp” 算法的复杂度（一般来说，例如，如果有 \mathcal{S}' 的 “维度” 为 \mathcal{K}'、其中 \mathcal{K}' 即为上文提到的，那么暴力 dp 的复杂度就不低于 O(n^{\mathcal{K}'}) 其中 n 是某个题目相关量（如数据范围））。

（总的来说，设计状态转移的目标，就是依据 \mathcal{S} 的可聚合性质（如可加性、可比较性）与 f 的计算性质来提取等价类，要求只关心每个等价类中所有原状态的 聚合信息（如最值、和、积等）、并且这些聚合信息在新状态之间的 “传递“ 是封闭的，从而缩减 |\mathcal{S}'| 优化计算；另外，覆盖集 \mathcal{I} 往往有的划分或嵌套特性，其实只是这种等价类的常见表现形式（的“性质体现”）。）

（另外，“其二” 这一步，或者说整个 dp 的构造方法，也是有可能在一道题中被 “多次使用” 的，通常出现在需要对题目进行多次 问题转化、或状态设计十分隐晦的时候。）

2.3. 一般性优化

总共可大致分为四大类：

2.3.1. 甲，数据结构优化

数据结构优化主要是优化 f' （或“f”）的计算复杂度，且和 Dp 的具体转移结构关联较大；具体还是要看题目。

例如。

更多的例子暂时略。

这类问题再稍微拓展即可到 “动态动态规划” 的领域（即带修改、要求修改后快速计算答案的动态规划问题）。

2.3.2. 乙，分析方法优化

包括一整个凸优化领域的各种方法...本节待完善...

考虑到凸优化本身已经有及其完善的理论模型和体系；这一小节应该是未来续写的重点内容...

（虽然笔者之前也整理过 dp 和凸优化交叉领域的 blog（可能需要国际网络环境）；但现在来看果然感觉之前写得实在是有些太稚嫩了，文章符号约定也做得不是很好。）

（另外，姑且值得一提的是，部分分析方法优化，也能简化状态空间（例如 wqs二分、部分单调性优化）；而不同的地方笔者感觉可能在于，“2.2.2. 其二，设计状态转移” 更聚焦于问题性质/“组合性质”，而分析方法优化的 “纯数”/分析浓度更大。）

2.3.3. 丙，代数方法优化

目前能想到的有 矩阵快速幂 和 生成函数。

（虽然生成函数转化后可能也还要用分析的方式来做；但笔者感觉首先第一步、转化成生成函数的这一步，代数含量已经高到值得专门拿出来讨论了。）

A. 矩阵快速幂

I. 基本流程

矩阵快速幂优化适用于 “线性递推形式” 的动态规划，即状态转移方程可以表示为 "状态向量" 的线性变换。

其大致流程如下：

I.1. 转换问题

先构造 dp 满足 \mathcal{K}'=2, \mathcal{V}'=\{\mathcal{V}_1'=\{1, 2, \cdots, N\}, \mathcal{V}_{2}'=\{1, 2, \cdots, d\}\}, \mathcal{S}'=\{1, 2, \cdots, N\}\times \{1, 2, \cdots, d\}，并且想办法把 f'(s') 构造成形如 f'(s')=f'(k, i)=\sum\limits_{1\leq j\leq d}\left(a_{ij}\cdot f'(k-1, j)\right) 的形式（当 d=1 时，这也可以称为是常系数齐次线性递推），且目标是计算 f'(n, i), 1\leq i\leq d（或者说满足 \bigcup\limits_{i\in I}\phi^{-1}((n, i))=\mathcal{S}、其中 I\subseteq \mathcal{V}_2'），最后同时还要求 f'(1, i), 1\leq i\leq d 可以轻松地计算。

I.2. 构造转移矩阵

（补充阅读：ref. 3.7. 集合论中的向量、矩阵、A^n, A^{n\times n}。）

（注意，从此开始，整个 "A. 矩阵快速幂" 章节的 A^n, A^{n\times n} 记号都采用的是 集合论定义，而非之前默认采用的 “A^n, A^* 符号定义（笛卡尔积ver）” 中的定义。）

考虑设计向量：

\mathbf{f}_k = \big( f'(k, 1), f'(k, 2), \dots, f'(k, d) \big)^\top \in Y^d

根据状态转移方程我们能得到递推关系：

\mathbf{f}_{k+1} = \mathbf{T} \cdot \mathbf{f}_k

其中 \mathbf{T} \in Y^{d \times d} 为 “转移矩阵”，是一个矩阵，其具体项为：

\mathbf{T} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1d} \\ a_{21} & a_{22} & \cdots & a_{2d} \\ \vdots & \vdots & \ddots & \vdots \\ a_{d1} & a_{d2} & \cdots & a_{dd} \end{pmatrix}

I.3. 矩阵快速幂计算

由递推关系得：

\mathbf{f}_n = \mathbf{T}^{n-1} \cdot \mathbf{f}_1

其中 \mathbf{f}_1 为初始状态向量，是可以快速计算的。接着，通过快速幂计算 \mathbf{T}^{n-1} 即可得到答案，复杂度可以做到 O(d^3 \cdot \log n)（而直接递推是 O(d^2\cdot n )）。

I.4 注意事项

一般来说，要求状态空间维度 \mathcal{K}'=d 较小，否则矩阵乘法开销过大。

~~对于 “维度” 更高的（\mathcal{K}' 更大的）dp，虽然也存在拓展的可能性，但是大抵要采用更高维度的矩阵、递推式会非常复杂。~~

II. 一些转换问题时的技巧

如题。主要是做一些形式/逻辑上的辨明；实际实现时其实也 “都是” 写出一个初始状态向量再写出一个转移矩阵，也许对状态的解释稍作改动就可以不需要这些技巧了。

II.1. 常系数线性齐次递推（d=1 但是转移涉及比 k-1 更远的项）

对于常系数线性齐次递推，即，可以构造 dp 满足 \mathcal{K}'=1, \mathcal{V}'=\{\mathcal{V}_1'=\{1, 2, \cdots, N\}\}, \mathcal{S}'=\{1, 2, \cdots, N\}，并且可以把 f'(s') 构造成形如 f'(s')=f'(k)=\sum\limits_{1\leq i\leq r}\left(a_{i}\cdot f'(k-i)\right) 的形式，且目标是计算 f'(n)（或者说满足 \phi^{-1}((n))=\mathcal{S}），最后同时还要求 f'(k), 1\leq k\leq r 可以轻松地计算。

考虑展开，设计向量：

\mathbf{f}_k = \big( f'(k), f'(k+1), \dots, f'(k+r-1) \big)^\top \in Y^r

根据状态转移方程我们能得到递推关系：

\mathbf{f}_{k+1} = \mathbf{T} \cdot \mathbf{f}_k

其中 \mathbf{T} \in Y^{r \times r} 为 “转移矩阵”，是一个矩阵，其具体项为：

\mathbf{T} = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ a_r & a_{r-1} & a_{r-2} & \cdots & a_1 \end{pmatrix}.

然后接下来要做的就很显然了，已知 \mathbf{f}_1 计算 \mathbf{f}_{n-r+1} = \mathbf{T}^{n-r} \cdot \mathbf{f}_1 即可，答案就在 \mathbf{f}_{n-r+1} 的最后一行即 (\mathbf{f}_{n-r+1})_r（或写作 \mathbf{f}_{n-r+1}[r]）。

II.2. 对上一节的拓展（d>1 且转移涉及比 k-1 更远的项）

即，可以构造 dp 满足 \mathcal{K}'=2, \mathcal{V}'=\{\mathcal{V}_1'=\{1, 2, \cdots, N\}, \mathcal{V}_{2}'=\{1, 2, \cdots, d\}\}, \mathcal{S}'=\{1, 2, \cdots, N\}\times \{1, 2, \cdots, d\}，并且可以把 f'(s') 构造成形如 f'(s')=f'(k, i)=\sum\limits_{1\leq p\leq r}\sum\limits_{1\leq j\leq d}\left(a_{ijp}\cdot f'(k-p, j)\right) 的形式，且目标是计算 f'(n, i), 1\leq i\leq d（或者说满足 \bigcup\limits_{i\in I}\phi^{-1}((n, i))=\mathcal{S}、其中 I\subseteq \mathcal{V}_2'），最后同时还要求 f'(k, i), 1\leq k\leq r, 1\leq i\leq d 可以轻松地计算。

考虑展开，设计向量：

\mathbf{f}_k = \big( f'(k, 1), f'(k, 2), \dots, f'(k, d), f'(k+1, 1), f'(k+1, 2) \dots, f'(k+r-1, d) \big)^\top \in Y^{(dr)}

根据状态转移方程我们能得到递推关系：

\mathbf{f}_{k+1} = \mathbf{T} \cdot \mathbf{f}_k

其中 \mathbf{T} \in Y^{(dr) \times (dr)} 为 “转移矩阵”，是一个矩阵，其分块形式为：

\mathbf{T} = \begin{pmatrix} \mathbf{0} & \mathbf{I} & \mathbf{0} & \cdots & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{I} & \cdots & \mathbf{0} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{I} \\ \mathbf{A}_r & \mathbf{A}_{r-1} & \mathbf{A}_{r-2} & \cdots & \mathbf{A}_1 \end{pmatrix}

其中：

(\mathbf{A}_p)_{ij} = a_{ijp}.

然后接下来要做的就很显然了，已知 \mathbf{f}_1 计算 \mathbf{f}_{n-r+1} = \mathbf{T}^{n-r} \cdot \mathbf{f}_1 即可，答案就在 \mathbf{f}_{n-r+1} 的最后 d 行即 (\mathbf{f}_{n-r+1})_{dr-d+1:dr}（或写作 \mathbf{f}_{n-r+1}[dr-d+1:dr]）。

注意，使用此种技巧时一定要注意向量的长度（也即转移矩阵的维度）；如果展开后发现向量过长的话会因为矩阵乘法复杂度过高而导致该方法不可行。

II.3. 常系数非齐次线性递推（仅限多了一个常数项）

若转移包含常数项，即，可以构造 dp 满足 \mathcal{K}'=1, \mathcal{V}'=\{\mathcal{V}_1'=\{1, 2, \cdots, N\}\}, \mathcal{S}'=\{1, 2, \cdots, N\}，并且可以把 f'(s') 构造成形如 f'(s')=f'(k)=\left(\sum\limits_{1\leq i\leq r}\left(a_{i}\cdot f'(k-i)\right)\right)+b 的形式，且目标是计算 f'(n)（或者说满足 \phi^{-1}((n))=\mathcal{S}），最后同时还要求 f'(k), 1\leq k\leq r 可以轻松地计算。

考虑设计向量：

\mathbf{f}_k = \big( f'(k), f'(k+1), \dots, f'(k+r-1), 1\big)^\top \in Y^{r+1}

根据状态转移方程我们能得到递推关系：

\mathbf{f}_{k+1} = \mathbf{T} \cdot \mathbf{f}_k

其中 \mathbf{T} \in Y^{(r+1) \times (r+1)} 为 “转移矩阵”，是一个矩阵，其具体项为：

\mathbf{T} = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ a_r & a_{r-1} & a_{r-2} & \cdots & a_1 & b \\ 0 & 0 & 0 & \cdots & 0 & 1 \end{pmatrix}.

然后接下来要做的就很显然了，已知 \mathbf{f}_1 计算 \mathbf{f}_{n-r+1} = \mathbf{T}^{n-r} \cdot \mathbf{f}_1 即可，答案就在 \mathbf{f}_{n-r+1} 的倒数第二行即 (\mathbf{f}_{n-r+1})_r（或写作 \mathbf{f}_{n-r+1}[r]）。

II.4. 对上一节的拓展（d>1，且多了一个常数项；且转移涉及比 k-1 更远的项）

~~具体写起来其实构造思路完全一样（展开为一维向量），会和 II.2、II.3 非常相似，但是也会更加加倍地长...... :(~~

即，可以构造 dp 满足 \mathcal{K}'=2, \mathcal{V}'=\{\mathcal{V}_1'=\{1, 2, \cdots, N\}, \mathcal{V}_{2}'=\{1, 2, \cdots, d\}\}, \mathcal{S}'=\{1, 2, \cdots, N\}\times \{1, 2, \cdots, d\}，并且可以把 f'(s') 构造成形如 f'(s')=f'(k, i)=\left(\sum\limits_{1\leq p\leq r}\sum\limits_{1\leq j\leq d}\left(a_{ijp}\cdot f'(k-p, j)\right)\right)+b 的形式，且目标是计算 f'(n, i), 1\leq i\leq d（或者说满足 \bigcup\limits_{i\in I}\phi^{-1}((n, i))=\mathcal{S}、其中 I\subseteq \mathcal{V}_2'），最后同时还要求 f'(k, i), 1\leq k\leq r, 1\leq i\leq d 可以轻松地计算。

考虑展开，设计向量：

\mathbf{f}_k = \big( f'(k, 1), f'(k, 2), \dots, f'(k, d), f'(k+1, 1), f'(k+1, 2) \dots, f'(k+r-1, d), 1 \big)^\top \in Y^{(dr+1)}

根据状态转移方程我们能得到递推关系：

\mathbf{f}_{k+1} = \mathbf{T} \cdot \mathbf{f}_k

其中 \mathbf{T} \in Y^{(dr+1) \times (dr+1)} 为 “转移矩阵”，是一个矩阵，其分块形式为：

\mathbf{T} = \begin{pmatrix} \mathbf{0} & \mathbf{I} & \mathbf{0} & \cdots & \mathbf{0} & 0\\ \mathbf{0} & \mathbf{0} & \mathbf{I} & \cdots & \mathbf{0} & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{I} & 0\\ \mathbf{A}_r & \mathbf{A}_{r-1} & \mathbf{A}_{r-2} & \cdots & \mathbf{A}_1 & \mathbf{b} \\ \mathbf{0'} & \mathbf{0'} & \mathbf{0'} & \cdots & \mathbf{0'} & 1 \end{pmatrix}

其中：

$$ (\mathbf{A}_p)_{ij} = a_{ijp}. $$

然后接下来要做的就很显然了，已知 \mathbf{f}_1 计算 \mathbf{f}_{n-r+1} = \mathbf{T}^{n-r} \cdot \mathbf{f}_1 即可，答案就在 \mathbf{f}_{n-r+1} 的倒数第 2:d+1 行即 (\mathbf{f}_{n-r+1})_{dr-d+1:dr}（或写作 \mathbf{f}_{n-r+1}[dr-d+1:dr]）。

III. 示例：Fibonacci 数列

求 Fibonacci 数列第 n 项。属于 II.1. 那类。

构造 dp 得 \mathcal{K}'=1, \mathcal{V}'=\{\mathcal{V}_1'=\{1, 2, \cdots, n-1\}\}, \mathcal{S}'=\{1, 2, \cdots, n-1\}，和 f'(s')=f'(k)=\sum\limits_{1\leq i\leq 2}\left(f'(k-i)\right) 的形式，目标则是计算 f'(n)，且有 f'(1)=f'(2)=1。

考虑展开，设计向量：

\mathbf{f}_k = \big( f'(k), f'(k+1)\big)^\top \in Y^2

根据状态转移方程我们能得到递推关系：

\mathbf{f}_{k+1} = \mathbf{T} \cdot \mathbf{f}_k

其中 \mathbf{T} \in Y^{2 \times 2} 为 “转移矩阵”，是一个矩阵，其具体项为：

\mathbf{T} = \begin{pmatrix} 0 & 1\\ 1 & 1\\ \end{pmatrix}.

然后接下来要做的就很显然了，已知 \mathbf{f}_1 计算 \mathbf{f}_{n-1} = \mathbf{T}^{n-2} \cdot \mathbf{f}_1 即可，答案就在 \mathbf{f}_{n-1} 的最后一行即 (\mathbf{f}_{n-1})_2（或写作 \mathbf{f}_{n-1}[2]）。

B. 生成函数

一般来说，这种类型的题目往往是先确定 dp 式子（\mathcal{S}', f'），然后单纯地将 f' 视为一个递推式，来套用生成函数、求通项公式，从而进行优化；又或者，是在计算具体每个 f'(s') 的值的时候想要优化该计算过程中的一些组合数项，从而使用了生成函数。

总之，这类问题中生成函数和 dp 环节并不存在耦合。不过，得指出的是，部分 dp 解决的问题本身就完全是组合问题，因此对这部分 dp 从一开始就也完全可以用生成函数做。

详细解析因为会涉及比较多得生成函数的知识，笔者也还了解的比较少，就暂时先不展开了...

2.3.4. 丁，其它优化

如：容斥 dp，感觉可以算作优化也可以不算作（因为有些题目不用容斥几乎完全不可做）；具体请见后文章节。

又如：cdq 分治。这种优化方法对 Dp 的具体转移结构要求比较高；一般要求必须能把转移的贡献抽象成某种多维前缀和统计的形式。

2.4. 容斥 dp

回想 “其二，设计状态转移” 的 1.：对于计数类目标，如果我们构造出的 \phi, \mathcal{S'}, f' 不满足 \exist s': \phi^{-1}(s') = \mathcal{S}（即存在一个元素等于 \mathcal{S}；其实就是下一个条件的弱化/特定情况）、和 \exist \mathcal{Q}\subseteq \mathcal{S}': \left(\bigcup\limits_{q\in \mathcal{Q}}\phi^{-1}(q) = \mathcal{S}\right) \; \land \; \left(\forall q\in \mathcal{Q}, p\in \mathcal{Q}, q\not=p: \phi^{-1}(q)\cap\phi^{-1}(p)=\empty\right)（即存在多个不交元素的并是 \mathcal{S}）；就会发现，我们无法简单地累加状态答案（选取特定的 f'(s') 累加）来得到总答案。

考虑容斥规则 |A\cup B|=|A|+|B|-|A\cap B| \rArr |A\cap B|=|A|+|B|-|A\cup B|。更一般的，设 N 个集合 A_1, A_2, \cdots, A_N，若要计算 \left| \bigcap\limits_{1\leq i\leq N} A_i\right|，我们有 \left| \bigcap\limits_{1\leq i\leq N} A_i\right|=\sum\limits_{I\subseteq \{1, 2, \cdots, N\}}\left(\left|\bigcup\limits_{i\in I}A_i\right|\cdot (-1)^{|I|+1}\right)。

容斥 dp 其实就是一个满足如下要求的 dp：

为（~~发音第二声~~）计数类目标。
目标形式可以被表述为 \left| \bigcap\limits_{1\leq i\leq N} A_i\right| 。
对要解决的问题，无法/很难设计出能直接得到 \left| \bigcap\limits_{1\leq i\leq N} A_i\right| 答案的 dp。
但对要解决的问题，对每一个 I\subseteq \{1, 2, \cdots, N\} 都可以设计出能得到 \left|\bigcup\limits_{i\in I}A_i\right| 答案的 dp。

容斥 dp 的流程：第一部分是分析确定容斥目标、围绕此设计状态和明确容斥式子；第二部分是和一般的计数 dp 完全一致的；第三部分是合并答案，且此时要使用容斥规则。

（其实容斥 dp 中，容斥部分和 dp 部分的耦合性也不是很强。）

有一个经典例题、建议结合它理解。

3. 附录：前置知识 & 一些符号定义

3.1. *关于多重集、幂集的定义

从标准集合论的角度来看，我们可以把一个多重集 M 视为一个函数 \mu_M: U \to \mathbb{N} 且满足 |\{a\in U \mid \mu(a)\neq 0\}|<\infty（为了讨论方便，我们这里限定了 \mu_M 为某种意义下的有限集；如果要研究无限的话也可以不限定），这里 U 是 M 中所有可能出现的元素的集合。

而一般集合可以认为是多重集的特例：\mu_M: U\to \{0, 1\} 且满足 |\{a\in U \mid \mu(a)\neq 0\}|<\infty。

定义 “多重集意义” 下的幂集：$\mathcal{M}(U)=\left\{\mu: U \to \mathbb{N}\;\mid\;|\{a\in U \mid \mu(a)\neq 0\}|<\infty\right\}$。 ## 3.2. 关于元组/函数的定义元组有一个最经典的定义：$(a_1, a_2, \cdots, a_n):=\{\{a_1\}, \{a_1, a_2\}, \cdots, \{a_1, a_2, \cdots, a_n\}\}$。接着还有二元关系的定义：二元关系 $R:A\to B$ 是 $A\times B$ 的任意子集 $R\subseteq A\times B$。而（单值）函数可以基于二元关系定义：$f:X\to Y$ 是一种二元关系（即 $f\subseteq X\times Y$），且满足 $\forall x\in X, \exist! y\in Y : (x, y)\in f$ 。 ## 3.3. $A^n, A^*$ 符号定义（笛卡尔积ver） $A^n=A\times\cdots_{n-2}\times A=\{(a_1, a_2, \cdots, a_n)|a_i\in A\}$。 $A^*:=\bigcup_{n\in \mathbb{N}} A^n$。关于 $A^n$ 还有一个集合论中更泛用的定义，可以见 “## 集合论中的向量、矩阵、$A^n, A^{n\times n}$”。 ## 3.4. $\prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}$ 符号定义 $\prod\limits_{i=1}^{\mathcal{K}}{\mathcal{V}_i}=\mathcal{V}_1\times \mathcal{V}_2\times\cdots\times \mathcal{V}_\mathcal{K}$。 ## 3.5. 像集、原像的定义 ### 3.5.1. 像集（Image） **定义**：给定映射 $h: \mathcal{S} \to \mathcal{S}'$，像集是指所有可能的输出值构成的集合，即： $$ \operatorname{Im}(h) = \{\, h(s) \mid s \in \mathcal{S} \,\}. $$ **通俗理解**：像集就是“映射能产生的所有结果”。例如，若原元素（状态）$s$ 是学生信息，$h$ 提取年龄，则像集是所有出现的年龄值。 ### 3.5.2. 原像（Preimage） **定义**：给定映射 $h: \mathcal{S} \to \mathcal{S}'$ 和一个特定的输出值 $s' \in \mathcal{S}'$，原像是指所有映射到 $s'$ 的输入值构成的集合： $$ h^{-1}(s') = \{\, s \in \mathcal{S} \mid h(s) = s' \,\}. $$ 注意，这里的 $h^{-1}$ 表示原像映射，而不是逆函数（逆函数要求单射，原像总是存在且是一个集合）。例如，若 $h$ 把颜色分类，则原像就是所有具有该颜色的原元素（状态）。 ## 3.6. 覆盖、划分的定义 **集合的覆盖**：设 $A$ 是一个非空集合，$\mathcal{C}$ 是由 $A$ 的一些子集构成的集合族。如果 $\bigcup_{X\in\mathcal{C}} X = A$，则称 $\mathcal{C}$ 是 $A$ 的一个**覆盖**。（覆盖中的子集可以相交；根据实际要求可以允许/不允许为空集。） **集合的划分**：设 $A$ 是一个非空集合，$\mathcal{P}$ 是由 $A$ 的一些非空子集构成的集合族，满足： 1. $\forall X,Y\in\mathcal{P}: X\neq Y \Rightarrow X\cap Y = \varnothing$（两两不相交）； 2. $\bigcup_{X\in\mathcal{P}} X = A$（覆盖 $A$）。则称 $\mathcal{P}$ 是 $A$ 的一个**划分**。（_划分中的每个元素称为一个**块**或**类**。_） **区别**： - 覆盖只要求子集的并集等于 $A$，允许子集之间有重叠，也允许某些元素属于多个子集。 - 划分则要求子集互不相交且非空，即每个元素恰好属于一个块。 _~~“**嵌套覆盖**”：对 $U$ 定义覆盖 $F$ 满足 $\forall A\in F, B\in F: \left(A\cap B=\empty\right)\lor\left(A\subseteq B \lor B\subseteq A\right)$，这种覆盖在数学中似乎通常称为**层状族**（laminar family），有时似乎也称为**嵌套族**或**分层族**。它要求覆盖集中的任意两个集合要么不相交，要么一个包含另一个。层状族可以包含划分（所有集合互不相交）作为特例，也允许有包含关系的层次结构。如果族覆盖了整个集合 $A$，则似乎称为一个**覆盖层状族**。~~_ 因为笔者对该定义也还不甚了解，于是姑且先划去了... ## 3.7. 集合论中的向量、矩阵、$A^n, A^{n\times n}

3.7.-1. IMP

必须得指出：在集合论中，记号 A^B 通常表示所有从集合 B 到集合 A 的函数构成的集合，即 A^n= \{ f \mid f: B \to A \}；而此时，A^n 和 \underbrace{A \times A \times \cdots \times A}_{n \text{ 个 } A}=\{(a_1, a_2, \cdots, a_n)|a_i\in A\} 并不等价！

最多只能是因为、存在一个自然的双射 \left(A^n=A^{\{0,1,\dots,n-1\}}\right) \;\cong\; \left(\underbrace{A \times A \times \cdots \times A}_{n \text{ 个 } A}=\{(a_1, a_2, \cdots, a_n)|a_i\in A\}\right)（这里 n=\{0, 1, \cdots, n-1\} 是因为自然数采用集合论定义，即 0=\empty, 1=\{0\}=\{\empty\}, 2=\{0, 1\}=\{\empty, \{\empty\}\}, 3=\{0, 1, 2\}=\{\empty, \{\empty\}, \{\empty, \{\empty\}\}\}, \cdots），于是才在同构的意义下两者 “相等”。

这可能是一个“记号滥用”的历史遗留问题 /kk。

（很显然，如果等价的话，会造成元组定义的循环定义。因为二元关系就是基于元组定义的；如果认为 A^n= \{ f \mid f: \{0, 1, \cdots, n-1\} \to A \} 和 \underbrace{A \times A \times \cdots \times A}_{n \text{ 个 } A}=\{(a_1, a_2, \cdots, a_n)|a_i\in A\} 相等，就意味着认为 f: \{0, 1, \cdots, n-1\}=(f(0), f(1), \cdots, f(n-1))、即用函数定义了元组；而函数就是基于二元关系定义的，循环论证就此产生了。）

3.7.0. 一些前置基本定义

在集合论中，记号 A^B 通常表示所有从集合 B 到集合 A 的函数构成的集合，即 A^n= \{ f \mid f: B \to A \}。
自然数的集合论定义：0=\empty, 1=\{0\}=\{\empty\}, 2=\{0, 1\}=\{\empty, \{\empty\}\}, 3=\{0, 1, 2\}=\{\empty, \{\empty\}, \{\empty, \{\empty\}\}\}, \cdots, n=\{0, 1, \cdots, n-1\}。

了解了这些后，A^{n} 与 A^{n \times n} 的含义就不言自明了：

3.7.1. A^n

根据自然数 n 的集合论定义 n=\{0,1,\dots,n-1\}：

A^n = \{ f : \{0,1,\dots,n-1\} \to A \}

3.7.2. A^{n \times n}

根据自然数 n 的集合论定义，这里的 n \times n 表示集合 \{0,1,\dots,n-1\} \times \{0,1,\dots,n-1\}，即所有有序对 (i,j)（0 \le i,j < n）构成的集合。于是：

A^{n \times n} = \{ f : \{0,\dots,n-1\} \times \{0,\dots,n-1\} \to A \}.

3.7.3. 集合论中的向量、矩阵

在集合论的框架下，向量和矩阵也是通过函数来定义的。

3.7.3.1. 向量的集合论定义

设 F 是一个集合（通常是一个域，如实数域 \mathbb{R}），n 是一个自然数（集合 \{0, 1, \dots, n-1\}）。

一个 n 维向量（或称 n 元组）就是从指标集（“标记”或“编号”一个集合中元素的那个集合）n 到 F 的一个函数：

v: n \to F

（即 v \in F^n，其中 F^n = \{ f \mid f: n \to F \}。）

此外我们还有：

比较自然地，向量 v 同构于有序组 (v(0), v(1), \dots, v(n-1))。
若将函数写作映射 i \mapsto v_i（\mapsto 表元素与像的对应关系），则上一条也可以写成下标表示：v \cong (v_0, v_1, \dots, v_{n-1})。

得指出的是，在集合论基本的向量的定义中，我们并没有区分行向量和列向量；关于这点的详细展开请见 3.5.。

3.7.3.2. 矩阵的集合论定义

设 m, n 为自然数（集合 \{0, 1, \dots, n-1\}）。一个 m \times n 矩阵是从笛卡尔积 m \times n 到 F 的一个函数：

M: m \times n \to F

即 M \in F^{\,m \times n}，其中 F^{\,m \times n} = \{ f \mid f: m \times n \to F \}。

对于 i \in m（行指标），j \in n（列指标），函数值 M(i, j) 记作 M_{(i+1)(j+1)}，表示矩阵第 i 行第 j 列的元素。
于是矩阵可以写成通常的矩形阵列： \begin{pmatrix} M_{11} & M_{12} & \cdots & M_{1n} \\ M_{21} & M_{22} & \cdots & M_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ M_{m1} & M_{m2} & \cdots & M_{mn} \end{pmatrix}

3.7.3.3. 与前文指数记号的关系

3.7.3.4. 矩阵运算的集合论描述

在集合论中，矩阵的运算定义为：

加法：若 M, N \in F^{m \times n}，定义 (M+N)(i,j) = M(i,j) + N(i,j)。
标量乘法：(cM)(i,j) = c \cdot M(i,j)。
乘法：若 M \in F^{m \times n}，N \in F^{n \times p}，则 M \cdot N \in F^{m \times p} 定义为： (M \cdot N)(i,k) = \sum_{j \in n} M(i,j) \cdot N(j,k)
这里的求和是域 F 中的运算。

3.7.3.5. 向量/列向量/行向量，和向量与矩阵的运算

（得指出的是，在集合论的基本向量的定义中，我们可能并没有区分行向量和列向量... ）

续前文；从集合论的视角来看，当涉及向量和矩阵的运算时，我们实际上是在做 1\times n / n\times 1 矩阵和一般矩阵的运算，也就是说我们实际上仍旧是在做矩阵与矩阵的运算、而非向量与矩阵的运算。

不过在书写中，出于历史原因、便捷原因（通常不用考虑集合论那么底层的东西）、以及存在一个自然的同构 F^n \cong F^{\,n \times 1} / F^n \cong F^{\,1 \times n}（即存在双射 \Phi: F^n \to F^{\,n \times 1}, (\Phi(v))(i,0) = v(i) / \Phi: F^n \to F^{\,1 \times n},(\Phi(v))(0,i) = v(i)）的原因，有可能会把向量与 1\times n 矩阵（或称 “列向量”）/ n\times 1 矩阵（或称 “行向量”）模糊混淆。

具体到线性代数应用中，常将 F^n 中的元素视为列向量，而将行向量视为 F^{1 \times n} 中的元素（即 1 \times n 矩阵），这种区分单纯是出于矩阵乘法的便利。具体来说，我们有：

列向量：F^{n \times 1} \cong F^n
行向量：F^{1 \times n}

另外，列向量与行向量之间也存在自然的同构/双射（即转置 \top）。

4. TODO

算是本文未来还要补完的方向，目前还都只写了残缺的几句，但姑且还是先放在这吧...

4.1. dfs

4.1.1. dfs 性质

定义（待完善）：

dfs 是一种遍历方法。通常采取其遍历一张图的定义。
dfs 树。定义遍历中走过的边是树边，没走过的是“虚边”（命名待定？）。

性质：

从极大联通子块任意节点开始 dfs，会遍历其所有节点。
dfs 生成树上没有横叉边（u->v 且 v 不是 u 的祖先或后代）；dfs 生成树虚边只可能是前向边或返祖边。

4.2. 典型搜索架构/板子的整理与解析（待完善）

极大联通子块。
网格填空（八皇后）、序列填空。
图遍历（还可联系一下 dfs 树性质...）。
类棋盘枚举、数字枚举、子集枚举、子图枚举...