n-m 2 16 Pk(Kn)k(k-1)…(k-n1)。 C：A2对角线元素aii2等于对应顶点vi的度数，所以对角线元素之和等于边数的两倍。 A的所有特征值的平方和等于A2的对角线元素之和。 B 完全图没有顶点隔，实际上也只有以完全图为生成子图的图没有顶点隔。 连通…

传送门 题意 给一个字符串，求它有多少个不同的子串。 思路 后缀数组当然是能做的，每个sa[i] - height[i]的和就是答案了。 后缀自动机也可以做，后缀自动机上从起点到任意状态就是一个子串，每条路径表示的子串都不同，所…

题目大意&#xff1a; 思路&#xff1a; DFS爆搜 数据小&#xff0c;可以轻松AC。 代码&#xff1a; #include <cstdio> #include <iostream> using namespace std;int sum,n,m,a[61][31],t[31],b[61],l,ok;int p() //判断 {ok0;for (int i1;i<m;i) //枚…

编译环境 &#xff1a; arm-linux-gcc #include <sys/mman.h> #include <stdio.h> #include <stdlib.h> #include <errno.h> #include <string.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #inclu…

链接 点击跳转 题解 a n s ∑ u ∈ s a m ( l e n u − l e n f ( u ) ) ans \sum_{u \in sam} ( len_u - len_{f(u)} ) ansu∈sam∑​(lenu​−lenf(u)​) 名不虚传&#xff0c;后缀自动机果然是快&#xff0c;完爆后缀数组 代码 #include <bits/stdc.h> #includ…

P2408 不同子串个数(SA-LCP||SAM) 传送门 经典的 S A − L C P SA-LCP SA−LCP题目。 显然所有子串数目为 n ( n 1 ) 2 \dfrac{n(n1)}{2} 2n(n1)​。 因此我们只需知道重复的子串有多少个。 根据 L C P LCP LCP我们知道利用 L C P LCP LCP求出的 h e i g h t [ i ] L C …

不同子串数 题目链接&#xff1a;ybt金牌导航2-3-2 / luogu P2408 题目大意 给你一个字符串&#xff0c;问你它有多少个不同的子串。 思路 当然这种字符串题都有很多做法&#xff0c;我们这里主要是将 SAM 的用途&#xff0c;所以用的是 SAM。 那用 SAM 要怎么求呢&#…

题目链接 裸体就是身体。 建出\(SAM\)&#xff0c;\(DAG\)上跑\(DP\)&#xff0c;\(f[u]1\sum_{(u,v)\in DAG}f[v]\) 答案为\(f[1]-1\)&#xff08;因为根节点没有字符&#xff09; #include <cstdio> #include <cstring> #include <algorithm> using namesp…