算法基础

高精度

高精度加法

#include <bits/stdc++.h>
using namespace std;
const int N = 550;
vector<int> add(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lena = a.length(), lenb = b.length();
    int len = max(lena, lenb);
    vector<int> res(len + 1);
    for (int i = 0; i < len; i++) {
        res[i] += i < lena ? a[i] - '0' : 0;
        res[i] += i < lenb ? b[i] - '0' : 0;
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    string a, b;
    cin >> a >> b;
    vector<int> res = add(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度减法

#include <bits/stdc++.h>
using namespace std;

vector<int> sub(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lena = a.length(), lenb = b.length();
    int len = max(lena, lenb);
    vector<int> res(len + 1);
    for (int i = 0; i < len; i++) {
        res[i] += i < lena ? a[i] - '0' : 0;
        res[i] -= i < lenb ? b[i] - '0' : 0;
        if (res[i] < 0) {
            res[i + 1]--;
            res[i] += 10;
        }
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    string a, b;
    cin >> a >> b;
    vector<int> res = sub(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度乘法

#include <bits/stdc++.h>
using namespace std;

vector<int> mul(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lena = a.length(), lenb = b.length();
    vector<int> res(lena + lenb + 1);
    for (int i = 0; i < lena; i++) {
        for (int j = 0; j < lenb; j++) {
            res[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }
    for (int i = 0; i + 1 < res.size(); i++) {
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;
    vector<int> res = mul(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度乘低精度

#include <bits/stdc++.h>
using namespace std;

vector<int> mul(string a, int b) {
    reverse(a.begin(), a.end());
    int lena = a.length();
    vector<int> res(lena);
    for (int i = 0; i < lena; i++) {
        res[i] = b * (a[i] - '0');
    }
    for (int i = 0; i + 1 < res.size(); i++) {
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (res.back() > 10) {
        int x = res.back();
        res.back() = x % 10;
        res.push_back(x / 10);
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> res = mul(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度除以低精度

#include <bits/stdc++.h>
using namespace std;

vector<int> div(string a, int b) {
    int lena = a.length();
    vector<int> res;
    long long x = 0;
    for (int i = 0; i < lena; i++) {
        x = x * 10 + (a[i] - '0');
        if (!res.empty() || x / b > 0) {
            res.push_back(x / b);
        }
        x %= b;
    }
    if (res.empty()) res.push_back(0);
    return res;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> res = div(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度除法

#include <bits/stdc++.h>
using namespace std;
struct BigInt {
    vector<int> d;

    BigInt() {}

    BigInt(const string& s) {
        for (int i = s.size() - 1; i >= 0; i--) {
            d.push_back(s[i] - '0');
        }
    }

    void trim() {
        while (d.size() > 1 && d.back() == 0) d.pop_back();
    }

    friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] += b[i];
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator-(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len, 0);
        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] -= b[i];
            if (c[i] < 0) {
                c[i] += 10;
                c[i + 1]--;
            }
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator*(const BigInt& lhs, int b) {
        BigInt res;
        const vector<int>& a = lhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        int len = lena;
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            c[i] += a[i] * b;
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c[len] >= 10) {
            c.push_back(c[len] / 10);
            c[len++] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    bool operator<(const BigInt& b) const {
        if (d.size() != b.d.size()) return d.size() < b.d.size();
        for (int i = d.size() - 1; i >= 0; i--)
            if (d[i] != b.d[i]) return d[i] < b.d[i];
        return false;
    }

    friend istream& operator>>(istream& is, BigInt& x) {
        string s;
        is >> s;
        x = BigInt(s);
        return is;
    }
    friend ostream& operator<<(ostream& os, const BigInt& x) {
        for (int i = x.d.size() - 1; i >= 0; i--) {
            os << x.d[i];
        }
        return os;
    }
};

pair<BigInt, BigInt> divmod(BigInt A, BigInt B) {
    BigInt Q, R("0");
    Q.d.assign(A.d.size(), 0);
    for (int i = A.d.size() - 1; i >= 0; i--) {
        R.d.insert(R.d.begin(), A.d[i]);
        R.trim();
        int q = 0;
        while (!(R < B)) {
            R = R - B;
            q++;
        }
        Q.d[i] = q;
    }
    Q.trim();
    return {Q, R};
}

int main() {
    BigInt a, b;
    cin >> a >> b;
    auto [c, d] = divmod(a, b);
    cout << c << endl;
    cout << d << endl;
    return 0;
}

压位高精度乘法

高精度乘法加强版

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 5000;
const int w = 9;
const int base = 1000000000;
vector<int> mul(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() + 1);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            // 避免爆long long
            ll now = c[i + j] + 1LL * a[i] * b[j];
            c[i + j] = now % base;
            c[i + j + 1] += now / base;
        }
    }
    for (int i = 0; i + 1 < c.size(); i++) {
        c[i + 1] += c[i] / base;
        c[i] %= base;
    }
    // 去掉前导0
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
int calc(const vector<int>& a, int k) {
    int x = a[k / w];
    for (int i = 0; i < k % w; i++) {
        x = x / 10;
    }
    return x % 10;
}
int main() {
    string a, b;
    cin >> a >> b;
    // 翻转
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    // 压位
    vector<int> va, vb;
    for (int i = 0; i < a.size(); i += w) {
        int x = 0;
        for (int j = i + w - 1; j >= i; j--) {
            x = x * 10 + (j < a.size() ? a[j] - '0' : 0);
        }
        va.push_back(x);
    }
    for (int i = 0; i < b.size(); i += w) {
        int x = 0;
        for (int j = i + w - 1; j >= i; j--) {
            x = x * 10 + (j < b.size() ? b[j] - '0' : 0);
        }
        vb.push_back(x);
    }
    vector<int> c = mul(va, vb);
    // 输出补0
    printf("%d", c.back());
    for (int i = (int)c.size() - 2; i >= 0; i--) {
        printf("%09d", c[i]);
    }
    return 0;
}

重载运算符写法

#include <bits/stdc++.h>
using namespace std;
struct BigInt {
    vector<int> d;

    // 默认构造函数
    BigInt() {}

    // 用 string 构造
    BigInt(const string& s) {
        for (int i = s.size() - 1; i >= 0; i--) {
            d.push_back(s[i] - '0');
        }
    }

    // 用 int 构造，需要是非负整数
    BigInt(int x) {
        if (x == 0) {
            d.push_back(0);
            return;
        }
        while (x > 0) {
            d.push_back(x % 10);
            x /= 10;
        }
    }

    // 重载加法运算符
    friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] += b[i];
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    // 重载减法运算符
    friend BigInt operator-(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len, 0);
        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] -= b[i];
            if (c[i] < 0) {
                c[i] += 10;
                c[i + 1]--;
            }
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator*(const BigInt& lhs, int b) {
        BigInt res;
        const vector<int>& a = lhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        int len = lena;
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            c[i] += a[i] * b;
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c[len] >= 10) {
            c.push_back(c[len] / 10);
            c[len++] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator*(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        int lenb = b.size();
        int len = lena + lenb + 1;
        c.resize(len, 0);

        for (int i = 0; i < lena; i++) {
            for (int j = 0; j < lenb; j++) {
                c[i + j] += a[i] * b[j];
            }
        }
        for (int i = 0; i + 1 < len; i++) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator/(const BigInt& lhs, int b) {
        BigInt res;
        const vector<int>& a = lhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        long long rem = 0;
        for (int i = lena - 1; i >= 0; i--) {
            rem = rem * 10 + a[i];
            if (!c.empty() || rem / b > 0) {
                c.push_back(rem / b);
            }
            rem %= b;
        }
        if (c.empty()) c.push_back(0);
        reverse(c.begin(), c.end());
        return res;
    }

    // 重载输出流运算符
    friend ostream& operator<<(ostream& os, const BigInt& x) {
        for (int i = x.d.size() - 1; i >= 0; i--) {
            os << x.d[i];
        }
        return os;
    }
};

int main() {
    string a;
    int b;
    cin >> a >> b;
    BigInt A = a;
    BigInt C = A / b;
    cout << C << endl;
    return 0;
}

题目

• 麦森数（重制版 mini） 用 $\log 10$ 计算位数

• 麦森数（重制版） 快速幂+固定长度的高精度乘法

• 麦森数（重制版 Pro） 快速幂+压位高精度

• 组合数计算 0

• 【SDOI2009】SuperGCD

排序算法

基础排序算法

插入排序

插入排序（代码填空）

#include <vector>
using namespace std;

void insertion_sort(vector<int> &a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

冒泡排序

冒泡排序（代码填空）

#include <vector>
using namespace std;

void bubble_sort(vector<int> &a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

选择排序

选择排序（代码填空）

#include <vector>
using namespace std;

void selection_sort(vector<int> &a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[k]) {
                k = j;
            }
        }
        if (i != k) {
            swap(a[i], a[k]);
        }
    }
}

计数排序

计数排序（代码填空）

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

// 计数排序函数
void counting_sort(vector<int>& a) {
    if (a.empty()) return;

    // 找到数组中的最大值
    int maxv = a[0];
    for (int i = 1; i < a.size(); i++) {
        maxv = max(maxv, a[i]);
    }

    // 创建计数数组并初始化
    vector<int> count(maxv + 1, 0);

    // 统计每个元素的出现次数
    for (int i = 0; i < a.size(); i++) {
        count[a[i]]++;
    }

    // 根据计数数组重新排序
        int idx = 0;
    for (int i = 0; i <= maxv; i++) {
        while (count[i] > 0) {
            a[idx++] = i;
            count[i]--;
        }
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<int> a;
        for (int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            a.push_back(x);
        }
        counting_sort(a);
        for (int i = 0; i < n; i++) {
            printf("%d%c", a[i], (i == n - 1) ? '\n' : ' ');
        }
    }
    return 0;
}

基数排序

最后的排序

[!warning] TODO

添加算法解释

#include <vector>
using namespace std;

void my_sort(vector<int> &a) {
	const int base = 65536;
    int n = a.size();
    vector<int> b(n);
    vector<int> c(base, 0);
    for (int exp = 1; exp <= base; exp *= base) {
        for (int i = 0; i < a.size(); i++) {
            c[a[i] / exp % base]++;
        }
        for (int i = 1; i < base; i++) {
            c[i] += c[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            b[--c[a[i] / exp % base]] = a[i];
        }
        swap(a, b);
        for (int i = 0; i < base; i++) {
            c[i] = 0;
        }
    }
}

排序题目

反向字典

归并排序

二路归并

[!info] 二路归并

给两个按非降序排列的整数数组 a 和 b。你需要将它们合并成一个数组，使合并后的数组同样按非降序排列。

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

vector<int> merge(const vector<int>& a, const vector<int>& b) {
    vector<int> c;
    int n = a.size(), m = b.size();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) {
            c.push_back(a[i++]);
        } else {
            c.push_back(b[j++]);
        }
    }
    while (i < n) {
        c.push_back(a[i++]);
    }
    while (j < m) {
        c.push_back(b[j++]);
    }
    return c;
}

[!question] 思维拓展

K 路合并怎么做？

归并排序思路

归并排序（代码填空）

例子：

初始数组：[8, 4, 5, 7, 1, 3, 6, 2]

分：
[8, 4, 5, 7]      [1, 3, 6, 2]
[8, 4]  [5, 7]    [1, 3]  [6, 2]
[8] [4]  [5] [7]  [1] [3]  [6] [2]

治：
[4, 8]  [5, 7]    [1, 3]  [2, 6]
[4, 5, 7, 8]      [1, 2, 3, 6]
[1, 2, 3, 4, 5, 6, 7, 8]

#include <cstdio>
#include <iostream>
using namespace std;

int a[100005], b[100005];

void merge_sort(int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int p1 = l, p2 = mid + 1, p = l;
    while (p1 <= mid && p2 <= r) {
        if (a[p1] <= a[p2]) {
            b[p++] = a[p1++];
        } else {
            b[p++] = a[p2++];
        }
    }
    while (p1 <= mid) {
        b[p++] = a[p1++];
    }
    while (p2 <= r) {
        b[p++] = a[p2++];
    }
    for (int i = l; i <= r; i++) {
        a[i] = b[i];
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        merge_sort(0, n - 1);
        for (int i = 0; i < n; i++) {
            printf("%d%c", a[i], (i == n - 1) ? '\n' : ' ');
        }
    }
    return 0;
}

归并排序应用

逆序对(Inversion Pair)

[4, 5, 7, 8]      [1, 2, 3, 6]

比如比较 (5, 2) 时，发现有三个逆序对需要统计 (5, 2), (7, 2), (8, 2)

答案需要加上 $mid-p1+1$

[!question] 易错辨析

为什么不是加上 $p2-mid$，统计 (5, 1), (5, 2) ？

int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int p1 = l, p2 = mid + 1, p = l;
while (p1 <= mid && p2 <= r) {
    if (a[p1] <= a[p2]) {
        b[p++] = a[p1++];
    } else {
        ans += mid - p1 + 1;  // 只需要加这一行
        b[p++] = a[p2++];
    }
}

快速排序

Partition

[!info] Partition

给一个数组 nums，要求把其中小于等于 0 的元素放到前面，把大于 0 的元素放到后面，内部顺序不做要求。答案为不唯一，返回任意一个合法解即可。

void partition(vector<int>& nums) {
	int left = 0, right = 0;
    while (right < nums.size()) {
        if (nums[right] <= 0) {
            swap(nums[left], nums[right]);
            left++;
        }
        right++;
    }
}

快速排序

快速排序（代码填空）

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    // 选取某个元素作为基准值（pivot）
    // 遍历这段区间，把小于等于 pivot 的元素放到左侧
    // 最后把 pivot 放到正确位置，返回它的索引
	swap(arr[rand() % (high - low + 1) + low], arr[high]);
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(arr[i++], arr[j]);
        }
    }
    swap(arr[i], arr[high]);
    return i;
}

// 快速排序
void quick_sort(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int pivotIndex = partition(arr, low, high);  // 获取 pivot 索引
    quick_sort(arr, low, pivotIndex - 1);        // 递归排序左部分
    quick_sort(arr, pivotIndex + 1, high);       // 递归排序右部分
}

如果每次都选第一个数作为 pivot，最坏情况是输入为 [1,2,3,4,5] 或 [5,4,3,2,1]。

快速排序最坏时间复杂度是 $O(n^2)$，平均时间复杂度是 $O(n\log n)$。

求无序数组第 k 小

查找第 K 小元素

TODO

各类排序算法的对比

稳定性：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序相同。

计数排序中的 $k$ 表示元素值范围大小，基数排序中的 $d$ 表示数位个数，$k$ 表示每个数位的取值范围大小。

基数排序的稳定性取决于底层排序算法，一般使用稳定的计数排序。

基于比较的排序：

• 插入排序、归并排序、堆排序、快速排序…

非基于比较的排序：

• 计数排序、基数排序、桶排序…

比较次数下界

[!question] 思考

4 个小球，假设他们重量各不相同，你每次可以用天平称出两个小球的轻重，想要将这 4 个小球按照重量从小到大排序，运气最差的情况下要称多少次？

一共 5 次：

• 比较 $A$ 和 $B$
• 比较 $C$ 和 $D$
• 比较 $\min (A,B)$ 和 $\min (C,D)$，确定最小值
• 比较 $\max (A,B)$ 和 $\max (C,D)$，确定最大值
• 比较中间的两个

[!question] 思考

如果改成 8 个小球，能否构造/估算出最小次数？（16 次）

决策树：将比较的执行过程抽象为一棵二叉树（每个内部节点对应一次比较；左分支代表“<”的结果，右分支代表“>”的结果），叶子节点对应一种可能的输出（即一种排序结果）。

树的深度（height）即为最坏情况下比较的次数。

一棵高度为 $h$ 的二叉树，最多拥有 $2^h$ 个叶子。因此，为了区分所有 $n!$ 种可能的输入排列，必须满足

$$2^h\ge n!\Rightarrow h\ge {\log }_2(n!)$$

从信息论的角度理解：通过比较来确定出正确的排列，完全消除这 $n!$ 种可能性中的不确定性。需要 ${\log }_2(n!)$ 次比较，每次消除一半可能。

重要结论：任意的基于比较的排序算法排序 $n$ 个元素的最坏情况运行时间的下界为 $\Omega (n\log n)$。

Note

A036604: Sorting numbers: minimal number of comparisons needed to sort n elements.

二分

整数二分

二分查找 1

二分查找 1

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000010];
int binary_search(int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", binary_search(x));
    }
}

二分查找 2

二分查找 2

求最大的 $i(0<=i<n)$ 使 $a_i<x$

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000010];
int binary_search(int x) {
    int l = -1, r = n - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (a[mid] < x) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", binary_search(x));
    }
}

二分查找 3

二分查找 3

求最小的 $i(0<=i<n)$ 使 $a_i>x$

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000010];
int binary_search(int x) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (a[mid] > x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (a[l] > x) return l;
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", binary_search(x));
    }
}

实数二分

求一元五次方程的解 求方程 $x^5+x=1$ 的根。

#include <bits/stdc++.h>
using namespace std;

int main() {
    double l = 0, r = 1;
    while (r - l > 1e-12) {
        double mid = (l + r) / 2;
        if (mid * mid * mid * mid * mid + mid < 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
    printf("%.10f\n", l);
}

二分答案

关键词：

• 最大值最小
• 答案跟某个变量之间存在单调性

题目：

• NOIP2015 跳石头

  一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。 为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

• 分配房间

• 打包

• 小木棍

• 数列分段 Section Ⅱ

倍增

快速幂

快速幂

分块思想

其实求 $a^n$ 也可以用 $O(\sqrt{n})$ 的分块。

递归版

#include <bits/stdc++.h>
using namespace std;

int power(int a, long long b, int mod) {
	if (b == 0) {
		return 1 % mod;
	}
	int x = power(a, b / 2, mod);
	if (b & 1) {
		return 1LL * x * x % mod * a % mod;
	} else {
		return 1LL * x * x % mod;
	}
}

int main() {
	long long a, b;
	int mod;
	cin >> a >> b >> mod;
	cout << power(a % mod, b, mod) << endl;
}

非递归版

#include <bits/stdc++.h>
using namespace std;

int power(int a, long long n, int mod) {
    int ans = 1 % mod;
    while (n) {
        if (n & 1) ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return ans;
}

int main() {
    long long a, b;
    int mod;
    cin >> a >> b >> mod;
    cout << power(a % mod, b, mod) << endl;
}

分块思想

其实求 $a^n$ 也可以用 $O(\sqrt{n})$ 的分块。

题目

• 慢速乘
• [NOIP 2013 提高组] 转圈游戏
• 等比数列求和

ST 算法

RMQ 问题：给定 $n$ 个数，$q$个询问，每次询问区间 $[l,r]$ 内的最大值。

时间复杂度：预处理 $O(n\log n)$，查询 $O(1)$。

注意也可以用二进制拆分的方法，将任意一个询问区间拆成 $O(\log n)$ 个区间。

模板题

HDU 5443 The Water Problem

RMQ

练习题

• 区间次大值

进阶

HDU 5726 GCD

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
int n, m;
int q[N];
int f[N][21];
unordered_map<int, ll> mp;
int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}
int calc(int l, int r) {
    int k = q[r - l + 1];
    return gcd(f[l][k], f[r - (1 << k) + 1][k]);
}
void work() {
    mp.clear();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &f[i][0]);
    }
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            // cout << i << " " << j << " " << f[i][j] << endl;
        }
    }
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x <= n) {
            // cout << "i = " << i << " x = " << x << endl;
            int g = calc(i, x);
            int l = x;
            int r = n;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (calc(i, mid) == g) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            // g: [i, x] ~ [i, r]
            mp[g] += r - x + 1;
            x = l + 1;
        }
    }
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int g = calc(l, r);
        printf("%d %lld\n", g, mp[g]);
    }
}
int main() {
    q[0] = -1;
    for (int i = 1; i < N; i++) {
        q[i] = ((i & (i - 1)) == 0) ? q[i - 1] + 1 : q[i - 1];
    }
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        printf("Case #%d:\n", cas);
        work();
    }
    return 0;
}

子序列倍数统计

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int mod = 1e9 + 7;
int n, m, q;
int f[N][18][6];
int ans[6];
inline void add(int& x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
void merge(int* c, int* a, int* b) {
    static int tmp[6];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            add(tmp[(i + j) % m], 1LL * a[i] * b[j] % mod);
        }
    }
    for (int i = 0; i <= m; i++) {
        c[i] = tmp[i];
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        f[i][0][0] = 1;
        f[i][0][x % m]++;
    }
    for (int j = 1; j <= 17; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            merge(f[i][j], f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        for (int j = 17; j >= 0; j--) {
            if (l + (1 << j) - 1 <= r) {
                merge(ans, ans, f[l][j]);
                l += 1 << j;
            }
        }
        cout << ans[0] << endl;
    }
}

倍增

stikl

题意：$n$ 个数 $a_i$，$q$次询问，每次问从下标 $x$，往右跳 $y$ 步到哪个点，每一步只能跳到下一个不小于当前的数字的位置。

$f[i][j]$ 表示节点$i$往右跳$2^j$步到达的点，初始的 $f[i][0]$ 需要用单调队列求一下。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
int n, m;
int a[N], q[N];
int f[N][20];
int main() {
    scanf("%d%d", &n, &m);
    int r = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        while (r > 0 && a[q[r]] <= a[i]) {
            f[q[r]][0] = i;
            r--;
        }
        q[++r] = i;
    }
    while (r > 0) {
        f[q[r]][0] = n + 1;
        r--;
    }
    f[n + 1][0] = n + 1;
    for (int j = 1; j <= 19; j++) {
        for (int i = 1; i <= n + 1; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    while (m--) {
        int x, d;
        scanf("%d%d", &x, &d);
        for (int i = 19; i >= 0; i--) {
            if (d >= (1 << i)) {
                d -= (1 << i);
                x = f[x][i];
            }
        }
        if (x == n + 1) {
            puts("leik lokid");
        } else {
            printf("%d\n", x);
        }
    }
}

贪心

基础

排队打水

[!info] 排队打水

有 $n$ 个人排队打水，第 $i$ 个人打水需要打 $T_i$ 分钟。请问如何安排他们打水的顺序，使得所有人等待的时间和最小。

结论：按打水时间从小到大让人打水是最小化总等待时间的最优策略。

证明用相邻交换法：任意逆序相邻对交换都能降低（或不增）总完成时间，从而最终得到非降序排列为最优。

也可以用排序不等式证明：

$$W_{\text{total}}=\sum _{i=1}^n{W}_i=\sum _{i=1}^n\sum _{j=1}^{i-1}{T}_j=\sum _{i=1}^n(n-i)\times T_i$$

神牛果

[!info] 神牛果

有 $n$ 个正整数，分成 $n/2$ 组使得 sum 最大的那组 sum 最小

奥利凡德

[!info] 奥利凡德

哈利波特在与伏地魔的战斗中毁坏了自己的魔杖，于是他决定去奥利凡德的魔杖店买个新的。他在店里看到 $n$ 个魔杖和 $n$ 个盒子，每个魔杖的长度为 $X_1,X_2,\dots ,X_n$，每个盒子的长度为$Y_1,Y_2,\dots ,Y_n$。一个长度为 $X$ 的魔杖要能放进长度为 $Y$ 的盒子里必须满足 $X<=Y$。哈利波特想知道他能否把所有的魔杖都放进盒子里，并且每个盒子只能放一根魔杖。

硬币问题

[!info] 硬币问题

有 1 元、5 元、10 元、50 元、100 元硬币各有若干枚，现在要用这些硬币支付 $n$ 元，问最少需要多少枚硬币。

反悔贪心

[!info] [CSP-S 2025] 社团招新 / club

其他

删数字 弱化版

删数字

grass 区间覆盖问题变形

kvallsfika 排序贪心

bolir n 个区间 n 个点问是否能一一匹配

回文数组

数袋鼠

前缀和&差分

前缀和

一维前缀和

前缀和（小数据）

前缀和

#include <bits/stdc++.h>
using namespace std;
#define N 200010
int n, q;
int a[N], sum[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        sum[i] = sum[i - 1] + a[i];
    }
    scanf("%d", &q);
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
}

二维前缀和

矩阵前缀和

#include <bits/stdc++.h>
using namespace std;
#define N 1010
int n, m, q;
int a[N][N], sum[N][N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    scanf("%d", &q);
    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
    }
}

[HNOI2003] 激光炸弹

一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。现在地图上有 $n$ 个目标，用整数 $x_i,y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $v_i$ 。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 $m$ 的边必须与$x$ 轴，$y$ 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。 现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。 可能存在多个目标在同一位置上的情况。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5000;
int n, m;
int val[N + 5][N + 5], sum[N + 5][N + 5];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        val[x][y] += c;
    }
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + val[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= N + 1; i++) {
        for (int j = 1; j <= N + 1; j++) {
            int now = sum[i][j] - sum[i][max(0, j - m)] - sum[max(0, i - m)][j] + sum[max(0, i - m)][max(0, j - m)];
            ans = max(ans, now);
        }
    }
    printf("%d", ans);
}

差分

区间加法

有一个长度为 $n$ 的数组 a，初始元素值都为 0。现在有 $m$ 次操作，每次给定三个参数 $l,r,x$，你需要给 a[l], a[l+1], …, a[r] 都加上 $x$。问 $m$ 次操作之后，数组的每个元素值是多少。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100010];
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        a[l] += x;
        a[r + 1] -= x;
    }
    for (int i = 1; i <= n; i++) {
        a[i] += a[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld ", a[i]);
    }
}

二维差分

扩展

结合模运算

区间计数：给一个长度为 $n$ 的数组，求有多少个区间 $[l,r](1\le l\le r\le n)$ 满足 $a_l+a_{l+1}+\cdots +a_r$ 是 $n$ 的倍数。

知识点：同余，计数

结合二分/双指针

进阶

• 每次给区间加上一个等差数列

• 菱形和

其他题目

• 加权前缀和
• 菱形和
• 语文成绩
• NOIP2012 借教室

递推

平面分割

[!info] 平面分割

用 $n$ 条直线分割平面，问最多分割出多少个区域。

答案是 $$\frac{n(n+1)}{2}+1$$

骨牌覆盖简单版

[!info] 骨牌覆盖简单版

有一个长度为 $2\times n$ 的长方形方格，用 $1\times 2$ 的骨牌完全覆盖，可横放或竖放，但不能重叠，有多少种不同的覆盖的方法。因为答案可能很大，你只需要输出答案模 $10007$ 的结果。

f = [0 for i in range(100 + 1)]
f[0] = 1
f[1] = 1
for i in range(2, 100 + 1):
    f[i] = (f[i - 1] + f[i - 2]) % 10007
n = int(input())
print(f[n])

汉诺塔问题（求步数）

[!info] 汉诺塔问题（求步数）

求汉诺塔的移动步数。

答案是 $2^n-1$。

棋盘格数

[!info] 棋盘格数

设有一个 $N\times M$方格的棋盘。求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。

记 $s=\min (n,m)$

$$\begin{array}{rl}an{s}_1& =\sum _{i=0}^{s-1}(n-i)(m-i)\\ an{s}_1& =nms-(n+m)(\sum _{i=0}^{s-1}i)+\sum _{i=0}^{s-1}{i}^2\\ an{s}_1& =nms-\left(n+m\right)\cdot \frac{s(s-1)}{2}+\frac{s(s-1)(2s-1)}{6}\end{array}$$

$$an{s}_2=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)\left(\genfrac{}{}{0ex}{}{m+1}{2}\right)-an{s}_1$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
__int128 read() {
    char s[30];
    __int128 res = 0;
    scanf("%s", s);
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        res = res * 10 + s[i] - '0';
    }
    return res;
}

void print(__int128 num) {
    if (num > 9) {
        print(num / 10);
    }
    putchar(num % 10 + '0');
}

int main() {
    __int128 n = read(), m = read();
    __int128 ans1 = 0, ans2 = 0;
    __int128 size = min(n, m);
    ans1 += n * m * size;
    ans1 -= (n + m) * size * (size - 1) / 2;
    ans1 += (size - 1) * size * (2 * size - 1) / 6;
    ans2 = n * (n + 1) * m * (m + 1) / 4 - ans1;
    print(ans1);
    cout << endl;
    print(ans2);
    return 0;
}

Neighbouring Ones

[!info] Neighbouring Ones

对于一个二进制 01 串来说，如果其中所有的 1 都有一个与它相邻的 1，那么称这个 01 串为好串。现在问长度为 $n$ 的好串有多少个，答案需要对 $1000000007$ 取模。

f = [0 for i in range(100 + 1)]
f[1] = 1
f[2] = 2
f[3] = 4
f[4] = 7
for i in range(5, 100 + 1):
    f[i] = (f[i - 1] + f[i - 2] + f[i - 4]) % 1000000007

• 第一类：末尾是 0
• 第二类：末尾是 11
• 第三类：末尾是 0111？

汉诺双塔

[!info] 汉诺双塔

$2n$个圆盘，求移动步数。

n = int(input().strip())
f = [0 for i in range(n + 1)]
f[0] = 0
for i in range(1, n + 1):
	f[i] = 2 * f[i - 1] + 2
print(f[n])

[NOIP2001 普及组] 数的计数

[!info] 数的计数

我们要求找出具有下列性质数的个数(包含输入的自然数 n): 先输入一个自然数 n(n<=1000),然后对此自然数按照如下方法进行处理: 1. 不作任何处理; 2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止。

n = int(input().strip())
f = [0 for i in range(n + 1)]
for i in range(1, n + 1):
    f[i] = 1
    for j in range(1, i // 2 + 1):
        f[i] += f[j]
print(f[n])

骨牌覆盖升级版

[!info] 骨牌覆盖升级版

有一个长度为 $3\times n$ 的长方形方格，用 $1\times 1$ 和 $2\times 2$ 的骨牌完全覆盖，要求不能重叠，问有多少种不同的覆盖的方法。因为答案可能很大，你只需要输出答案模 $1000000007$ 的结果。

#include <bits/stdc++.h>
using namespace std;
int f[1010];
int main() {
	f[1] = 1;
	f[2] = 3;
	for (int i = 3; i <= 1000; i++) {
		f[i] = (f[i - 1] + 2LL * f[i - 2]) % 1000000007;
	}
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		cout << f[n] << endl;
	}
}

覆盖墙壁

[!info] 覆盖墙壁

用 $2\times 1$ 和 L型的牌覆盖 $2\times n$ 的墙壁，有多少种不同的覆盖方法。答案取模。

递归

一般递归

汉诺塔

汉诺塔

#include <bits/stdc++.h>
using namespace std;
int cnt;
void hanoi(int n, char from, char mid, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, mid);
    ++cnt;
    cout << cnt << ".Move " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, mid, from, to);
}
int main() {
    int n;
    cin >> n;
    hanoi(n, 'a', 'b', 'c');
}

FJ 的字符串

生成递归构造的字符串

FJ 的字符串
FJ 在沙盘上写了这样一些字符串：
A1 = “A”
A2 = “ABA”
A3 = “ABACABA”
A4 = “ABACABADABACABA”
你能找出其中的规律并写所有的数列 AN 吗？

#include <iostream>
using namespace std;
string dfs(int n) {
	if (n == 1) {
		return "A";
	}
	string mid;
	mid += 'A' + n - 1;
	return dfs(n - 1) + mid + dfs(n - 1);
}
int main() {
	int n;
	cin >> n;
	cout << dfs(n) << endl;
}

其他题目

• 2 的幂次方

递归枚举

分治

基础模型

• 快速幂
• 汉诺塔
• 快速排序
• 归并排序

题目

• 小 A 的拼图
• 希尔伯特曲线
• 皮亚诺曲线距离

数论

链表

TODO

队列

• 最近的请求次数

栈

题目

• 用栈实现队列

数学

数论

素数筛

埃氏筛

筛法求素数

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
bool isp[N + 5];
int sum[N + 5];
void pre() {
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = false;
    for (int i = 2; i <= N / i; i++) {
        if (isp[i]) {
            for (int j = i * i; j <= N; j += i) {
                isp[j] = false;
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        sum[i] = sum[i - 1] + isp[i];
    }
}

int main() {
    pre();
    int t;
    scanf("%d", &t);
    while (t--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
}

[!info] 质数统计（数据加强版）

给定 $L$ 和 $R$，求出 $[L,R]$ 内质数的个数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000000;
bool isp[N + 5];
vector<int> prime;
void pre() {
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isp[i]) {
            prime.push_back(i);
        }
        for (int x : prime) {
            if (x > N / i) break;
            isp[i * x] = false;
            if (i % x == 0) break;
        }
    }
}

int main() {
    pre();
    ll l, r;
    cin >> l >> r;
    memset(isp, 1, sizeof(isp));
    for (int x : prime) {
        if (x > r / x) break;
        ll k = max(2ll, (l + x - 1) / x);
        for (ll i = k * x; i <= r; i += x) {
            isp[i - l] = false;
        }
    }
    int sum = 0;
    for (ll i = l; i <= r; i++) {
        sum += (i != 1 && isp[i - l]);
    }
    cout << sum << endl;
}

[!info] 约数和加强版

给定 $n$ 个数，分别求出他们所有约数之和。

先枚举约数，再枚举倍数，可以用 $O(N\log N)$ 时间求出所有数的约数和。证明是经典的调和级数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 10000000;
ll f[N + 5];
int main() {
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            f[j] += i;
        }
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", f[n]);
    }
}

[!info] 园艺题解

求任意两个数 $(x,y)$ 的最大公约数。

for (int d = 1; d <= n; ++d) {
    for (int a = d; a <= n; a += d) {
        for (int b = d; b <= n; b += d) {
            g[a][b] = d;
            g[b][a] = d;
        }
    }
}

对于固定的 $d$，最里层两个循环次数约为 $\frac{n}{d}\cdot \frac{n}{d}=\frac{n^2}{d^2}$。

循环总次数：

$$T(n)\approx \sum _{d=1}^n\frac{n^2}{d^2}=n^2\sum _{d=1}^n\frac{1}{d^2}$$

注意到 ${\sum }_{d=1}^n\frac{1}{d^2}$ 是一个收敛的调和级数，极限为 ${\pi }^2/6\approx 1.6449$ （巴塞尔问题）。

所以这个代码的时间复杂度是 $O(n^2)$。

线性筛

每个合数只被它的最小素因子筛一次，时间复杂度 O(n)。

const int N = 10000000;
int prime[N + 5], cnt;
bool vis[N + 5];
void getprime(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && prime[j] <= n / i; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

i * prime[j] 的素因子一定是 prime[j]。

题目：

• 最小素因子的乘积

组合数计算

给定 $n$, $m$, $P$，求 $C_n^m\mathrm{mod}P$。

组合数计算 0

不取模，数据范围 $1\le n\le 10000,0\le m\le n$

做法：高精度

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BigInt {
    vector<int> d;

    BigInt() {}
    BigInt(const string &s) { *this = s; }
    BigInt(int x) {
        d.clear();
        if (x == 0) {
            d.push_back(0);
            return;
        }
        while (x > 0) {
            d.push_back(x % 10);
            x /= 10;
        }
    }
    BigInt &operator=(const string &s) {
        d.clear();
        for (int i = s.size() - 1; i >= 0; i--) {
            d.push_back(s[i] - '0');
        }
        trim();
        return *this;
    }

    void trim() {
        while (d.size() > 1 && d.back() == 0) d.pop_back();
    }

    string str() const {
        string s;
        for (int i = d.size() - 1; i >= 0; i--) s.push_back(d[i] + '0');
        return s.empty() ? "0" : s;
    }

    friend BigInt operator+(const BigInt &a, const BigInt &b) {
        BigInt c;
        int lena = a.d.size();
        int lenb = b.d.size();
        int len = max(lena, lenb);
        c.d.resize(len + 1, 0);
        for (int i = 0; i < len; i++) {
            c.d[i] += (i < lena) ? a.d[i] : 0;
            c.d[i] += (i < lenb) ? b.d[i] : 0;
            c.d[i + 1] += c.d[i] / 10;
            c.d[i] %= 10;
        }
        c.trim();
        return c;
    }

    friend BigInt operator*(const BigInt &a, const BigInt &b) {
        BigInt c;
        int lena = a.d.size();
        int lenb = b.d.size();
        c.d.resize(lena + lenb + 1, 0);
        for (int i = 0; i < lena; i++) {
            for (int j = 0; j < lenb; j++) {
                c.d[i + j] += a.d[i] * b.d[j];
            }
        }
        for (int i = 0; i + 1 < c.d.size(); i++) {
            c.d[i + 1] += c.d[i] / 10;
            c.d[i] %= 10;
        }
        c.trim();
        return c;
    }

    friend BigInt operator*(const BigInt &a, const int &b) {
        BigInt c;
        int lena = a.d.size();
        c.d.resize(lena, 0);
        for (int i = 0; i < lena; i++) {
            c.d[i] = b * a.d[i];
        }
        for (int i = 0; i + 1 < c.d.size(); i++) {
            c.d[i + 1] += c.d[i] / 10;
            c.d[i] %= 10;
        }
        while (c.d.back() >= 10) {
            int x = c.d.back();
            c.d.back() = x % 10;
            c.d.push_back(x / 10);
        }
        c.trim();
        return c;
    }

    friend BigInt operator/(const BigInt &a, const int &b) {
        BigInt c;
        int lena = a.d.size();
        ll x = 0;
        for (int i = lena - 1; i >= 0; i--) {
            x = x * 10 + a.d[i];
            if (c.d.empty() && x / b == 0) {
                continue;
            }
            c.d.push_back(x / b);
            x %= b;
        }
        if (c.d.empty()) c.d.push_back(0);
        reverse(c.d.begin(), c.d.end());
        return c;
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    BigInt ans(1);
    for (int i = 1; i <= m; i++) {
        ans = ans * (n - i + 1);
        ans = ans / i;
    }
    cout << ans.str() << endl;
    return 0;
}

组合数计算 1

多组询问，$T\le 100000$，$1\le n\le 2000$， $0\le m\le n$，$1<P\le 10^9$

做法：递推 $$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$$ 时间复杂度 $O(N^2+T)$

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
int c[N + 5][N + 5];

int main() {
    int T, P;
    cin >> T >> P;
    c[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
        }
    }
    while (T--) {
        int n, m;
        cin >> n >> m;
        cout << c[n][m] << endl;
    }
    return 0;
}

组合数计算 2

数据范围：

$1\le n\le 10^{18}$

$0\le m\le min(10^6,n)$

$m<P<2^{31}$ 且 $P$ 是质数。

做法：

$$C_n^m=\frac{n\times (n-1)\times (n-2)\times \cdots \times (n-m+1)}{1\times 2\times 3\times \cdots \times m}$$

因为模数是质数，直接用费马小定理求乘法逆元。

时间复杂度 $O(Tm\log P)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int power(int a, ll n, int mod) {
    int res = 1;
    while (n) {
        if (n & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return res;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n;
        int m, P;
        cin >> n >> m >> P;
        if (m > n / 2) m = n - m;
        ll ans = 1;
        for (int i = 1; i <= m; i++) {
            ans = ans * ((n - i + 1) % P) % P;
            ans = ans * power(i, P - 2, P) % P;
        }
        cout << ans << endl;
    }
    return 0;
}

组合数计算 3

数据范围：

$T\le 100000$

$1\le n\le 1000000$

$0\le m\le n$

模数 $P=10^9+7$

做法：

预处理 $$fac[i]=i!\mathrm{mod}P$$ $$inv[i]=(i!{)}^{-1}\mathrm{mod}P$$

则每次询问可以做到 $O(1)$，预处理时间复杂度可以$O(N\log N)$，也可以优化到 $O(N)$。

总时间复杂度 $O(N+T)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 1e6;
int fac[N + 10], inv[N + 10];
int power(int a, ll n, int mod) {
    int res = 1;
    while (n) {
        if (n & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return res;
}
int main() {
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
    inv[N] = power(fac[N], mod - 2, mod);
    for (int i = N - 1; i >= 0; i--) inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        cout << 1LL * fac[n] * inv[m] % mod * inv[n - m] % mod << endl;
    }
    return 0;
}

组合数计算 4

数据范围：

$T\le 5$

$1\le n\le 10^{18}$

$0\le m\le n$

$1<P<10^6$ 且 $P$ 是质数。

做法：lucas 定理

$$C_n^m=C_{n/P}^{m/P}\times C_{n\mathrm{mod}P}^{m\mathrm{mod}P}\mathrm{mod}P$$

时间复杂度 $O(P\log n/\log P)$（TODO）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int power(int a, ll n, int mod) {
    int res = 1;
    while (n) {
        if (n & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return res;
}
ll com(ll n, ll m, ll p) {
    if (n < m) return 0;
    ll ans = 1;
    for (int i = 1; i <= m; i++) {
        ans = ans * ((n - i + 1) % p) % p;
        ans = ans * power(i, p - 2, p) % p;
    }
    return ans;
}

ll lucas(ll n, ll m, ll p) {
    ll ans = 1;
    while (n && m) {
        ans = ans * com(n % p, m % p, p) % p;
        n /= p;
        m /= p;
    }
    return ans;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, m, p;
        cin >> n >> m >> p;
        cout << lucas(n, m, p) << endl;
    }
    return 0;
}

组合数计算 5

数据范围：

$1\le n\le 10^7$

$0\le m\le n$

$1<P\le 10^9$。

做法：线性筛+勒让德定理+分解质因数。

时间复杂度：$O(N)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 10000000;
int prime[N + 5], cnt;
bool vis[N + 5];
void getprime(int n = N) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && prime[j] <= n / i; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

ll calc(ll n, ll p) {
    ll ans = 0;
    while (n) {
        ans += n / p;
        n /= p;
    }
    return ans;
}

int main() {
    getprime();
    int T;
    cin >> T;
    while (T--) {
        int n, m, p;
        cin >> n >> m >> p;
        int ans = 1;
        for (int i = 1; i <= cnt; i++) {
            int x = calc(n, prime[i]) - calc(m, prime[i]) - calc(n - m, prime[i]);
            for (int j = 1; j <= x; j++) {
                ans = 1LL * ans * prime[i] % p;
            }
        }
        cout << ans << endl;
    }
}

组合数计算 6

给定 $n$, $m$, $P$，求 $$C_n^0,C_n^1,C_n^2,\dots ,C_n^m$$

$n\le 10^{18}$，$m\le \min (n,1000)$，$P\le 10^9$

做法：二项式定理+卷积快速幂

$$(1+x{)}^n=\sum _{i=0}^n{C}_n^i{x}^i$$

求多项式的前 $m+1$ 项系数。

时间复杂度 $O(m^2\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
int m, p;
void add(int& x, int y) {
    x += y;
    if (x >= p) x -= p;
}
vector<int> mul(const vector<int>& a, const vector<int>& b, int m) {
    vector<int> c(m, 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; i + j < m; j++) {
            add(c[i + j], 1LL * a[i] * b[j] % p);
        }
    }
    return c;
}
int main() {
    cin >> n >> m >> p;
    m++;
    vector<int> v(m, 0);
    v[0] = v[1] = 1;
    vector<int> ans(m, 0);
    ans[0] = 1;
    while (n) {
        if (n & 1) {
            ans = mul(ans, v, m);
        }
        v = mul(v, v, m);
        n >>= 1;
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i];
        cout << (i + 1 < m ? " " : "\n");
    }
    return 0;
}

组合数计算 7

组合数学基础

广义的组合数学（Combinatorics）就是离散数学，狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。 但这只是不同学者在叫法上的区别。总之，组合数学是一门研究可数或离散对象的科学。 随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。

加法原理乘法原理

加法原理

如果事件 $A$ 有 $m$ 种产生方式，事件 $B$ 有 $n$ 种产生方式，当 $A$ 与 $B$ 产生的方式不重叠时，则事件 $A$ 或 $B$ 有 $m+n$ 种产生方式。

使用加法原理要注意事件 $A$ 和事件 $B$ 产生的方式不能重叠，即每种产生方式不能同时属于两个事件。

加法原理可以推广到 $n$ 个事件：设 $A_1,A_2,\dots ,A_n$ 是 $n$ 个事件，他们的产生方式分别有 $p_1,p_2,\dots ,p_n$ 种， 当其中任意两个事件产生的方式都不重叠时， 则事件“ $A_1$ 或 $A_2\dots$ 或 $A_n$ ”有 $p_1+p_2+\cdots +p_n$ 种产生方式。

在运用加法原理时，我们通常把问题分隔成若干穷尽所有可能的互相排斥的情况。

从北京前往上海旅游，有三种交通工具可供选择，分别为飞机、高铁、长途汽车。而飞机的班次有 $4$ 种，高铁的班次有 $6$ 种，长途汽车的班次有 $5$ 种，那么一共有：

$$4+6+5=15$$

种不同的交通方式。

乘法原理

如果事件 $A$ 有 $n$ 种产生方式，事件 $B$ 有 $m$ 种产生方式，当 $A$ 与 $B$ 产生的方式相互独立时，则事件$A$ 与 $B$有：

$$n\times m$$

种产生方式。

这里独立的意思是，事件 $A$ 与事件 $B$ 对产生方式的选择彼此没有影响。乘法原理也可以推广到 $n$ 个事件。设 $A_1,A_2,\dots ,A_n$ 是 $n$ 个事件，他们的产生方式分别有 $p_1,p_2,\dots ,p_n$ 种，当其中任何两个事件产生的方式彼此独立时，事件“$A_1$ 与 $A_2\dots A_n$”有：

$$p_1\times p_2\times \cdots \times p_n$$

种产生方式。

粉笔的长度有 $3$ 种，颜色有 $8$ 种，直径有 $4$ 种，那么一共有：

$$3\times 8\times 4=96$$

种不同的粉笔。

正因为长度、颜色、直径是相互独立的，所以才能用乘法原理。如果两个事件之间是相关的，比如一种长度对应几种直径，那就不能直接用乘法原理计算了。

练习题

加法原理乘法原理例题

[!info] 例1

在 $1000\sim 9999$ 之间，有多少个各位不相同的奇数？

首先考虑个位，因为这个数必须是奇数，所以个位有 $5$ 种选择: $1,3,5,7,9$。

再来看千位，原本的选择范围是 $1,2,3,4,5,6,7,8,9$，除去个位的选择后，剩下还有 $8$ 种选择。

再来看百位，原本的选择范围是 $0\sim 9$，除去个位和千位的选择后，只剩下 $8$ 种选择。

最后来看十位，只有 $7$ 种选择方案，因此最终答案为 $5\times 8\times 8\times 7=2240$ 种。

注意我们首先选择的是个位，然后再是千位，这是因为他们的约束性比较强。如果先选十位或者百位，你会发现就不能用乘法原理解决了（要分类讨论有没有用过 $0$ 和奇数）。所以，计算的顺序很重要。

[!info] 例2

求 $63541800$ 的约数个数为多少。

$63541800=2^3\times 3^3\times 5^2\times 7\times 41^2$

根据算术基本定理,该数的某个因数可以表示为 $2^{k_1}\times 3^{k_2}\times 5^{k_3}\times 7^{k_4}\times 41^{k_5}$。

其中 $0\le k_1\le 3$，那么 $k_1$ 有 4 种选择。同理 $k_2$ 有 4 种选择，$k_3$ 有 3 种选择，$k_4$ 有 2 种选择，$k_5$ 有 3 种选择。 那么总共的因数个数为 $4\times 4\times 3\times 2\times 3=288$ 个。

[!info] 例3

由五个数字 $7,7,7,5,3$ 可以组成多少个不同的五位数？

$3$ 可以放在五位数中的任何一位中，$5$ 可以放在剩下四个位置中的任何一位，那么剩下都是 $7$ 了只有一种放法。 一共能组成 $5\times 4=20$ 个不同的五位数。

排列数

线性排列

设 $S$ 为 $n$ 元集合，从 $S$ 中有序选取 $r$ 个元素称为 $S$ 的一个 $r$ 排列。

$S$ 的 $r$ 排列总数记作 $A_n^r$，当 $n=r$ 时称为全排列。$A_n^r$ 也称为从 $n$ 个不同的元素取 $r$ 个元素的排列数。

从 $n$ 个不同的元素取 $r$ 个元素按顺便排成一列，选择第 1 个元素可以有 $n$ 种方法，选择第 2 个元素可以有 $n-1$ 种方法，以此类推。所以 $A_n^r$ 的计算方法如下：

$$A_n^r=n(n-1)(n-2)\cdots (n-r+1)$$

这里只考虑 $n$ 和 $r$ 都是整数，且 $0\le r\le n$ 的情况，则有:

$$A_n^r=\frac{n!}{(n-r)!}$$

举个例子：用 26 个字母构成一个长度为 5 的英文单词，要求每个字母最多使用一次，那这样不同的单词个数为 $A_{26}^5=7893600$。

圆排列

刚才我们所讨论的都是把对象排成一条线，称为线性排列。如果把对象排成环形呢？这种环形的排列我们称为圆排列（也可以叫环排列，循环排列）。

有 6 个小朋友手拉手围成一个圈，编号分别为 1, 2, 3, 4, 5, 6，问有多少种不同的方案？

很显然 123456 和 234561 是同一种方案，也就是说方案数比原来 $A_6^6$ 种可能要少。再具体一点，一种圆排列对应了 6 种线性排列。

因此，$n$ 个元素的 $r$ 圆排列的数目为 $\frac{A_n^r}{r}=\frac{n!}{r\cdot (n-r)!}$。

特别地，当 $r=n$ 时，圆排列数目为 $(n-1)!$。

练习题

排列数例题

[!info] 例4

将字母表中的 26 个字母排成一行，使得元音字母 $a,e,i,o,u$ 中任意两个都不能连续出现，这样的方案数有多少？

可以先排 21 个辅音字母，这样一共有 $A_{21}^{21}$ 种排列方法。 然后把元音字母进行插空，来保证不相邻。 这样的空位一共有 22 个，然后把 5 个元音字母放进空位里。 第一个元音字母有 22 种放法，第二个元音字母有 21 种放法…… 也就是说元音字母有 $A_{22}^5$ 种方案数，那么根据乘法原理，总方案数为 $A_{21}^{21}\times A_{22}^5$ 种。

[!info] 例5

由 $1\sim 9$ 这 $9$ 个数字组成的七位数中，有多少个数满足各位数字互不相同，且数字 $5$ 和 $6$ 不连续？

暂且不考虑数字 5 和 6 不连续出现，由 1～9 组成各位数字互不相同的七位数有 $A_9^7$ 种。那么再减去一定出现 5 和 6 连续的情况，就是答案了。

5 和 6 两个数字本身的排列有 $A_2^2$ 种，在七位数中一共有 6 种放法，而剩余的数放置的方案为 $A_7^5$ 种。那么一定出现 5 和 6 连续的情况的方案数就为 $A_2^2\times 6\times A_7^5$ 种。

因此，最终答案为 $A_9^7-A_2^2\times 6\times A_7^5=151200$。

[!info] 例6

A 和 B 参加同学聚餐，一共有 $10$ 个人要围坐一张桌子。在路上 A 和 B 吵架了，因此他们不想坐在相邻的位置上，那么一共要多少种分配座位的方法？

让 A 先随便坐一个位置，那他左边有 8 个人选，右边有 7 人选，剩下的七个位置一共有 $A_7^7$ 种方案，那么一共有 $8\times 7\times A_7^7=282240$ 种方案。

也可以这么想，总共圆排列有 $9!$ 种，然后减去 A 和 B 相邻的方案数。他们两人的顺序有 $A_2^2$ 种，捆绑在一起和其他人组成的圆排列有 8! 种，那么答案为 $9!-A_2^2\times 8!=282240$ 种方案。

组合数

设 $S$ 为 $n$ 元集合，从 $S$ 中无序选取 $r$ 个元素，称作 $S$ 的一个 $r$ 组合。 $S$ 的 $r$ 组合总数记作 $C_n^r$，$C_n^r$ 也称为从 $n$ 个不同的元素取 $r$ 个元素的组合数，也可以记作 $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$，称为二项式系数。

这里只考虑 $n$ 和 $r$ 都是整数，且 $0\le r\le n$ 的情况，则有: $$C_n^r=\frac{n!}{r!(n-r)!}$$

根据上面的式子可以得出： $$C_n^r=C_n^{n-r}$$ $$A_n^r=r!\cdot C_n^r$$

举个例子：教室里有 30 个座位，进来了 10 个学生，每个人会选择坐一个座位，那么每个座位的空闲情况一共有 $C_{30}^{10}$ 种。

帕斯卡恒等式是组合数中非常重要的公式：

$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$$

尝试证明一下？

可以用组合分析的方法证明：

从 $n$ 个元素中取 $k$ 个一共有 $C_n^k$ 种取法，现在换一种角度来考虑：对于其中一个元素，如果取它，那么剩余的 $n-1$ 个元素里就要取 $k-1$ 个；如果不取它，那么剩余 $n-1$ 个元素里就要取 $k$ 个。那么总共的取法一共有 $C_{n-1}^{k-1}+C_{n-1}^k$ 种。

问题：一个包含 $n$ 个元素的集合的子集个数为多少？（一个长度为 $n$ 的数组的子序列个数有多少个？）

一个包含 $n$ 个元素的集合的子集数目为 $2^n$，因为每个元素可以取或者不取。

也可以分别统计大小为 $0,1,2,\cdots ,n$ 的子集数目，大小为 $r$ 的子集一共有 $C_n^r$ 个，那么根据加法原理，所以子集数目为 ${\sum }_{i=0}^n{C}_n^i$。

两种计算方法的结果是相等的，所以推出了一个恒等式

$$\sum _{i=0}^n{C}_n^i=2^n$$

多重集的排列组合

为了讨论允许重复的选取问题需要引入多重集合的概念。多重集合 $$S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\}$$， 其中 $a_1,a_2,\cdots a_k$ 是 $k$ 种不同的元素，$n_i$ 表示 $a_i$ 在 $S$ 中出现的次数，称为 $a_i$ 的重复度。

设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\}$ 为多重集合，元素的总数为 $n=n_1+n_2+\cdots +n_k$。

• 从 $S$ 中有序选取的 $r$ 个元素称为多重集合 $S$ 的一个 $r$ 排列。$r=n$ 的排列称为 $S$ 的全排列。

• 从 $S$ 中无序选取的 $r$ 个元素称为多重集合 $S$ 的一个 $r$ 组合。

• $S$ 的全排列个数是 $\frac{n!}{n_1!n_2!\cdots n_k!}$。

• 若 $r\le n_i,i=1,2,\cdots ,k$，那么 $S$ 的 $r$ 排列数是 $k^r$。

练习题

[!info] 例7

用 4,4,4,4,3,3,3,2,2,1 这十个数字能组成多少个不同的十位数？

由多重集合全排列公式，得出答案为

$$\frac{10!}{4!3!2!1!}=12600$$

[!info] 例8

在 $8\times 8$ 的棋盘上放置 2 个红车，4 个黄车，2 个绿车，要求所有车之间彼此不能攻击（任意两个车不在同一行且不在同一列）， 同种颜色的车之间没有区别，问有多少种摆放的方案。

首先只考虑摆放的位置，8 个车显然每行要放一个，假设他们的坐标分别为 $(1,y_1),(2,y_2),\cdots ,(8,y_8)$。因为列号不能重复，$y_1,y_2,\cdots ,y_8$ 是 $\{1,2,3,4,5,6,7,8\}$ 的一个排列。那么在所有车一样的情况下，摆放位置有 $A_8^8$ 种。

现在我们要给每行分配某种颜色的车，而 8 个车其实是一个多重集合 $2\cdot R,4\cdot Y,2\cdot G$。也就是说，在位置固定的情况下，一种颜色方案就是这个多重集合的一个排列，其总的排列数为 $\frac{8!}{2!4!2!}$。

因此，总共的摆放方案有 $A_8^8\times \frac{8!}{2!4!2!}=16934400$ 种。

[!info] 例9

多重集合 $S=\{3\cdot a,2\cdot b,4\cdot c\}$，求 $S$ 的 8 排列个数。

多重集合的非全排列个数没有直接的公式，但某些情况下还是能够求解的，这里采用分类讨论的方法。

一共 9 个元素，8 排列是少用了一个元素，那么可以分成三种独立的情况：

• 少用一个 $a$，$\{2\cdot a,2\cdot b,4\cdot c\}$ 的全排列个数为 $\frac{8!}{2!2!4!}=420$。
• 少用一个 $b$，$\{3\cdot a,1\cdot b,4\cdot c\}$ 的全排列个数为 $\frac{8!}{3!1!4!}=280$。
• 少用一个 $c$，$\{3\cdot a,2\cdot b,3\cdot c\}$ 的全排列个数为 $\frac{8!}{3!2!3!}=560$。

所以 $S$ 的 8 排列个数为 $420+280+560=1260$。

多重集合与不定方程的解

设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\}$ 为多重集合，若 $r\le n_i,i=1,2,\cdots ,k$，那么 $S$ 的 $r$ 组合数是 $C_{k+r-1}^r$。

证明：

$S$ 的 $r$ 组合是 $S$ 的一个子集，也是一个多重集合 $\{x_1\cdot a_1,x_2\cdot a_2,\cdots ,x_k\cdot a_k\}$，其中满足 $x_1+x_2+\cdots +x_k=r$，$x_i$ 都为非负整数。

那么组合数的个数就等于这个不定方程解的个数，即每一个组合和每一个解是一一对应的。

• 正整数解的个数：隔板法，现在有 $r$ 个元素，用 $k-1$ 个隔板把他们分成 $k$ 个部分，每个部分不能为空，那么答案就是 $C_{r-1}^{k-1}$。

• 非负整数解的个数：隔板法，现在有 $r$ 个元素，用 $k-1$ 个隔板把他们分成 $k$ 个部分，每个部分允许为空，那么答案就是 $C_{k+r-1}^{k-1}=C_{k+r-1}^r$。

练习题

[!info] 例10

有一家面包店有 $8$ 种面包圈，一个面包盒内装有 $12$ 个面包圈，那么能够装配多少不同类型的面包盒？

显然，每种面包圈有无限个，也就保证了 $12<n_i$。这个问题其实是求 8 种元素的多重集合里选出 12 个元素的组合有多少个，那么答案为 $C_{12+8-1}^{12}=50388$ 种。

[!info] 例11

不定方程 $x_1+x_2+x_3+x_4=10$ 的正整数解的个数有多少个？ 直接用隔板法，现在有 10 个元素，用 3 个隔板把他们分成 4 个非空部分，答案为 $C_9^3$。

[!info] 例12

不定方程 $x_1+x_2+x_3+x_4=10$ 的正整数解的个数有多少个？

把 $2n$ 个人分成 $n$ 组，每组 2 人，求不同的分组方法数，比如 $n=10$ 的情况。

比如现在 $n=2$，有三种分法：

• $\{1,2\},\{3,4\}$
• $\{1,3\},\{2,4\}$
• $\{1,4\},\{2,3\}$

1. 考虑总的排列数：

$$20!$$

2. 每组组内的顺序不重要：

$$\frac{20!}{(2!{)}^{10}}$$

3. 组与组之间的顺序不重要：

$$\frac{20!}{(2!{)}^{10}\cdot 10!}$$

更一般的情况，我们有如下定理：

把 $n$ 个不同的元素划分成 $k$ 个不同的组，使得第 $i$ 个组有 $n_i$ 个元素，并且满足 $n=n_1+n_2+\cdots +n_k$。那么这样的划分方案数等于 $$\frac{n!}{n_1!n_2!\cdots n_k!}$$

如果组之间没有区别，且 $n_1=n_2=\cdots =n_k=\frac{n}{k}$，那么划分方案数为$$\frac{n!}{k!n_1!n_2!\cdots n_k!}=\frac{n!}{k!(\frac{n}{k}{)}^k}$$

抽屉原理

定义及证明

鸽巢原理又称为抽屉原理。其最简单的形式如下：

如果 $n+1$ 个物体被放进 $n$ 个盒子，那么至少有一个盒子包含两个或者两个以上的物体。

可以用反证法来证明：如果这 $n$ 个盒子中每个都至多含有一个物体，那么物体的总数最多是 $n$，和已知的有 $n+1$ 个物体矛盾，故某个盒子必然包含两个及以上的物体。

• 用 $n$ 种颜色给 $n+1$ 个物体染色，那么必有两个物体颜色相同。
• 某年级有 367 个人，那么必有 2 人的生日是相同的。
• 有 $n$ 对已婚夫妇，至少选出其中 $n+1$ 个人才能保证能够选出一对夫妇。

一个合格的水果篮必须满足下面三个条件之一：

• 至少有 8 个苹果；
• 至少有 6 个橙子；
• 至少有 9 个桃子。

现在有一个只装苹果、橙子、桃子的水果篮，那么篮子里最少有多少水果时，能保证是合格的？

最坏情况是包含 7 个苹果、5 个橙子、8 个桃子，此时再随便多一个水果就是合格的了，所以最少 $7+5+8+1=21$ 个水果能保证合格。

[!example] Erdős–Szekeres定理

对于一个长度为 $n$ 的序列，如果 $n\ge k^2+1$，那么序列中一定存在一个长度至少为 $k+1$ 的非降序子序列或非增序子序列。

例题

[!info] 区间最小差值查询

给定一个包含 $n$ 个整数的数组，你会得到该数组中的两个下标 $i$ 和 $j$（$i<j$）。你需要找出下标范围 $[i,j]$ 内的所有整数中，差值最小的两个数的差值，并输出这个最小值。数组的下标从 $1$ 开始到 $n$ 结束。

保证 $2\le n\le 10^5$， $1\le q\le 10^5$，数组元素取值范围 $[1,1000]$

[!info] 糖果分配

$n$ 个数，选出一个子集使得子集和是 $c$ 的倍数，保证 $c\le n$。

容斥原理

[!example] 例子

一个班有 $30$ 名学生，$20$ 人喜欢数学，$15$ 人喜欢物理，$10$ 人两科都喜欢。数学物理都不喜欢的人有多少？

设全集 $U$ 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么

$$\begin{array}{rl}\left|\bigcup _{i=1}^n{S}_i\right|=& \sum _i|S_i|-\sum _{i<j}|S_i\cap S_j|+\sum _{i<j<k}|S_i\cap S_j\cap S_k|\\ & \\ & -\cdots +(-1{)}^{m-1}\sum _{a_i<a_{i+1}}\left|\bigcap _{i=1}^m{S}_{a_i}\right|\\ & \\ & +\cdots +(-1{)}^{n-1}|S_1\cap \cdots \cap S_n|\end{array}$$

即

$$\left|\bigcup _{i=1}^n{S}_i\right|=\sum _{m=1}^n(-1{)}^{m-1}\sum _{a_i<a_{i+1}}\left|\bigcap _{i=1}^m{S}_{a_i}\right|$$

容斥原理例题

[!example] 例1

求 $1$ 到 $1000$ 中能被 $4$ 或 $6$ 或 $9$ 整除的数的个数。

1. 定义集合

• $A$：能被 $4$ 整除的数，$|A|=\lfloor \frac{1000}{4}\rfloor =250$
• $B$：能被 $6$ 整除的数，$|B|=\lfloor \frac{1000}{6}\rfloor =166$
• $C$：能被 $9$ 整除的数，$|C|=\lfloor \frac{1000}{9}\rfloor =111$

2. 计算交集的大小

• $|A\cap B|$：能被 $lcm(4,6)=12$ 整除的数，$|A\cap B|=\lfloor \frac{1000}{12}\rfloor =83$
• $|B\cap C|$：能被 $lcm(6,9)=18$ 整除的数，$|B\cap C|=\lfloor \frac{1000}{18}\rfloor =55$
• $|A\cap C|$：能被 $lcm(4,9)=36$ 整除的数，$|A\cap C|=\lfloor \frac{1000}{36}\rfloor =27$

3. 计算三者交集的大小

$|A\cap B\cap C|$ ：能被 $lcm(4,6,9)=36$ 整除的数， $$|A\cap B\cap C|=\lfloor \frac{1000}{36}\rfloor =27$$

4. 容斥公式:

$$\begin{array}{rl}|A\cup B\cup C|=& |A|+|B|+|C|\\ & \\ & -|A\cap B|-|B\cap C|-|A\cap C|\\ & \\ & +|A\cap B\cap C|\end{array}$$

$$=250+166+111-83-55-27+27=389$$

[!example] 例2

有 $5$ 个不同的物品需要放入 $4$ 个不同的盒子中，要求所有盒子都不为空。问有多少种放置方法？

提示：设事件 $A_i$ 表示盒子 $i$ 为空。

$$N=4^5-\left(\genfrac{}{}{0ex}{}{4}{1}\right)\cdot 3^5+\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 2^5-\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 1^5$$

[!example] 例3

有 $6$ 个信件需要装入 $6$ 个信封，要求没有一个信件被装入正确的信封，有多少种装法？

提示：设事件 $A_i$ 表示第 $i$ 个物品在原来位置。

根据容斥原理，错排数 $D_n$ 可以表示为： $$n!-\left(\genfrac{}{}{0ex}{}{n}{1}\right)(n-1)!+(\genfrac{}{}{0ex}{}{n}{2})(n-2)!-\left(\genfrac{}{}{0ex}{}{n}{3}\right)(n-3)!+\cdots$$

进一步化简

$$n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1{)}^n}{n!}\right)$$

$$=\lfloor \frac{n!}{e}\rfloor$$

概率与期望

多项式相关

快速傅里叶变换

一、写在前面

两个 $n$ 次多项式相加的最直接方法所需的时间是 $O(n)$，但是相乘的最直接方法所需的时间为 $O(n^2)$。用快速傅里叶变换（Fast Fourier Transform，FFT）可以使多项式相乘的时间复杂度降低为$O(n\log n)$。

需要的一些前置技能：复数、多项式、线性代数。

二、多项式

一个以 $x$ 为变量的多项式定义在一个代数域 $F$ 上，将函数 $A(x)$ 表示为形式和:

$$A(x)=\sum _{j=0}^{n-1}{a}_j{x}^j$$

我们称 $a_0,a_1,\dots ,a_{n-1}$ 为如上多项式的系数，所有系数都属于域 $F$，典型的情形是复数集合 $C$。

如果一个多项式 $A(x)$ 的最高次的非零系数是 $a_k$，则称 $A(x)$ 的次数是 $k$，记 $degree(A)=k$。任何严格大于一个多项式次数的整数都是该多项式的次数界，因此，对于次数界为 $n$ 的多项式，其次数可以是 $0\sim n-1$ 之间的任何整数。

多项式加法

如果 $A(x)$ 和 $B(x)$ 是次数界为 $n$ 的多项式，那么它们的和也是一个次数界为 $n$ 的多项式 $C(x)$，对所有属于定义域的 $x$，都有 $C(x)=A(x)+B(x)$。也就是说，

若

$$A(x)=\sum _{j=0}^{n-1}{a}_j{x}^j$$

$$B(x)=\sum _{j=0}^{n-1}{b}_j{x}^j$$

则

$$C(x)=\sum _{j=0}^{n-1}{c}_j{x}^j(c_j=a_j+b_j)$$

例如，如果有多项式 $A(x)=6x^3+7x^2-10x+9$ 和 $B(x)=-2x^3+4x-5$，那么 $C(x)=4x^3+7x^2-6x+4$。

多项式乘法

如果 $A(x)$ 和 $B(x)$ 是次数界为 $n$ 的多项式，那么它们的乘积 $C(x)$ 是一个次数界为 $2n-1$ 的多项式 $C(x)$，对所有属于定义域的 $x$，都有 $C(x)=A(x)B(x)$。方法类似还是用上一个例子，那么得到

$$C(x)=-12x^6-14x^5+44x^4-20x^3-75x^2+86x-45$$

形式化的式子有

$$C(x)=\sum _{j=0}^{2n-2}{c}_j{x}^j$$

其中

$$c_j=\sum _{k=0}^j{a}_k{b}_{j-k}$$

此时

$$degree(C)=degree(A)+degree(B)$$

多项式的表示

从某种意义上，多项式的系数表达与点值表达式等价的。

系数表达

对一个次数界为 $n$ 的多项式 $A(x)={\sum }_{j=0}^{n-1}{a}_j{x}^j$而言，其系数表达是一个由系数组成的（列）向量 $a=(a_0,a_1,\dots ,a_{n-1})$。对于多项式乘法，系数向量 $c$ 成为输入向量 $a$ 和 $b$ 的卷积，表示成 $c=a\otimes b$。

点值表达

一个次数界为 $n$ 的多项式 $A(x)$ 的点值表达就是一个由$n$个点值对组成的集合

$$\{(x_0,y_0),(x_1,y_1),\dots ,(x_{n-1},y_{n-1})\}$$

使得对 $k=0,1,\dots ,n-1$，所有 $x_k$ 各不相同，且 $y_k=A(x_k)$。

一个多项式可以有很多不同的点值表达。如果采用的点都相同的话，用点值表达多项式做乘法只需 $O(n)$ 的时间。

求值与插值

从一个多项式的系数表达转化为点值表达的过程是求值，其逆运算称为插值。

定理（插值多项式的唯一性）：对于任意 $n$ 个点值对组成的集合 $\{(x_0,y_0),(x_1,y_1),\dots ,(x_{n-1},y_{n-1})\}$，其中所有的 $x_k$ 都不同，那么存在唯一的次数界为 $n$ 的多项式 $A(x)$，满足 $y_k=A(x_k)$。

证明列出矩阵方程，然后结合范德蒙德矩阵的性质。

简单的求值和插值（拉格朗日插值）的时间复杂度都是 $O(n^2)$ 的。

我们之后就要通过巧妙选取点来加速这两个过程，使其运行时间变为$O(n\log n)$。

三、单位复数根

$n$ 次单位复数根是满足 ${\omega }^n=1$ 的复数 $\omega$。

$n$ 次单位复数根恰好有 $n$ 个：

$${\omega }_n^0,{\omega }_n^1,\dots ,{\omega }_n^{n-1}$$

其中主 $n$ 次单位复数根为

$${\omega }_n=e^{2\pi i/n}=\cos (2\pi /n)+i\sin (2\pi /n)$$

其他 $n$ 次单位复数根都是 ${\omega }_n$ 的幂次。

[!theroem] 消去引理

对于任何整数 $n\ge 0,k\ge 0,d>0$，有 ${\omega }_{dn}^{dk}={\omega }_n^k$

[!theroem] 推论

对于任意偶数 $n>0$，有 ${\omega }_n^{n/2}={\omega }_2=-1$

[!theroem] 折半引理

如果 $n>0$ 为偶数，那么 $n$ 个 $n$ 次单位复数根的平方的集合就是 $n/2$ 个 $n/2$ 次单位复数根的集合

[!theroem] 求和引理

对任意整数 $n\ge 1$ 和不能被 $n$ 整除的非负整数 $k$，有 ${\sum }_{j=0}^{n-1}({\omega }_n^k{)}^j=0$

四、快速傅里叶变换

DFT

现在我们希望计算次数界 $n$ 的多项式

$$A(x)=\sum _{j=0}^{n-1}{a}_j{x}^j$$

在 ${\omega }_n^k$ 处的值，记为 $y_k$

$$y_k=A({\omega }_n^k)=\sum _{j=0}^{n-1}{a}_j{\omega }_n^{kj}$$

向量 $y=(y_0,y_1,\dots ,y_{n-1})$ 就是系数向量 $a=(a_0,a_1,\dots ,a_{n-1})$ 的离散傅里叶变换（DFT），记为 $y={\text{DFT}}_n(a)$。

FFT

快速傅里叶变换（FFT） 利用复数单位根的特殊性质，可以在$O(n\log n)$时间内计算出 ${\text{DFT}}_n(a)$。首先通篇假设 $n$ 恰好是 $2$ 的整数幂。

FFT 利用了分治策略，采用 $A(x)$ 中偶数下标的系数与奇数下标的系数，分别定义两个新的次数界为 $n/2$ 的多项式 $A^{[0]}(x)$ 和 $A^{[1]}(x)$:

$$A^{[0]}(x)=a_0+a_{2}x+a_4{x}^2+\cdots +a_{n-2}{x}^{n/2-1}$$

$$A^{[1]}(x)=a_1+a_{3}x+a_5{x}^2+\cdots +a_{n-1}{x}^{n/2-1}$$

于是有

$$A(x)=A^{[0]}(x^2)+x{A}^{[1]}(x^2)$$

所以，求 $A(x)$ 在 ${\omega }_n^0,{\omega }_n^1,\dots ,{\omega }_n^{n-1}$ 处的值转换为求次数界为 $n/2$ 的多项式 $A^{[0]}(x)$ 和 $A^{[1]}(x)$ 在点 $$({\omega }_n^0{)}^2,({\omega }_n^1{)}^2,\dots ,({\omega }_n^{n-1}{)}^2$$ 的值。可以发现其实是 $n/2$ 个 $n/2$ 次单位复数根，且每个根恰好出现两次:

$${\omega }_{n/2}^0,{\omega }_{n/2}^1,\dots ,{\omega }_{n/2}^{n/2-1},{\omega }_{n/2}^{n/2},{\omega }_{n/2}^{n/2+1},\dots ,{\omega }_{n/2}^{n-1}$$

IDFT

将点值表达的多项式转换回系数表达，是相似的过程。

我们把 DFT 写成矩阵乘积 $y=V_{n}a$。

其中 $V_n$ 是一个范德蒙德矩阵，在 $(k,j)$ 处的元素为 ${\omega }_n^{kj}$。

对于逆运算 $a={\text{DFT}}_n^{-1}(y)$，我们把 $y$ 乘以 $V_n$ 的逆矩阵来处理。

[!theroem] 定理

对 $j,k=0,1,\dots ,n-1$，$V_n^{-1}$ 在 $(j,k)$ 元素为 ${\omega }_n^{-kj}/n$。

证明 $V_n^{-1}{V}_n=I_n$ 时用求和引理即可，注意使用条件。

所以可以推导出 ${\text{DFT}}_n^{-1}(y)$：

$$a_j=\frac{1}{n}\sum _{k=0}^{n-1}{y}_k{\omega }_n^{-kj}$$

可以看出只需将单位根取倒数，做一次 FFT，最后将结果都除以 $n$，就做完逆变换了。

五、代码实现

首先是手写复数类，也可以用 std::complex<T>。

struct Complex {
    double x, y;
    Complex(double x_ = 0, double y_ = 0) {
        x = x_;
        y = y_;
    }
    Complex operator-(const Complex& t) const {
        return Complex(x - t.x, y - t.y);
    }
    Complex operator+(const Complex& t) const {
        return Complex(x + t.x, y + t.y);
    }
    Complex operator*(const Complex& t) const {
        return Complex(x * t.x - y * t.y, x * t.y + y * t.x);
    }
};

递归实现

void fft(Complex y[], int n) {
    if (n == 1) return;
    static Complex c[MAXN];
    int m = n / 2;
    for (int i = 0; i < m; ++i) {
        c[i] = y[i * 2];
        c[i + m] = y[i * 2 + 1];
    }
    copy(c, c + n, y);
    Complex *a0 = y, *a1 = y + m;
    fft(a0, m);
    fft(a1, m);
    for (int i = 0; i < m; ++i) {
        Complex w(cos(-2 * PI / n * i), sin(-2 * PI / n * i));
        c[i] = a0[i] + w * a1[i];
        c[i + m] = a0[i] - w * a1[i];
    }
    copy(c, c + n, y);
}

合并过程的推导：

对于$0\le k<n/2$

$$\begin{array}{rl}{y}_k& =A({\omega }_n^k)\\ & \\ & =A^{[0]}({\omega }_n^{2k})+{\omega }_n^k{A}^{[1]}({\omega }_n^{2k})\\ & \\ & =A^{[0]}({\omega }_{n/2}^k)+{\omega }_n^k{A}^{[1]}({\omega }_{n/2}^k)\\ & \\ & =y_k^{[0]}+{\omega }_n^k{y}_k^{[1]}\end{array}$$

前半段没什么问题，再来看后半段

$$\begin{array}{rl}{y}_{k+(n/2)}& =A({\omega }_n^{k+(n/2)})\\ & \\ & =A^{[0]}({\omega }_n^{2k+n})+{\omega }_n^{k+(n/2)}{A}^{[1]}({\omega }_n^{2k+n})\\ & \\ & =A^{[0]}({\omega }_n^{2k})-{\omega }_n^k{A}^{[1]}({\omega }_n^{2k})\\ & \\ & =A^{[0]}({\omega }_{n/2}^k)-{\omega }_n^k{A}^{[1]}({\omega }_{n/2}^k)\\ & \\ & =y_k^{[0]}-{\omega }_n^k{y}_k^{[1]}\end{array}$$

迭代实现

递归实际运行起来常数很大，我们需要更高效的实现方法。

先来观察一下递归过程中输入向量的下标变化，以$n=8$举例，可以将这个过程自行脑补成一个完全二叉树的样子：

[0   1   2   3   4   5   6   7]

[0   2   4   6] [1   3   5   7]

[0   4] [2   6] [1   5] [3   7]

[0] [4] [2] [6] [1] [5] [3] [7]

如果观察二进制的话会发现对应的下标是反转二进制位得到的，比如“011”变成“110”，即下标 3 变成了 6。

[000   001   010   011   100   101   110   111]

[000   010   100   110] [001   011   101   111]

[000   100] [010   110] [001   101] [011   111]

[000] [100] [010] [110] [001] [101] [011] [111]

代码实现举例两种

1. 直接求出对应位置反转二进制位后的数，然后交换，时间复杂度$O(n\log n)$

void change(Complex y[], int len) {
    int k = 0;
    while ((1 << k) < len) ++k;
    for (int i = 0; i < len; ++i) {
        int t = 0;
        for (int j = 0; j < k; ++j)
            if (i >> j & 1)
                t |= 1 << (k - j - 1);
        if (i < t) swap(y[i], y[t]);
    }
}

2. 从高位模拟二进制加一，用经典的摊还分析可以证明复杂度是$O(n)$

void change(Complex y[], int len) {
    int i, j, k;
    for (i = 1, j = len / 2; i < len - 1; i++) {
        if (i < j) swap(y[i], y[j]);
        k = len / 2;
        while (j >= k) {
            j -= k;
            k /= 2;
        }
        if (j < k) j += k;
    }
}

之后我们再考虑自底向上的合并，在之前的递归版本中，有一个公用子表达式 ${\omega }_n^k{y}_k^{[1]}$ 计算了两次，我们可以只计算一次乘积，存放在临时变量 $t$ 里，然后从 $y_k^{[0]}$ 中增加或者减去 $t$，这一系列操作称为一个蝴蝶操作。

代码：

void fft(Complex y[], int len, int on) {
    change(y, len);
    for (int h = 2; h <= len; h <<= 1) {
        Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
        for (int j = 0; j < len; j += h) {
            Complex w(1, 0);
            for (int k = j; k < j + h / 2; k++) {
                Complex u = y[k];
                Complex t = w * y[k + h / 2];
                y[k] = u + t;
                y[k + h / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if (on == -1)
        for (int i = 0; i < len; i++)
            y[i].x /= len;
}

on 取值 $1$ 或 $-1$，on 为 $-1$ 代表逆变换。

实际上，预处理单位根代替每次旋转精度会更好。

void init() {
    for (int i = 0; i <= MAXN; ++i)
        wn[i] = Complex(cos(-2 * PI * i / MAXN), sin(-2 * PI * i / MAXN));
}

void fft(Complex y[], int len, int on) {
    change(y, len);
    for (int h = 2; h <= len; h <<= 1) {
        int st = MAXN / h;
        for (int j = 0; j < len; j += h) {
            int ptr = 0;
            for (int k = j; k < j + h / 2; k++) {
                Complex w = wn[on == 1 ? ptr : MAXN - ptr];
                Complex u = y[k], t = w * y[k + h / 2];
                y[k] = u + t;
                y[k + h / 2] = u - t;
                ptr += st;
            }
        }
    }
    if (on == -1)
        for (int i = 0; i < len; i++)
            y[i].x /= len;
}

六、模板

多项式乘法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI = acos(-1.0);
const int MAXN = 1 << 18;
struct Complex {
    double x, y;
    Complex(double x_ = 0, double y_ = 0) {
        x = x_;
        y = y_;
    }
    Complex operator-(const Complex& t) const {
        return Complex(x - t.x, y - t.y);
    }
    Complex operator+(const Complex& t) const {
        return Complex(x + t.x, y + t.y);
    }
    Complex operator*(const Complex& t) const {
        return Complex(x * t.x - y * t.y, x * t.y + y * t.x);
    }
} x1[MAXN + 5], x2[MAXN + 5], wn[MAXN + 5];
void init() {
    for (int i = 0; i <= MAXN; ++i)
        wn[i] = Complex(cos(-2 * PI * i / MAXN), sin(-2 * PI * i / MAXN));
}
void change(Complex y[], int len) {
    int i, j, k;
    for (i = 1, j = len / 2; i < len - 1; i++) {
        if (i < j) swap(y[i], y[j]);
        k = len / 2;
        while (j >= k) {
            j -= k;
            k /= 2;
        }
        if (j < k) j += k;
    }
}
void fft(Complex y[], int len, int on) {
    change(y, len);
    for (int h = 2; h <= len; h <<= 1) {
        int st = MAXN / h;
        for (int j = 0; j < len; j += h) {
            int ptr = 0;
            for (int k = j; k < j + h / 2; k++) {
                Complex w = wn[on == 1 ? ptr : MAXN - ptr];
                Complex u = y[k], t = w * y[k + h / 2];
                y[k] = u + t;
                y[k + h / 2] = u - t;
                ptr += st;
            }
        }
    }
    if (on == -1)
        for (int i = 0; i < len; i++)
            y[i].x /= len;
}
int n, m;
int main() {
    init();
    scanf("%d%d", &n, &m);
    ++n;
    ++m;
    int len = 1;
    while (len < (n << 1) || len < (m << 1)) len <<= 1;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        x1[i].x = x;
    }
    for (int i = 0; i < m; ++i) {
        int x;
        scanf("%d", &x);
        x2[i].x = x;
    }
    fft(x1, len, 1);
    fft(x2, len, 1);
    for (int i = 0; i < len; ++i) x1[i] = x1[i] * x2[i];
    fft(x1, len, -1);
    for (int i = 0; i < n + m - 1; ++i)
        printf("%d%c", (int)(x1[i].x + 0.5), " \n"[i == n + m - 2]);
    return 0;
}

七、进阶

拆系数 FFT

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
const int MAXL = 1 << 18;

namespace FFT {
const db PI = acos(-1.0);
const int base = 32768;
struct Complex {
    db x, y;
    Complex(db x_ = 0, db y_ = 0) {
        x = x_;
        y = y_;
    }
    Complex operator-(const Complex& t) const {
        return Complex(x - t.x, y - t.y);
    }
    Complex operator+(const Complex& t) const {
        return Complex(x + t.x, y + t.y);
    }
    Complex operator*(const Complex& t) const {
        return Complex(x * t.x - y * t.y, x * t.y + y * t.x);
    }
    Complex operator*(const db& t) const {
        return Complex(x * t, y * t);
    }
} wn[MAXL + 5];
Complex x1[MAXL + 5], x2[MAXL + 5], x3[MAXL + 5], x4[MAXL + 5];
Complex x5[MAXL + 5], x6[MAXL + 5], x7[MAXL + 5];
int rev[MAXL + 5];
int len, mod;
void init(int n, int p) {
    mod = p;
    int L = 0;
    while ((1 << L) < (n << 1)) ++L;
    len = 1 << L;
    for (int i = 0; i <= MAXL; i++) {
        rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (L - 1));
        wn[i] = Complex(cos(-2 * i * PI / MAXL), sin(-2 * i * PI / MAXL));
    }
}
void fft(Complex y[], int on) {
    for (int i = 0; i < len; ++i)
        if (i < rev[i])
            swap(y[i], y[rev[i]]);
    for (int h = 2; h <= len; h <<= 1) {
        int st = MAXL / h;
        for (int j = 0; j < len; j += h) {
            int ptr = 0;
            for (int k = j; k < j + h / 2; k++) {
                Complex u = y[k];
                Complex t = wn[on == 1 ? ptr : MAXL - ptr] * y[k + h / 2];
                y[k] = u + t;
                y[k + h / 2] = u - t;
                ptr += st;
            }
        }
    }
    if (on == -1)
        for (int i = 0; i < len; i++)
            y[i].x /= len;
}
void solve(int* a, int n, int* b, int m, int* c) {
    for (int i = 0; i < n; ++i) {
        x1[i] = Complex(a[i] / base, 0);
        x2[i] = Complex(a[i] % base, 0);
    }
    for (int i = n; i < len; ++i) x1[i] = x2[i] = Complex(0, 0);
    for (int i = 0; i < m; ++i) {
        x3[i] = Complex(b[i] / base, 0);
        x4[i] = Complex(b[i] % base, 0);
    }
    for (int i = m; i < len; ++i) x3[i] = x4[i] = Complex(0, 0);
    fft(x1, 1);
    fft(x2, 1);
    fft(x3, 1);
    fft(x4, 1);
    for (int i = 0; i < len; ++i) {
        x5[i] = x1[i] * x3[i];
        x6[i] = x1[i] * x4[i] + x2[i] * x3[i];
        x7[i] = x2[i] * x4[i];
    }
    fft(x5, -1);
    fft(x6, -1);
    fft(x7, -1);
    for (int i = 0; i < len; ++i) {
        c[i] = 1LL * base * base * ((ll)(x5[i].x + 0.5) % mod) % mod;
        c[i] += 1LL * base * ((ll)(x6[i].x + 0.5) % mod) % mod;
        if (c[i] >= mod) c[i] -= mod;
        c[i] += (ll)(x7[i].x + 0.5) % mod;
        if (c[i] >= mod) c[i] -= mod;
    }
}
}  // namespace FFT

ll n;
int m, p;
int ans[MAXL + 5], v[MAXL + 5];
int main() {
    cin >> n >> m >> p;
    m++;
    FFT::init(m, p);
    v[0] = v[1] = 1;
    ans[0] = 1;
    while (n) {
        if (n & 1) {
            FFT::solve(ans, m, v, m, ans);
        }
        FFT::solve(v, m, v, m, v);
        n >>= 1;
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i] << (i + 1 < m ? " " : "\n");
    }
    return 0;
}

数据结构

单调队列

动态规划

背包

综合练习

• 进攻策略 背包+前缀和+双指针

• 子序列倍数统计 ST/线段树+背包合并

背包基础

01 背包

普通写法

01 背包

01 背包：每个物品只有一个。

$dp[i][j]$ 表示考虑前 $i$ 个物品，用容量为 $j$ 的背包能背出的最大价值。

时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[205][5005];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = 1; j <= m; j++) {
            if (j < w)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
        }
    }
    cout << dp[n][m] << endl;
}

空间优化

因为 $dp[i][j]$ 只由上一行的之前某列转移过来，所以可以优化掉第一维，倒序更新 dp 值。空间复杂度 $O(m)$。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[5005];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = m; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[m] << endl;
}

完全背包

完全背包问题

完全背包：每种物品有无限个。

直接把 01 背包的倒序改成正序 for 循环即可。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[5005];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = w; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[m] << endl;
}

多重背包

部分背包问题

多重背包：每种物品有个数限制。

二进制拆分优化：把 $c$ 个物品拆成 $1$ 个，$2$ 个，$4$ 个，$8$ 个…直到最后剩下的捆绑到一起，这样分成 $O(\log c)$ 个物品，一定能组合出 $0$ 到 $c$ 之间任意一个整数。

时间复杂度 $O(m{\sum }_i\log c_i)$