快速幂

LL pow(LL a, LL n, LL p)    //快速幂 a^n % p
{
    LL ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;          //若不取模就去掉p
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

线性质数筛

const int N=1e9+5;
int a[N],b[N];
void prime(int n)
{
	int k=1;
	for(int i=2;i<=n;i++)
	{
		if(!a[i])
		{
			b[k++]=i;
		}
		for(int j=1;j<=k&&i*b[j]<=n;j++)
		{
			a[i*b[j]]=1;
			if(i%b[j]==0)
			break;
		}
	}
}

组合数

//简易版
void comb(int n)
{
	c[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=100;j++)
		{
			if(i==j)
			c[i][j]=1;
			else if(j==1)
			c[i][j]=i;
			else
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	}
}

//gcd版
typedef long long LL;
LL gcd(LL a,LL b)
{
	return b==0 ? a : gcd(b,a%b);
}
LL comb(LL n,LL k)
{
	if(k*2>=n)
	k=n-k;
	LL a=1,b=1;
	for(LL i=1;i<=k;i++)
	{
		a=a*(n-i+1),b*=i;
		LL g=gcd(a,b);
		a/=g,b/=g;
	}
	return a/b;
}

卢卡斯定理（最快）

【模板】卢卡斯定理 [P3807]

#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,P,T,jc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
    Re s=1;
    while(k){
        if(k&1)s=(LL)s*x%P;
        x=(LL)x*x%P,k>>=1;
    }
    return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline int C(Re m,Re n){
    return m>n?0:(LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;
}
inline int Lucas(Re m,Re n){
    return m==0?1:(LL)Lucas(m/P,n/P)*C(m%P,n%P)%P;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(T);
    while(T--){
        in(n),in(m),in(P),jc[0]=1;
        for(Re i=1;i<=P-1;++i)jc[i]=(LL)jc[i-1]*i%P;
        printf("%d\n",Lucas(n,n+m));
    }
}

二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

逆序数（树状数组）

逆序对 [P1908]

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=500050;
int n;
long long c[N];      //c[n]表示a[1~n]的和，a数组省略
struct node
{
    int val,pos;
}a[500005];

int lowbit(int x)       //求2^k
{
    return x & -x;
}

long long getsum(int n)   //区间查询，求a[1~n]的和
{
    long long res = 0;
    while(n>0)
    {
        res+=c[n];
        n=n-lowbit(n);
    }
    return res;
}

int change(int x)  //单点更新，将c[x]的值加1
{
     while(x<=n)
     {
         c[x]++;
         x+=lowbit(x);
     }
}

bool cmp(node a,node b)         //包含相同数
{
    if(a.val!=b.val)
        return a.val>b.val;
    return a.pos>b.pos;
}

int main()
{
    std::ios::sync_with_stdio(false);
    while(cin>>n)
    {
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].val;
            a[i].pos=i;
        }
        sort(a+1,a+n+1,cmp);
        long long cnt=0;
        for(int i=1;i<=n;i++)
        {
            change(a[i].pos);                     //修改最大数位置的值
            cnt+=getsum(a[i].pos-1);     //最大数位置之前的所有位置和，即区间求和，可知比当前数小的数有多少个
        }
        cout<<cnt<<endl;
    }
    return 0;
}

最长上升子序列【LIS】

int main(){
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			scanf("%d",&num[i]);
		}
		
		dp[0]=inf;
		int cnt=0;
		for(int i=1;i<=n;i++){
			if(dp[cnt]>=num[i]){
				cnt++;
				dp[cnt]=num[i];
			}
			else {
				int t=upper_bound(dp+1,dp+cnt+1,num[i],cmp)-dp;//最长非递增子序列 (可重复) 
				dp[t]=num[i];
			}
		}
		cout<<cnt<<endl;
		
		dp[0]=0;
		cnt=0;
		for(int i=1;i<=n;i++){
			if(dp[cnt]<num[i]){
				cnt++;
				dp[cnt]=num[i];
			}
			else {
				int t=lower_bound(dp+1,dp+cnt+1,num[i])-dp;//最长严格递增子序列 
				dp[t]=num[i];
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}

最长公共子序列【LCS】

    int l1,l2;
    char s1[N],s2[N];
    scanf("%d%d",&l1,&l2);
    scanf("%s%s",s1,s2);
    for(int i=0;i<l1;i++)
        for(int j=0;j<l2;j++)
            if(s1[i]==s2[j])
                dp[i+1][j+1]=dp[i][j]+1;
            else
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
     printf("%d\n",tmp[l1][l2]);

先就这么多，慢慢更新。。。