> 逆元：使得x * inv(x) % mod = 1 的数 > 当mod为质数时可以通过费马小定理和快速幂求： > 如果a与p互质 > 则a^(p-1) % p = 1 > 它可以解决带除法的取模问题 DP 的优化 多重背包二进制分解：O(MLOG(SI)) 模板： 单调队列优化：O(MN) 模板： 区间DP的四边形不等式优化 > 对于状态转移方程为f[i][j] = min(f[i][k] + f[k+1][j]) + w[i][j]的区间dp > 且w[i][j]满足四边形不等式和区间单调性： > 对于a<=b<=c<=d， > w[a][c]+w[b][d] < w[a][d]+w[b][c] > w[a][d] >= w[b][c] > 则有：opt[i][j-1] <= opt[i][j] <= opt[i+1][j] 状态压缩DP的优化 子集枚举 SOSDP 2^N 模板 括号序列模板 数位DP记忆化搜索模板

原题 这是我的代码 注：d是找树数根的函数。 个人对题目的理解是： 找到满足d(xy)=d(z)且xy!=z且1<=x,y,z<=n的(x,y,z)的组数，大于十的时候不满足条件的只有23对，所以我直接用总的，也就是(x,y,xy)的组数，减去23，如有错误欢迎指正。 最后一个测试点错了，还不能查看测试点。 如有常识性错误请大家谅解，本人萌新。

C++开平方怎么开？求解

FLOYD算法 多源最短路算法：求得多个起点之间到达任意顶点的最短距离的算法 核心思想:：通过枚举的方式来求得任意顶点之间的最短距离 核心做法：把所有顶点都作为其他顶点的中转站，求得所有顶点之间的最短距离

质数判定+搜索下标 我勒个镭

import math n=int(input('')) s=0 for i in range(n): m=int(input()) if m <=70: s+=0.1 else: if m%70==0: s+=m//700.1 else: a=m/70 a=math.ceil(a) s+=a0.1 s=round(s,1) print(s)

题面翻译 给定 nnn 个结点的，以 111 为根，编号在 1…n1 \dots n1…n 的树。并给定排列 ppp。 qqq 次询问每次给定 l, r, xl,\,r,\,xl,r,x，你需要回答是否存在编号在 pl, pl+1, …, prp_l,\,p_{l+1},\,\dots ,\, p_{r}pl ,pl+1 ,…,pr 中的结点，使得其是 xxx 的后代。

题面翻译 题目描述 树中两个顶点 uuu 和 vvv 之间的距离是指顶点 uuu 到顶点 vvv 必须经过的最小边数。 亚历克斯的生日快到了，蒂莫菲想送他一棵有 nnn 个顶点的树。然而，亚历克斯是个喜怒无常的孩子。在 qqq 天里，他每天都会选择一个整数，第 iii 天选择的整数用 did_idi 表示。如果在第 iii 天，树上没有两片距离正好为 did_idi 的叶子节点，亚历克斯就会很失望。 蒂莫菲决定送给亚历克斯一个设计器，这样他就可以随心所欲地改变他的树了。蒂莫菲知道亚历克斯也很懒惰，所以每天一开始，他可以进行多次以下类型的操作： * 选择顶点 uuu 、 v1v_1v1 和 v2v_2v2 ，需要满足 uuu 和 v1v_1v1 之间有一条边， uuu 和 v2v_2v2 之间没有边。然后删除 uuu 和 v1v_1v1 之间的边，并在 uuu 和 v2v_2v2 之间添加一条边。如果操作后图形不再是树，则不能执行此操作。 不知怎的，蒂莫菲设法找出了所有的 did_idi 。之后，他又想出了一个绝妙的主意——以防万一，为这组集合 did_idi 制作一本说明书，这样亚历克斯就不会失望了。 输入格式 第一行包含整数 ttt（1≤t≤1001\leq t\leq1001≤t≤100），表示数据组数。 每个测试用例的第一行包含两个整数 nnn（3≤n≤5003\leq n\leq5003≤n≤500）和 qqq（1≤q≤5001\leq q\leq5001≤q≤500），分别表示树中的节点数和操作天数。 下面第 qqq 行的第 iii 行包含整数 did_idi （2≤di≤n−12\leq d_i\leq n-12≤di ≤n−1）。 保证 ∑n,∑q≤500\sum n,\sum q\le500∑n,∑q≤500。 可以证明，满足所述条件的树和操作序列总是存在的。 输出格式 对于每组数据，首先输出描述树的 n−1n-1n−1 条边。如果节点 uuu 和 vvv 之间有一条边，则必须输出 u vu\ vu v 或 v uv\ uv u。 在接下来的 qqq 行中，每行输出三个整数 uuu、v1v_1v1 、v2v_2v2 。如果亚历克斯这天不需要执行操作，则直接输出 -1 -1 -1\texttt{-1 -1 -1}-1 -1 -1。

Vanya和Vova在玩游戏。玩家得到一个整数nnn。轮到玩家时，玩家可以加111或减111。 Vanya先开始。如果Vanya移动后,nnn 可以被 333 整除，那么他就赢了，输出First。如果已经过了 10 步，而Vanya没有赢，那么Vova就赢了，输出Second。

来源洛谷 题面翻译 给定数列 aaa，求有多少对 (i,j)(i,j)(i,j) 满足 (2ai)(2aj)=(2aj)(2ai)(2^{a_i})^{(2^{a_j})}=(2^{a_j})^{(2^{a_i})}(2ai )(2aj )=(2aj )(2ai )。

来源：洛谷（自行添加了一些） 题目描述 给定一个数组，求数组中连续子数组之和的最大值，但要求子数组必须满足：相邻两项奇偶性不同。 输出最大总和。 输入描述 输入一个整数，第一行一个整数 ttt 代表测试样例的组数， 接下来 2×t2 \times t2×t 行中，第一行输入一个整数 nnn，第二行输入 nnn 个整数表示数组。（多组数据） 输出描述 输出 ttt 行，每行一个整数表示答案。

来源我的翻译洛谷翻译+我的 亚历克斯正在参与拍摄布尔马斯特的另一个视频，布尔马斯特让亚历克斯准备25万吨TNT炸药，但亚历克斯没有听清楚，于是他准备了 𝑛个箱子，并把它们摆成一排等待卡车。左边的 𝑖个箱子重𝑎𝑖𝑎_𝑖ai 吨。 亚历克斯要使用的所有卡车都装有相同数量的箱子，用 𝑘表示。装载过程如下： * 第一个 kkk 个箱子装到第一辆卡车上、 * 第二个𝑘箱子装到第二辆卡车上、 * ⋯\cdots⋯ * 最后𝑘个箱子装到第 kn \frac{k}{n} nk 辆卡车上。 装载完成后，每辆卡车上必须有 𝑘个箱子。换句话说，如果在某一时刻无法将𝑘 个箱子准确地装入卡车，那么 𝑘个箱子的装载选项就无法实现。 亚历克斯讨厌公正，所以他希望两辆卡车总重量的最大绝对值差越大越好。如果只有一辆卡车，这个值就是0。 亚历克斯有很多关系，所以每 1≤𝑘≤𝑛，他都能找到一家公司，使其每辆卡车正好能装载 𝑘个箱子。打印任意两辆卡车总重量的最大绝对差值。

F12真是YYDS

CF1697C.awoo's Favorite Problem

小帅，你是真的饿了，什么都吃得下

算法 五大特性 1有穷性 明确运行次数（不为死循环） 2确切性 程序中不出现歧义 3输入项 0~n个输入均可 4输出项 必须有输出，无输出的算法无意义 5可行性 输出要正确，在有效时间中完成 时间复杂度 T（）为程序运行的次数 O（）为T（）最高项去系数 数据量推算法复杂度 竞赛通常限制时长为1s，一般运行10^8次左右。以下为常用时间复杂度。 时间复杂度 数据大小 O(n) <5*10^7 O(n logn) <5*10^5 O(n^2) <5000 O(n^3) <500 O(2^n) <20 O(n!) <10 两种数据点超出时空范围的报错： TLE：程序超时（死循环/算法繁琐） MLE：超内存（空间过大） 模拟算法 1 审题立意 不遗漏提取题目条件 ，分析题目样例 2 分析关系 最好用流程图或表格列出各条件关系 3 编写程序 用相应语言，逐步求精的方法描述具体算法 例： 时间复杂度 算法 O(n^3) 暴力 O(n^2) 枚举 O(n) dp(动态规划) 4 调试运行 调试代码并测试样例，如输出中间重要过程，观察中间过程是否正确 5 构造数据 构造一些更复杂，更全面的测试数据检查程序正确性 对拍 自己给数据点，将两种不同复杂度的算法的结果进行对比。 代码：

矩阵快速幂，听起来很难，模板题也都是绿色的，令人望而却步。我在发呆时突然想起了矩阵快速幂，于是花了一个下午去学习它。于是，就有了这篇文章。 ACGO 主题库上似乎还没有矩阵快速幂的题目，我从洛谷上搬运了几道。数据自造，强度应该是够的，如果搬的题目或数据有什么问题还请联系我。题单：矩阵模板题。原题分别为洛谷 P3390，P1939 和 P1962。 正文从此开始。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前置知识： * 快速幂 * 矩阵 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 概念 先从矩阵的乘法讲起。矩阵乘法 AB=CAB=CAB=C 的定义为： cij=∑k=1naikbkj,(1≤i≤m, 1≤j≤p).c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} cij =k=1∑n aik bkj ,(1≤i≤m, 1≤j≤p). 其中 AAA 的大小为 m×nm\times nm×n，BBB 的大小为 n×pn\times pn×p，结果 CCC 的大小为 m×pm\times pm×p。如果 AAA 的列数与 BBB 的行数不同，则他们无法进行矩阵乘法。 是不是有点抽象？举个例子你就明白了。当 AAA 的大小为 2×22\times 22×2，BBB 的大小为 2×32\times 32×3 时，则 C=[a11b11+a12b21a11b12+a12b22a11b13+a12b23a21b11+a22b21a21b12+a22b22a21b13+a22b23]. C = \begin{bmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} & a_{11}b_{13}+a_{12}b_{23}\\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} & a_{21}b_{13}+a_{22}b_{23} \end{bmatrix} \text{.} C=[a11 b11 +a12 b21 a21 b11 +a22 b21 a11 b12 +a12 b22 a21 b12 +a22 b22 a11 b13 +a12 b23 a21 b13 +a22 b23 ]. 同时，我们可以证明矩阵乘法满足结合律，但在一般情况下不满足交换律。 我们立刻写出了这样的矩阵乘法代码： 这个代码的时间复杂度是 O(n3)O(n^3)O(n3) 的，可以接受。事实上，《算法导论》给出了一种时间复杂度 O(nlog⁡27)O(n^{\log_2 7})O(nlog2 7) 的矩阵乘法算法，但似乎并没有在 OI 界得到广泛运用，因此这里暂不介绍。 现在，我们回到正题：矩阵快速幂。由于矩阵乘法满足结合律，我们把它当作一般的快速幂打代码即可，只不过数字变成了矩阵，乘法变成了矩阵乘法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 实现 先放出 AC 模板题的代码： 整个代码的精髓是这几行： 最令人疑惑的是第三行。按照第三行的定义，我们构造出的矩阵是： Ans=[10⋯001⋯⋮⋮⋮⋱⋮0⋯⋯1]. Ans = \begin{bmatrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & \vdots\\ \vdots & \vdots & \ddots & \vdots\\ 0 & \cdots & \cdots & 1\\ \end{bmatrix} \text{.} Ans= 10⋮0 01⋮⋯ ⋯⋯⋱⋯ 0⋮⋮1 . 这个矩阵我们称其为单位矩阵。任何矩阵与单位矩阵相乘，得到的依然是原矩阵。 因此，单位矩阵就类似数的乘法中的 111，起到基的作用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 应用 例题：斐波那契数列（洛谷）或斐波那契数列（ACGO 搬运）。 题面非常简单，就是让你求斐波那契数列的第 nnn 项。但是看到数据范围，1≤n<2631\leq n<2^{63}1≤n<263，显然事情并不是那么简单。现在，我们先从斐波那契数列的本质想起。它的递推式是这样的： fi=fi−1+fi−2f_i=f_{i-1}+f_{i-2} fi =fi−1 +fi−2 发现 fif_ifi 的值只与前两项有关。我们只需要保存两项的值就够了。我们把接下来需要保存的两项 fi,fi−1f_i,f_{i-1}fi ,fi−1 通过现在已知的两项 fi−1,fi−2f_{i-1},f_{i-2}fi−1 ,fi−2 表达出来，形成一个线性方程组： {1×fi−1+1×fi−2=fi1×fi−1+0×fi−2=fi−1\begin{cases} 1\times f_{i-1}+1\times f_{i-2} &= f_i\\ 1\times f_{i-1}+0\times f_{i-2} &= f_{i-1} \end{cases}{1×fi−1 +1×fi−2 1×fi−1 +0×fi−2 =fi =fi−1 根据矩阵乘法，我们可以把这个方程组表达成两个矩阵相乘： [1110][fi−1fi−2]=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_{i-1}\\ f_{i-2} \end{bmatrix}=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ][fi−1 fi−2 ]=[fi fi−1 ] 这是线性代数中十分常见的变换。是不是非常神奇？别急，还有更神奇的。我们发现矩阵 [fi−1fi−2]\begin{bmatrix}f_{i-1}\\f_{i-2}\end{bmatrix}[fi−1 fi−2 ] 也可以用这个式子求出来。于是，我们可以把它展开： [1110]([1110][fi−2fi−3])=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_{i-2}\\ f_{i-3} \end{bmatrix}\right)=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]([11 10 ][fi−2 fi−3 ])=[fi fi−1 ] 继续展开直到已知项 [f2f1]\begin{bmatrix}f_2\\f_1\end{bmatrix}[f2 f1 ]： [1110]([1110](⋯[1110][f2f1]⋯ ))=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\cdots\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_2\\ f_1 \end{bmatrix}\cdots\right)\right)=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]([11 10 ](⋯[11 10 ][f2 f1 ]⋯))=[fi fi−1 ] 又根据矩阵乘法的结合律： [1110]i−2[f2f1]=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{i-2}\begin{bmatrix} f_2\\ f_1 \end{bmatrix}=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]i−2[f2 f1 ]=[fi fi−1 ] （为什么是 i−2i-2i−2 次？因为乘 iii 次的时候结果矩阵的首项就是 fi+2f_{i+2}fi+2 了，所以乘 i−2i-2i−2 次的时候结果矩阵的首项就刚好是 fif_ifi 了，如果不理解手推一下就明白了。） 现在，你一定发现了：[1110]i−2\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{i-2}[11 10 ]i−2 这一项，直接使用矩阵快速幂即可。最后再乘上 [f2f1]\begin{bmatrix}f_2\\f_1\end{bmatrix}[f2 f1 ] 即 [11]\begin{bmatrix}1\\1\end{bmatrix}[11 ]，得到的结果矩阵首项即为所求的 fif_ifi 。由于矩阵的大小为常数，所以可以把单次矩阵乘法视为 O(1)O(1)O(1)，矩阵快速幂的时间复杂度即为 O(log⁡n)O(\log n)O(logn)，轻松跑过 long long 范围。注意特判 n≤2n\leq 2n≤2 即可（本搬题人好心地加上了这两个极限情况）。AC 代码如下： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 总结一下，用矩阵快速幂优化此类递推（动态规划）的步骤： 1. 确定哪些状态对结果状态或过程状态有贡献。只保留有贡献的状态。 2. 确定上一次得到的状态转移到当前状态使用的递推式（方程组）。 3. 提取方程组的各项系数为转移矩阵。 4. 计算转移矩阵的次数。 5. 写下矩阵快速幂和矩阵乘法模板。 接下来大家可以尝试一下矩阵加速（数列）（洛谷）、矩阵加速（数列）（ACGO 搬运）和广义斐波那契数列（洛谷）。如果你会数论，还可以尝试斐波那契公约数（我不会）。 祝大家暑假快乐！ 看在我搬题，打 LaTeX\LaTeX{}LATE X，写 Markdown 这么努力，可否留个赞支持一下 qwq。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Upd on 2024/6/30：ACGO主题库已有广义斐波那契数列与斐波那契公约数。

题目描述 小码君被邀请到一个节目上，可以在N个岛上寻找宝藏，会随机给小码君降落到其中的一个岛上，每一个岛有通向其他岛的路径（也有可能没有），都有的岛屿之间一共有M条路径，每一个岛都有一个编号，编号越大的岛屿宝藏价值越大，小码君现在想要知道所有位置可以能够去往的最大的编号的岛屿是多少。 提示 n<1000,m<2000 输入格式 第一行输入一个N，M表示有N个岛，M条路径 输出格式 每一个点可以去往的最大的岛屿的编号 样例组输入#1 5 3 1 2 3 4 2 4 样例组输出#1 4 4 4 4 5

SE是啥