快速幂

#include<bits/stdc++.h>
using namespace std;
int quick_pow(int a, int n)
{
    int res = 1;
    while (n > 0)
    {
        if (n % 2 == 1) res *= a;
        a = a * a;
        n>>=1;
    }
    return res;
}
int main()
{
    cout << quick_pow(2, 14);
    return 0;
}
​

Floyed

时间复杂度：O (N³)，适用于小规模图（N ≤ 500）

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int dist[N][N];
void Floyed()
{
    for (int k = 0;k < N;k++)
    {
        for (int i = 0;i < N;i++)
        {
            for (int j = 0;j < N;j++)
            {
                dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
            }
        }
    }
}
​

组合数

1. 时间复杂度：O(N^2)

2. 空间复杂度：O(N^2)

   #include<bits/stdc++.h>
   using namespace std;
   const int N = 10000;
   int ca[N+1][N+1];
   void CA()
   {
       for (int i = 0;i <= N;i++)
       {
           for (int j = 0;j <= i;j++)
           {
               if (j == 0) ca[i][j] = 1;
               else ca[i][j] = ca[i - 1][j - 1] + ca[i - 1][j];
           }
       }
   }
   int main()
   {
       CA();
       for (int i = 1;i <= 100;i++)
       {
           for (int j = 0;j <= i;j++)
           {
               cout << ca[i][j] << " ";
           }
           cout << endl;
       }
       return 0;
   }
   
   

全错位

时间复杂度为 ：O(n)

#include<bits/stdc++.h>
using namespace std;
const int N = 10000;
int f[N];
void cuowei()
{
    f[1] = 0;
    f[2] = 1;
    for (int i = 3;i <N;i++)
    {
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
    }
}
int main()
{
    cuowei();
    for (int i = 1;i <= 15;i++)
    {
        cout << f[i] << endl;
    }
    return 0;
}

线性筛

时间复杂度为 ：O(n)

#include <bits/stdc++.h>
using namespace std;
#define N 1000000
bool isprime[N];
int p[N],cnt=0;
void linear_sieve()
{
    //先把所有的数都初始化为质数
    for (int i = 2;i < N;i++) isprime[i] = true;
​
    //线性筛
    for (int i = 2;i < N;i++)
    {
        if (isprime[i]) p[++cnt] = i;
        
        for (int j = 1;i * p[j] < N && j <= cnt;j++)
        {
            isprime[i * p[j]] = false;
            if (i%p[j] == 0) break;
            //保证每个合数被最小的质数筛除一次
            //当 i % p[j] == 0 时，说明 p[j] 是 i 的最小质因数。
            //此时，i* p[j + 1] 的最小质因数仍然是 p[j]（因为 p[j] 是 i 的因数），但线性筛要求每个合数由其最小质因数筛除。
            //如果继续筛除 ,那么 i* p[j + 1] 将被 p[j + 1] 筛除，而不是被其真正的最小质因数 p[j] 筛除，这会导致重复筛除。
        }
    }
}
int main()
{
    linear_sieve();
    for (int i = 1;i <=cnt;i++)
    {
        cout << p[i] << endl;
    }
    return 0;
}

卡特兰数

#include<bits/stdc++.h>
using namespace std;
const int N = 10000;
int f[N];
void cantland()
{
    f[0] = f[1] = 1;
    for (int i = 2;i < N;i++)
    {
        for (int j = 0;j < i;j++)
        {
            f[i] += f[j] * f[i - 1 - j];
        }
    }
}
int main()
{
    cantland();
    for (int i = 1;i <= 15;i++)
    {
        cout << f[i] << endl;
    }
    return 0;
}