二维前缀和 正常来说，我们处理二维前缀和需要开一个二维数组a[N][N]，然后对于覆盖区间(x1, y1)(左下角)到(x2, y2)(右上角)      a   [   x   1   −   1   ]   [   y   1   −   1   ]   +   +   ;    a[x1 - 1][y1 - 1] ++;   a[x1−1][y1−1]++;      a   [   x   1   −   1   ]   [   y   2   ]   −   −   ;    a[x1 - 1][y2] --;   a[x1−1][y2]−−;      a   [   x   2 ...

## 后缀数组(suffix array) 求的是每个后缀的排名，我们可以使用倍增法跟DC3,前者时间复杂度O(nlogn),后者O(n) 本文只考虑倍增法 然后我们定义了一些数组 sa[i]: 排名为i的后缀的位置 tp[i]: 第二关键字，性质同sa[i] rak[i]: 第i个后缀的排名 tax[i]: 排序是需要用到的桶(基数排序) 排序部分 void Qsort() { for(int i = 0; i <= m; i ++) tax[i] = 0; for(int i = 1; i <= n; i ++) tax[rak[i]] ++; for(int i = 1; i...

我们在树状数组中可以遇到lowbit这个函数，他的用处是找最低位1的，一般写成(x & -x)形式。 原理 我们知道在计算机中二进制是以补码存储的。 对于x(x>0),我们知道他的补码就是他的本身，但-x怎么求呢 对于整数x,     [   x    ]   补    =    2    n   +   1     −   ∣   x   ∣    [x]_补=2^{n+1} - |x|   [x]补​=2n+1−∣x∣,n为x的二进制最高位 设     x   =   26   ,   [   x    ]   补    =   011010   (   B   )    x...

二次剩余 形如:       x   2    ≡   d   (    m   o   d    p   )    {x^2} \equiv d \pmod p   x2≡d(modp) ,d为模p意义下的二次剩余 本文讨论的是p为质数的二次剩余 在数学中有个勒让德符号，判断是否是二次剩余      (    n   p    )   =    {     <mstyle displaystyle="true" scriptlevel="0">   1  <mtext>   </mtext>  (   n   是  ...

Codeforces Round #579 (div3) A 由于数据范围很小，我们可以直接枚举每个点，然后在向两边遍历去匹配 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; int main() { ios::sync_with_stdio(false); int t; cin >> t; while(t --) { int n; cin >> n; int a[300]; for(int i = 0; i ...

简介 ac自动机是一种有确定限状态自动机 大众的理解就是在字典树上跑kmp 前置知识点 kmp, 字典树 正题 我们知道kmp是模式串与文本串进行匹配的算法，即两个串之间匹配。那我们思考这样一个问题。如果模式串有多个，文本串有一个，如何算出每个模式串在文本串上的匹配。按原有思维，我们需要对每个模式串与文本串进行一次kmp，这样的话，时间复杂度就很高了。 于是乎，树上看毛片 横空出世 ac自动机首先将我们要匹配的所有模式串建成了一个字典树。然后在字典树上连接fail边，也就是fail指针。fail指针指向的是当前点所在模式串的所有后缀与整个字典树的所有前缀的最长的位置。有点绕口。  上图中所有有...

2019河北省大学生程序设计竞赛（重现赛）Ｂ 我们假设有一个等比数列: a[n] = q ^ n 那么 S[n] = q ^ 1 + q ^ 2 + q ^ 3 …… + q ^ n 正常情况我们有 S[n] = q * (1 - q ^ n) / (1 - q) 若我们需要求的是 S[n] % mod 且 (1 - q)与ｍod不互质，那么上面的公式便会有问题(逆元无法确定) 这时候我们发现： 如果n为奇数: S[n] = S[n / 2] + a[(n - 1) / 2 + 1]×S[n / 2] + a[(n - 1) / 2 + 1] 如果n为偶数: S[n] = S[n / 2] +...

在使用set的前提下，std::set::lower_bound更快

我们对于每个节点建立到根节点的线段树，即我们建立一颗主席树来维护 对于每个查询，答案是query(1, x) + query(1, y) - 2 * query(1, lca(x, y)) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 1e5 + 5; struct node//主席树 { int l; int r; int val;//存的是节点个数 }T[N * 50]; struct edge {...

根据提供的类型返回相应的类型 template<typename T> void o(T x) {cout << x << endl;}  C++模板

理解 一般的我们求a^b可以跑一个for或者pow函数，这种在遇到大的数据范围很浪费时间或者存不下。 这时候就可以使用快速幂进行求解 快速幂 快速幂使用了二进制的思想，假如b=11 二进制 1011 快速幂的作用就是给1与1之间的距离缩短了 int p_pow(int a,int b,int mod) { int c=1; while(b) { if(b&1)c=(c*a)%mod; a=(a*a)%mod; b>>=1; } return c; }

简介 唯一分解定理是数论中重要的思想之一。简述就是一个大于一的整数N,可以由他的素因子唯一构成。证明用到了反证法。 数学 假设N是大于一的正整数，我们有： N=q1^p1*q2^p2*……*qn^pn  q1……qn是N的质因数 有如下性质：  1. 约数个数 = (p1+1)*(p2+1)*……*(pn+1) 2. 约数和 = (1+q1+……+q1^p1)*(1+q2+……+q2^p2)*……*(1+qn+……+qn^pn)  质因数分解 for(int i=2;i*i<=n;i++) { if(n%i==0) { a[k++]=i;//将素因数存在数组中 while(n%i==0)...

##素数## 素数即质数，只能被自身和一整除。 一般暴力找素数，O(n2)或者O(nsqrt(n)) 这样耗费时间太多，所以我们用筛法来处理 ##素数筛## 素数筛通过将非素数筛掉来找素数，是重要的数论工具 ###一般筛法### --埃氏筛 一般筛法接近O（n）的复杂度，但比快速筛慢 bool mark[Max];//标记是否为素数 int ss[Max];//将素数存入数组 void prime()//筛法 { memset(mark,0,sizeof(mark); int tot=0; for(int i=2;i<Max;i++) { if(!mark[i]) { ss[tot++]...