1. 快速幂模板
虽然前面可能写过了，但是遇到了就再贴一下。
LL qmi(LL a,LL k,LL p){
LL res = 1%p;
while(k){
if(k & 1) res = res * a % p;
a = a * a % p;
k = k>>1;
}
return res;
}
2. 最大子段和
给一个数组 ， 求其中元素总和最大的一个子段，子段不能为空
做法是使用一个tmp记录区间的元素总和。如果总和小于等于0，那么当前面没有选过，因为是负贡献。因为字段不能为空，所以从当前遍历的这个元素开始算起的区间。每次遍历改变一次tmp。每次遍历最后，维护一下区间的最大值。
void solve(){
int n;
cin>>n;
int tmp=0;
int ans=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(i == 1) ans = x;//因为至少要有一个
tmp = tmp<=0?0:tmp;//如果目前小于0那么就当前面没有选过。
tmp+=x;//选择当前这个
ans = max(tmp,ans);//能保证至少选择一个
}
cout<<ans<<endl;
}
3. 集合求和
给定一个集合，求它所有子集的元素的和
找规律
比如一个集合有3个元素{1，2，3}
那么它的子集有：空，{1} {2} {3} {1,2} {2,3} {1,3} {1,2,3}
发现什么呢？每一个元素被重复了4次。实际上我们找多几个例子可以发现，个数p = 2(n-1); 那么求和不就简单了，ans = sum * p
4. 逆序对
P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
其实写这个的意义是通过逆序对来了解归并排序的原理
查找资料得知
归并排序是建立在归并操作上的一种有效的排序算法,该算法采用的是分治法（二分法），时间复杂度为O(nlogn)
步骤是：
- 将一个序列进行二分，直到分解成n个独立的元素。l==r
- 将已经有序的子序列合并 因为我们直到二分到最后的时候，每个子序列都是一个独立的元素，所以它一定是有序的。从而得到完整的 有序序列。其中在合并的过程中，就可能产生逆序对的情况。我们每次都是将一段a[l ~ r]分成两个序列，a[l , mid] , a[mid+1 , r]，其中每一个数组都是有序的，我们的 任务是将他们排好序放在临时数组b中，结束后再将这段b付给a的对应区间。在这个过程中，出现了a[i] > a[j]的情况，又因为i<j所以就出现了一个逆序对的情况，但是因为数组是有序的，所以i后面到mid这一段的都是对于a[j]是逆序对。所以一次就ans+=mid-i+1，然后将a[j]放入b[t],t++，else 就放a[i]进b[t]呗，原理相同。最后将两段没有放完的都放到b中，先放i的再放j的就好了。
- 最后将b[]放入a[l ，r]中，完成一轮排序。
int n, a[5000001], b[5000001];
long long ans;
void gbsort(int l,int r){
int mid = l+r >>1;
if(l == r){
return;
}
else {
gbsort(l,mid);
gbsort(mid+1,r);
}
int i = l;
int j = mid+1;
int t = l;
while(i<=mid && j<=r){ //事实上i~mid 和 j~r都是排好序了的
if(a[i] > a[j]){ //确定i是小于j的，那么就出现逆序对了
ans += mid-i+1;
b[t++] = a[j];
j++;
}
else {
b[t++] = a[i];
i++;
}
}
while(i<=mid){//处理剩下的没有放入b[]的，一般原因都是太大了。
b[t++] = a[i];
i++;
}
while(j<=r){
b[t++] = a[j];
j++;
}
for(int i=l;i<=r;i++){ //将对应区间的有序序列b赋到a中
a[i] = b[i];
}
return;
}
5. 分治
分治就是将一个问题分解成多个相似的子问题，各自解决，然后再将答案汇总到一起得到最终的答案。
典型的例子就是快速排序和归并排序。归并上一个例子讲过了。
经典例题：
[P2345 USACO04OPEN] MooFest G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一般分治能达到 x*logn的复杂度。
等待更新。还没整明白