爱飞鱼的blog

DFS序专题 NC13611 https://ac.nowcoder.com/acm/problem/13611 题意：要求树上任意两点相同颜色之间的路径上的点也是相同颜色，k种颜色，求方案数 Solution：原问题等价于将树分割成若干连通块且相互之间颜色不同 其实是道数论题。 题意可以转化为将树分割为不超过 kkk 个连通块，每个连通块颜色不同。若将树分割为 iii 个连通块，则需要删去 i−1i-1i−1 条边，故方案数为 Cn−1i−1\mathrm{C}_{n-1}^{i-1}Cn−1i−1​ 。同时，要从 kkk 种颜色中选出 iii 中颜色染色，而且是有顺序的，故方案数为 Aki\mathrm{A}_{k}^{i}Aki​ 。 综上，总的方案数为： ans=∑i=1min⁡(n,k)Cn−1i−1Akians= \sum_{i=1}^{\min(n,k)}\mathrm{C}_{n-1}^{i-1}\mathrm{A}_{k}^{i}ans=∑i=1min(n,k)​Cn−1i−1​Aki​ 可以线性求逆元，枚举 iii 实现。...

题面翻译 给你一个NNN个节点的树，求一个1⋯N1\cdots N1⋯N的排列(p1,p2,⋯pN)(p_1,p_2,\cdots p_N)(p1​,p2​,⋯pN​) ，使得∑dist(i,pi)\sum dist(i,p_i)∑dist(i,pi​)最大。 求这样的排列的个数。答案对109+710^9+7109+7取模。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <cmath>using namespace std;typedef long long ll;typedef pair<int,int>ttfa;inline ll...

后缀数组SA 简述：花费O(nlogn)用倍增+基数排序花费O(nlogn)用倍增+基数排序花费O(nlogn)用倍增+基数排序构建H数组完成对后缀排序。 思想在于calabashboy，实现细节和方法看dxsf。 注意细节：传入字符串0base，内部会修改成1base，传的是引用。值域都在1-n之间 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182struct SA { int n; // 存储字符串的长度 vector<int> sa, rk, lc; // sa: 后缀数组, rk: 排名数组, lc: 最长公共前缀数组 (LCP) SparseTable<int> qmn; SA(string& s)...

马拉车学习笔记 概念与定义： 回文串：S=R(S) 回文中心： 奇长度：回文中心为S[n+12]S[\frac{n+1}{2}]S[2n+1​],如abcbaabcbaabcba 偶长度：回文中心在S[n2]与S[n2+1]S[\frac{n}{2}]与S[\frac{n}{2}+1]S[2n​]与S[2n​+1]之间,如abc∣cbaabc|cbaabc∣cba。 回文半径L：回文中心到回文串左右端点的距离，常用二元组<回文中心，回文半径>< 回文中心，回文半径><回文中心，回文半径>来表示一个回文子串. 回文长度和回文半径的关系： 奇长度回文串：∣S∣=2L−1|S|=2L-1∣S∣=2L−1 偶长度回文串：∣S∣=2L|S|=2L∣S∣=2L 回文半径的二分性：回文半径-1 等价于同时删掉回文串的首尾字母，依然是回文串。 回文串和 Border：对于回文串 S，回文前（后）缀等价于Border。因此得到结论：回文串的回文前后缀都是border（!!!) 算法预处理：为了将偶回文串的处理方式与奇回文串统一起来，将 S...

AC自动机 AC 自动机= Trie + KMP AC 自动机基于Trie，将KMP 的Border 概念推广到多模式串上。 AC 自动机是一种离线型数据结构，即不支持增量添加新的字符串。 AC 自动机常用于将字符串询问类的问题进行离线处理，也经常与各种 DP 结合，或是补全成Trie 图。 广义border 1.推广到两个串：对于两个串S 和T，相等的p 长度的S 的后缀和T 的前缀称为一个border。 2.推广到一个字典：对于串S 和一个字典D，相等的p 长度的S 的后缀，和任意一个字典串T 的前缀称为一个border。 3.失配（Fail）指针： 对于Trie 中的每一个节点（即某个字典串的前缀），它与Trie 中所有串的最大Border...

Border树 对于一个字符串S，n = |S|，它的Border 树（也叫next 树）共有n+1 个节点：0, 1, 2, . . . , n。 0 是这棵有向树的根。对于其他每个点1 ≤ i ≤ n，父节点为next[i]。 123456789101112131415161718192021222324252627struct KMP { vector<int> nxt; string tt; int len; KMP() {} KMP(string t) { len = t.size(); t = " " + t; tt = t; nxt.resize(len + 1); nxt[1] = nxt[0] = 0; init(tt); } void init(string t) { for (int i = 2; i <= len;...

Trie三战含板子 字典：一个字符串的集合称为字典。 字典串：在字典里的串称为字典串。 在处理字符串的时候，常会遇到这样的简单问题：给出一个字典，然后回答大量询问：输入一个字符串，判断它是否在字典中。 Trie 是一棵有根树，每个点至多有 |Σ| 个后继边，每条边上有一个字符。 每个点表示一个前缀：从跟到这个点的边上的字符顺次连接形成的字符串。 每个点还有一个终止标记：是否这个点代表的字符串是一个字典串。可以支持向 Trie 插入新字典串，删除字典串，查询某字符串是否是字典串，以及一些稍微复杂的查询。作为一个数据结构，它理所应当的还可以进行持久化。 这是一份处理小写字母字符串 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051int id(char c) {//给出现的字符集编码，记得改offset部分 if (c >= 'a' && c <=...

高斯消元 1.高斯消元解线性方程组。这个模板只处理n方程n个未知数的，分别处理无解，无穷多解，以及唯一解的情况。结果存在最后一列中（一开始的常数项）， 无解返回0 唯一解返回1 无穷多解返回2 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657int gauss(vector<vector<db>>& a, int n) { int r = 1; // 当前行 for (int c = 1; c <= n; c++) { // 消元进行到第c列 // 1.找到c列的最大行t int t = r; for (int i = r; i <= n; i++) if (fabs(a[i][c]) > fabs(a[t][c])) ...

N≤400，所有 0≤aij<1e9+7 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647const int N=405,P=1e9+7;int n;LL a[N][N<<1];LL quickpow(LL a, LL b){ LL ans = 1; while(b){ if(b & 1) ans = ans*a%P; a = a*a%P; b >>= 1; } return ans;}bool Gauss_Jordan(){ for(int i=1;i<=n;++i){ //枚举主元的行列 int r = i; for(int k=i; k<=n; ++k) //找非0行 if(a[k][i]) {r=k; break;} if(r!=i)...

线性基 解决异或问题除了字典树，剩下很常用的就是线性基。理解线性基的作用就是极大线性无关向量组，只不过在线代中我们一般讨论的是线性加减运算，而在竞赛中往往是异或运算。 对于一个向量能不能在当前的基中表示，也就是它能不能被基的某个子集异或出来，那我们如何简单高效的判断呢。首先最暴力的是直接按位拆开，高斯消元，对于每一列，也就是每一位只保留1行有1. 设原集合为S,线性基为B。线性基的性质： B是极小的满足线性基性质的集合，它的任何真子集都不可能是线性基；B是线性无关的 S中的任意元素都可以唯一表示为 中若干个元素异或起来的结果。 直接给出最优算法： 设集合 S中最大的数在二进制意义下有 L位，我们使用一个 大小为Ld的a数组 来储存线性基。 首先，线性基是动态构造的，我们只需要从空的a 开始，每次考虑在一个已存在的线性基中插入一个数t 即可。 从 t最高位上的 1开始考虑，设这是第 j位. 如果这一位已经存在于线性基中，则我们需要将t 中的这一位消掉（将 t异或上 aja_{j}aj​），才可以继续插入（因为只有 aja_{j}aj​ 的第 j位可以为...