2020-2021:teams:legal_string:王智彪:数理知识
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/10 20:55] 王智彪 |
2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/10 23:17] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 113: | 行 113: | ||
| ===== 矩阵的操作 ===== | ===== 矩阵的操作 ===== | ||
| - | 例题：三维空间中 $n$ 个点 $p_{i}$ ，要求将 $m$ 个操作都应用与这些点，操作种类有三种： | + | 例题1：三维空间中 $n$ 个点 $p_{i}$ ，要求将 $m$ 个操作都应用与这些点，操作种类有三种： |
| 1.沿向量移动 | 1.沿向量移动 | ||
| 行 136: | 行 136: | ||
| 于是就把三种矩阵处理好了，分别求 $k$ 的快速幂，这样复杂度可以看成是 $O(mlogk)$ ，最后对于 $n$ 个点，分别乘矩阵，总复杂度为 $O(n+mlogk)$ 。 | 于是就把三种矩阵处理好了，分别求 $k$ 的快速幂，这样复杂度可以看成是 $O(mlogk)$ ，最后对于 $n$ 个点，分别乘矩阵，总复杂度为 $O(n+mlogk)$ 。 | ||
| + | |||
| + | 例题2：定长路径计数 | ||
| + | |||
| + | 给一个有向图，边权都为 $1$ ，求任意两点 $u,v$ 间从 $u$ 到 $v$ ，长度为 $k$ 的路径的条数。 | ||
| + | |||
| + | 套路题，将邻接矩阵求 $k$ 次幂即可。 | ||
| + | |||
| + | 如果是小于等于 $k$ ，则对于每个点加一个权值为 $1$ 的自环，这样就可以原地踏步，包括所有情况了。 | ||
| + | |||
| + | 例题3：树上询问 | ||
| + | |||
| + | 有一颗 $n$ 结点的树，根为 $1$ 号结点。每个结点有两个权值 $k_{i},t_{i}$ ，初始值均为 $0$ 。 | ||
| + | |||
| + | 有三种操作： | ||
| + | |||
| + | 1.将 $x$ 到根的路径上所有点的 $k_{i}$ 变成 $k_{i}+d$ | ||
| + | |||
| + | 2.将 $x$ 到根的路径上所有点的 $t_{i}$ 变成 $t_{i}+d×k_{i}$ | ||
| + | |||
| + | 3.查询点 $t_{x}$ | ||
| + | |||
| + | 我们用矩阵维护两种操作 | ||
| + | |||
| + | 每个点的矩阵都设为 $[k\ t\ 1]$ ，末尾的 $1$ 的理由上面说过了 | ||
| + | |||
| + | 于是两种操作写一下就很显然能知道转移矩阵了。 | ||
| ===== 组合数 ===== | ===== 组合数 ===== | ||
2020-2021/teams/legal_string/王智彪/数理知识.1628600125.txt.gz · 最后更改: 2021/08/10 20:55 由 王智彪
