#include<bits/stdc++.h> #include<iostream> using namespace std; int isp(int n) { int sum=1; while (n > 0){ sum=n*sum; n--; } return sum; } int main(){ int n; cin>>n; cout<<isp(n); return 0; }

,,,

https://www.acgo.cn/contest/2204/detail?matchRoundId=2204&examId=40534&teamCode=1793944541884059648&openLevel=2

https://www.acgo.cn/application/1776484607864774656

https://www.acgo.cn/contest/2026/detail?matchRoundId=2026&examId=39081&teamCode=1661232050350374912&openLevel=2 邀请码：SHAi

4. 游戏的规则是，在你和小码君面前有 N 个数，同时将给出一个数 C ,要求你和小码君在这组数内找到两个数，满足 A−B=C 。找出的数对越多，你们的排名越高。 为了计算赢得比赛的可能性，你们打算先计算出所有满足此条件的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入格式 第一行包含两个正整数 N 和 C 。 接下来的一行包含 N 个正整数，表示你将在这 N 个数中找数对。 输出格式 共一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。 样例组 输入#1 复制 4 1 1 1 2 3 输出#1 复制 3 提示说明 对于 75% 的数据，1 ≤ N ≤ 2000。 对于 100% 的数据，1 ≤ N ≤ 2×10 5 ，0 ≤ a i ≤ 2 30 , 1 ≤ C ≤ 2 30 。 样例解释： 4 个数，分别为 1 1 2 3，总共有 3 对 A-B 的值等于 1。 这三对分别为 2-1、2-1、3-2（不同位置的数字一样的数对算不同的数对）

1.想要投稿超难50题的人可以关注@阿墨（创题）在自己的个人题单里创建名为”稿超难50题“的题单把需要投稿的题目放入题单里@阿墨（创题）每周日查看。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 嗯嗯嗯额-_-

1.想要投稿超难50题的人可以关注@阿墨（创题）在自己的个人题单里创建名为”稿超难50题“的题单把需要投稿的题目放入题单里@阿墨（创题）每周日查看。 2..想要挑战超难50题的人可以关注@阿墨（创题）在他的个人题单挑战。

AC - Accepted（答案正确） WA - Wrong Answer（答案错误） TLE - Time Limit Exceeded（超出时间限制） RE - Runtime Error（运行时错误） CE - Compilation Error（编译错误） MLE - Memory Limit Exceeded（超出内存限制） OLE - Output Limit Exceeded（输出限制超出） PE - Presentation Error（格式错误）

STL库 包含很多数据结构，可以节省手搓的时间直接用： vector: 动态数组 queue: 队列 priority_queue: 优先队列 deque: 双向队列 set: 有序集合 multiset: 有序集合，但允许相同的元素 unordered_set: 无序集合 map: 字典，以键值对的方式储存数据 unordered_map: 无序的字典，通过哈希实现 bitset: 一种二进制数据结构，常用于加速位运算 倍增 一种基于指数增长模式的算法设计技术 典型例题：求a^b % (1e9+7), a<=1e9, b<=1e9 模板： ST表 一种用于解决区间最小/最大值的数据结构 模板： 矩阵快速幂 矩阵作为倍增的对象 矩阵类乘法的实现： 可以用来加速一些递推方程的计算，例如： 斐波那契数列的地推方程可以表示为：f[n]=f[n-1]+f[n-2] 使用矩阵可以表示为： [Fn+1Fn]=[1110]n⋅[11]\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix} [Fn+1 Fn ]=[11 10 ]n⋅[11 ] 其中 FnF_nFn 表示第 n 个Fibonacci数。 并查集 一种处理不相交集合的数据结构和算法 模板：

图 图是若干个给定的顶点，以及若干条连接两个顶点的边所构成的图形。这种图形通常用来描述 常用G(V,E)G(V,E)G(V,E)表示。某些事物之间的某种特定关系，用顶点代表事物，用连接两个顶点的边表示相应两个事物具有某种关系。 VVV为顶点集合，EEE为边集合。 图是图论的研究对象 顶点的个数叫做图的阶 相关定义 * 有向图的基图：忽略有向图所有边的方向得到的无向图 * 完全图：无向图中任何一对顶点之间都有一条边 * 有向完全图：有向图中任何一对顶点u和v都存在<u,v><v,u>两条有向边 * 稀疏图：边的数目相对少（远小于n(n−1)n(n-1)n(n−1)) * 稠密图：边的数目相对多（接近于完全图或有向完全图） * 平凡图：只有一个顶点的图 * 零图：边集合为空的图 * 自环：一个顶点连接到自身的边 * 重边：两个顶点之间有多条边 * 权值图：边带有全权值的图 * 简单图： 一种无向图或有向图，其中不存在自环与重边 * 多重图：一种无向图或有向图，其中存在自环与重边 * 路径：在图G(V,E)中从顶点viv_ivi 出发，沿着一些边经过一些顶点viv_ivi ,vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,vp3v_{p3}vp3 ,……,vpmv_{pm}vpm 到达顶点vjv_jvj ，则称顶点序列{viv_ivi ,vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,vp3v_{p3}vp3 ,……,vpmv_{pm}vpm ,vjv_jvj }为viv_ivi 到vjv_jvj 的一条路径 * 联通：若从顶点u至v有路径，则称顶点u，v是联通的 * 如果无向图中任意一对顶点都是连通的，则称此图为连通图 * 如果有向图中任意一对顶点都是互相连通的，则称此图为强连通图 树 * 树：一个不存在回路无相连通图 * 树是一种特殊的图 * 树是一种非线性的数据结构，是由n(n≥0)n(n\ge 0)n(n≥0)个节点组成的有限集合 当n==0n==0n==0时，称为空树；如果n>0n>0n>0，树有且只有一个根节点 * 树的前驱与后继：除根节点没有前驱外，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点 * 节点的后继称为节点的的孩子，节点的之家前驱称为节点的父亲，有同一个父节点的不同节点互称兄弟 * 结点拥有的子树的数量叫做节点的度 树中节点的层次：树中根节点为第一层，根节点的孩子为第二层，以此类推…… 树中节点最大层次乘坐是的高度。 注意：有些题中根节点是第0层 树的存储 父亲表示法： 孩子表示法 特殊的树 二叉树（BT） 度数最大为2的树，即二叉树的节点最多有两个子节点，每个子节点分别被称为左孩子节点、右孩子节点， 每个子树分别被称为左子树、右子树 满二叉树：一棵深度为kkk且有2k+12^{k+1}2k+1个节点的二叉树 完全二叉树：若二叉树的高度为kkk，则共有kkk层，除第kkk层外，其他各层(1(1(1到(k−1))(k-1))(k−1))的节点数都达到最大个数， 且kkk层缺少的节点是从左到右并连续的，则称其为完全二叉树 二叉搜索树（BST） 二叉搜索树具有以下性质： * 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。 * 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。 * 任意结点的左、右子树也分别为二叉搜索树。

图论 图 是由若干个给定的顶点/以及若干条连接两个顶点的边所构成的图形 图 是 图论 的研究对象 图(graph)图(graph)图(graph):通常用 G(V,E)G(V,E)G(V,E)表示。VVV 为集合，EEE 为边集合。 > G(V,E)-->GraphGraphGraph VertexVertexVertex EdgeEdgeEdge 顶点的个数称为图的阶 路径 在图G(V,E)中从顶点viv_ivi 出发，沿着一些边经过一些顶点vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,………………,vpmv_{pm}vpm 有向图 有向图：单向的 <1,5>为一对顶点构成的有序对（用尖括号括起来） 有向图的基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。（无向图G为有向图的G1的基图） 完全图 一个n阶的完全图含有n∗(n−1)÷2n*(n-1) \div 2n∗(n−1)÷2条边。 完全有向图 有向图中任何一对顶点u和v，都存在<u,v>&<v,u>两条有向边。一个n阶的完全有向图含有n∗(n−1)n*(n-1)n∗(n−1)条边。 稀疏图 边的数目相对较小（远小于n∗(n−1)n*(n-1)n∗(n−1)). 稠密图 边的数量相对较多（接近于完全图或者有向完全图 平凡图 只有一个顶点的图 自环 一个节点连接到自身的边 重边 两个结点之间存在多条边。 带权图 边上有带权值的图 简单图（5） 一种无向图或有向图，其中不存在自环和重边。 多重图（5） 一种无向图或有向图，其中存在自环和重边。 连通 若从顶点u到v有路径，则称顶点u和v是连通的。 连通图 如果无向图中任意一对顶点都是连通的，称此图为连通图。 强连通图 有向图中，每一对顶点u和v，存在u<−>vu<->vu<−>v(双向奔赴)。 连通图和连通分量 如果在图G中，任意2个顶点之间都存在路径，那么称G为连通图（注意是任意2顶点）。上面那张城市之间的图，每个城市之间都有路径，因此是连通图。而下面这张图中，顶点8和顶点2之间就不存在路径，因此下图不是一个连通图，当然该图中还有很多顶点之间不存在路径。 上图虽然不是一个连通图，但它有多个连通子图：0,1,2顶点构成一个连通子图，0,1,2,3,4顶点构成的子图是连通图，6,7,8,9顶点构成的子图也是连通图，当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图，也就是连通分量。连通分量有如下特点： 1）是子图； 2）子图是连通的； 3）子图含有最大顶点数。 注意：“最大连通子图”指的是无法再扩展了，不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。 显然，对于连通图来说，它的最大连通子图就是其本身，连通分量也是其本身。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 例题 有101010个顶点的无向图至少有（ ）条边边边才能确保是一个连通图。 解析：2个顶点需要1条边，3个顶点需要2条边，以此类推 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 树 n个V，n-1 个E 连通 当n==0时，称为空树。 二叉树 是一种度数为2的树 满二叉树： 定义：一个深度为k且有2k−12^k-12k−1个结点的树叫做满二叉树。 树中结点的最大层次称为树的（深度）高度； 完全二叉树 若二叉树的高度为kkk，则共有kkk层，除第kkk层外，其他各层(1 (k−1))(1~(k-1))(1 (k−1))的结点数都达到最大个数，且第kkk层缺少的结点是从右向左并连续的（存在的是从左到右），这就是完全二叉树。 注意:注意:注意:满二叉树也是完全二叉树的一种。 二叉搜索树 一种应用广泛的二叉树。

图和树 图(有向图，无向图，有向图的基图是无向图) 定义 > 图有若干节点和线组成 表示 > G(V,E) V顶点集合，E边集合 完全图 > 定义:无向图中任意两点都有相连 > 计算方法：1.n阶完全图有n*(n-1)/2条边 稀疏图（边数量相对少（远小于N*(N-1)））&&稠密图(接近完全图或有向完全图) 自环（自己链连接自己）&&重边（两点之间有多条边相连） 简单图 > 无向或有向图，无自环或重边 多重图 > 无向或有向图，有自环或重边 联通 > 从u到v有路径，则称u与v联通 连通图 > 无向图中任意两点相连 强连通图 > 有向图中，有从u到v的路径，也有从v到u的路径 路径 > 在图G(V,E)中， 树 定义 > 无向连通图中不存在回路 性质 > 有n个点，n-1条边 度 > 结点所拥有的子树的数量，为结点的度，度=0->叶子结点，度!=0->分支结点 前驱 后继 > 除根外，任意结点都有前驱结点 > 除叶子结点外都有后继结点 树的深度(高度) > 根为第一层，根的孩子为第二层，以此类推 二叉树（树的度数为2） > 两个子树，左子树（左孩子），右子树（右孩子） 满二叉树 > 有k层，且结点树为$ 2^k-1 $，即是一个标准的二叉树 完全二叉树 > 二叉树高度为k，除第k层以前是满的，第k层不完全，但第k层的结点是从左到右连续的 > ####二叉搜索树 > 根结点的左子树<根节点 > 根节点的右子树>根节点

AKSZ-第X课 图论 图分为有向图、无向图，有权图、无权图 图：G(V,E) V=顶集 E=边集 顶点的个数是图的阶 把几组具体的联系转变为抽象的模型就是图论模型 > G(V,E)G(V,E)G(V,E)=GraphGraphGraph VertexVertexVertex EdgeEdgeEdge 有向图的基础就是无向图。 每个顶点之间都有边相连就是完全图 > 完全图公式：边数=n∗(n−1)/2边数=n*(n-1)/2边数=n∗(n−1)/2 > 但如果有向，就不用除以二 稀疏图和稠密图是用来看边的密度 对于n=1e5 边数<=1e5就算稀疏图 自环是自己连自己，重边就是有完全一致的边 边上有数字就是有权值 简单图就是没有自环和重边，相反则是多重图 平凡图就是只有一个点，零图就是没路 路径 从V（j）出发到V（i）就是路径 长度就是边数 若u到v有路径，则称他们是联通的 如果谁到谁都有路，就是连通图，有向则称为强连通图 树 n个顶点，必须联通，n+e条边 **根节点（root）**绝对固定 度 就是子节点数量 度为零是叶子节点，否则叫分支节点，一整棵树的度是度的最大值 前驱、后继、兄弟 对于一个点，它的父节点就是它的前驱，子节点就是后继，同父节点的几个节点就是兄弟 树的输入 高度 高度就是根节点走到一个点所用的步数，+不+1看根节点深度 树中任意两个节点之间有且仅有一条简单路径 树的遍历 二叉树 每个节点都有两个子树 满二叉树 深度为k且有2k−12^k-12k−1个节点 完全二叉树 若二叉树高度为k，除第k层外，（1~（k-1））的节点数都达到最大个数，且第k层有的点是从左到右并连续的，这就是完全二叉树 二叉搜索树 所字数所有节点都小于根节点，右边则大于

rt，记忆化的本质就是 dpdpdp 思想，这种题都不用找方程，注意下细节就行了

rt，蒟蒻居然TLE了，一康数据发现#3、#4测试点 n = 1，#3 测试点中图仅仅包含1,#4 恰恰相反，只有1个0,所以可以加入以下特盘：

翻译 多米尼克设想了一个正整数p1，…，pn的数组。让我们将该数组的排序版本表示为q1，…，qn。 此外，他还设想了一系列允许的换人。如果一对（X，Y）是允许替换集合的成员，Dominik可以交换数组p中X和Y位置的数字。 Marin正在向Dominik Q提供查询，每个查询都属于以下类型之一： 交换A和B位置的数字。 将对（A，B）添加到允许的替换集合中。 马林可以给已经在允许换人范围内的一对（A，B）。 看看是否可以只使用允许的替换对数组进行排序？ 替换可以按任意顺序使用，并且每个替换可以进行任意次数。 如果从位置a的数字可以仅使用允许的字幕转移到位置B，那么我们调用一对链接的位置（a，B）。 让我们把链接到位置A的所有位置的集合称为A的云。 如果云中的每个位置j都可以使用一系列允许的替换来实现pj=qj，那么云就是好的。 你必须回答存在多少对不同的位置（A，B），使其保持： a.位置a和B没有链接。B.a的云不好，B的云也不好。c.如果我们将对（a，B）添加到允许的替换集，则a的云（通过链接a的云和B的云创建）变好。 请注意：对（A，B）和（B，A）被认为是同一对。 输入格式 输入的第一行包含整数N和Q（1≤N，Q≤1000 000）。 第二行输入包含N个整数p1、…、pn（1≤p1、…，pn≤1000 000）。 以下Q行中的每一行都包含以下格式的查询： ● 行中的第一个数字是集合{1,2,3,4}中的查询T的类型。 ● 如果查询T的类型是1或2，则后面跟着两个不同的整数A和B（1≤A，B≤N） 其表示取代（A、B）。 输出格式 对于每个类型为3或4的查询，在其单独的行中输出答案。 类型3的查询答案是“DA”（克罗地亚语表示是）或“NE”（克罗地亚文表示否），不带引号，类型4的查询答案为任务中的非负整数。 输入输出样例 输入#1. 复制 3 5 1 3 2 4. 3. 2 2 3 4. 3. 输出#1. 复制 1. 氖 0 DA 输入#2. 复制 5 5 4 2 1 4 4 3. 4. 1 1 3 3. 4. 输出#2. 复制 氖 1. DA 0 输入#3. 复制 4 10 2 1 4 3 3. 4. 1 1 2 3. 4. 2 2 3 2 1 2 4. 2 3 4 3. 输出#3. 复制 氖 2. 氖 1. 3. DA 说明/提示 在占总分50%的测试用例中，它将保持N，Q≤1000。 第一个测试用例的说明： 第一个查询的答案是1，因为位置对（2，3）满足所有给定的要求。 第二个查询的答案是NE（否），因为无法将数字2和3转移到 对应的位置，因为所允许的替换的集合是空的。 在第三个查询之后，我们将对（2，3）添加到允许的替换集合中。 第四个查询的答案现在是0，因为2和3已经链接，而第五个查询的回答 查询为DA（是），因为可以通过应用允许的替换（2，3）对数组进行排序。