「v3」A - 基础算法

    「v3」A - 基础算法

    A - 基础算法 指令基础

    NOI Linux 指令

    返回上一级目录:cd ..。
    返回当前用户的主目录:cd ~。
    进入某一目录内:cd <目录路径>。

    显示当前工作目录:pwd。

    新建文件夹:mkdir <目录文件> <新建文件夹名>。

    删除:

    • 删除单一文件:rm <文件路径>。
    • 删除目录及目录内的文件:rm -r <要删除的目录路径>。

    改名:mv <旧文件名> <新文件名>。

    查看文件内容:cat <文件路径>。

    简单查看文件信息:dir <目录路径>。

    详细查看文件信息:ls -alh <目录路径>。

    • ls -a <目录路径>:显示所有文件(包括隐藏文件)。
    • ls -l <目录路径>:显示文件属性。
    • ls -h <目录路径>:将文件大小转换为常用单位(无单位默认为字节)。

    提升权限:

    • 使用 root 权限(最高权限)操作该命令:sudo <命令>。
    • 登录到另外一个用户:su <用户名>。

    命令行编译:g++/gcc <源代码文件名> -o <可执行文件名>。

    • -std=c++11:c++11 标准。
    • -O2:O2 优化。
    • ulimit -s 128000000:开栈。
    • -Wall:显示所有警告。
    • -Wextra:检测可疑代码并生成警告。
    • -Wconversion:转型警告。

    执行程序:./<应用程序>。

    只读执行程序:./<project> <A.in。

    只输执行程序:./<project> >A.out。

    读输执行程序:./<project> <A.in >A.out。

    查看执行程序运行时间:time ./<应用程序>。

    比较文本:diff <文本 A><文本 B>。

    A - 基础算法 语言基础

    语言基础

    空间大小

    • bit(位,简写 b),是计算机中的最小数据单位。
    • Byte(字节,简写 B),是计算机文件大小的基本计算单位。1 个 Byte 由 8 bit 组成,可代表一个字母、数字或符号。中文字符则需要 2 Byte。
    • KB(千字节)、MB(兆字节)、GB(吉字节、千兆)、TB(太字节)。
    1 Byte=8 bit1 KB=1024 Byte1 MB=1024 KB1 GB=1024 MB1 TB=1024 GB1 \ \mathrm{Byte} = 8 \ \mathrm{bit} \\ 1 \ \mathrm{KB} = 1024 \ \mathrm{Byte} \\ 1 \ \mathrm{MB} = 1024 \ \mathrm{KB} \\ 1 \ \mathrm{GB} = 1024 \ \mathrm{MB} \\ 1 \ \mathrm{TB} = 1024 \ \mathrm{GB}
    • sizeof() 的功能是返回指定数据类型或表达式值在内存中占用的字节数(单位:B),需要强转 double 后除以 2202^{20} 转化为以 MB 为单位。

    进制

    • 二进制 B,八进制 O,十进制 D,十六进制 H。
    • 0b 表示二进制;0 表示八进制;0x 表示十六进制。在 32 位有符号整数(int)中,0xFFFFFFFF 表示 −1-1。
    • 使用 memset(a, value, sizeof(a)) 初始化一个数组 aa,将数值 value(0x00∼0xFF)\mathrm{value}(\mathrm{0x00\sim 0xFF}) 填充到数组 aa 的每一个字节上。而 11 个 int 占用 44 个字节,故 memset 只能赋值出每 88 位都相同的 int。
    • 0x3F3F3F3F 是满足以下两个条件的最大整数。常用于将一个数初始化为正无穷。
      • 整数的两倍不超过 0x7FFFFFFF,即 int 能表示的最大正整数。
      • 整数的每 88 位(每个字节)都是相同的。
    • 常使用 memset(a, 0x3f, sizeof(a)),将一个数组 aa 初始化为正无穷。

    原码:

    • 32 位有符号整数(int)的最高位为符号位。00 表示非负数,11 表示负数。

    反码:

    • 非负数的反码:为原码本身。
    • 负数的反码:符号位不变,其余位取反。

    补码:计算机中有符号数码用补码表示。解决了 00 的编码不唯一性。

    • 非负数的补码:为原码本身。
    • 负数的补码:符号位不变,其余位取反,再 +1+1(即在反码的基础上 +1+1)。
    • −231-2^{31} 的补码为 1000...0000,无原码与反码。

    数值类型

    数值范围:

    • int 范围:[−231,231)[-2^{31}, 2^{31})。
    • unsigned int 范围:[0,232)[0, 2^{32})。
    • long long 范围:[−263,263)[-2^{63}, 2^{63})。
    • unsigned long long 范围:[0,264)[0, 2^{64})。

    自然溢出:

    • unsigned int 自然溢出:对 2322^{32} 取模。
    • unsigned long long 自然溢出:对 2642^{64} 取模。

    输出格式:

    • unsigned int 输出格式:%u。
    • unsigned long long 输出格式:%llu。

    运算符优先级

    1. 圆括号 ()、下标 []、取类或结构分量 ->、取类或结构成员 .
    2. 单目运算符:!、~、++、--、-、&、*、 (type)、sizeof()
    3. 乘除运算符:*、/、%
    4. 加减运算符:+、-
    5. 位移运算符:<<、>>
    6. 比较运算符:<、<=、>、>=
    7. 判等运算符:==、!=
    8. 按位运算符:& 大于 ^ 大于 |
    9. 逻辑运算符:&& 大于 ||
    10. 条件运算符:?:
    11. 赋值运算符:=、/=、%=、*=、+=、-=、<<=、>>=、&=、^=、|=
    12. 逗号运算符:,

    运算符结合性

    只有 单目运算符、条件运算符(?:)、赋值运算符 为右结合。其余运算符均为左结合。

    C++ STL

    lower_bound & upper_bound

    • lower_bound(s, t, val):指向 [s,t)[s, t) 中第一个 ≥val\geq \mathrm{val} 的元素的迭代器,需要保证 [s,t)[s, t) 升序排序。
    • upper_bound(s, t, val):指向 [s,t)[s, t) 中第一个 >val> \mathrm{val} 的元素的迭代器,需要保证 [s,t)[s, t) 升序排序。
    • --upper_bound(s, t, val):指向 [s,t)[s, t) 中最后一个 ≤val\leq \mathrm{val} 的元素的迭代器,需要保证 [s,t)[s, t) 升序排序。

    sort

    • sort() 的实现基于快速排序。

    升序排序(默认):sort(s, t)。

    降序排序:sort(s, t, greater<int>())。

    stable_sort

    • stable_sort() 的实现基于归并排序。比较次数稳定且相较于 std::sort 较少。

    unique

    • unique() 去除容器中相邻的重复元素,并返回去重之后的尾迭代器(或指针)。常用于离散化。
    • 将一个 vector 去重:m = unique(a.begin(), a.end()) - a.begin()。
    • 将一个下标为 1∼n1\sim n 的数组去重:m = unique(a + 1, a + 1 + n) - (a + 1)。

    next_permutation & prev_permutation

    • next_permutation() 求出指定部分的元素,构成的全排列中,字典序排在下一个的排列,并直接在序列上更新。特别地,若不存在排名更靠后的排列,则返回 false;否则返回 true。
    • prev_permutation() 求出指定部分的元素,构成的全排列中,字典序排在上一个的排列,并直接在序列上更新。特别地,若不存在排名更靠前的排列,则返回 false;否则返回 true。
    • 遍历 1∼n1 \sim n 的 n!n! 种全排列:
    for (int i = 1; i <= n; i ++) a[i] = i;
    do {
        // // Calculate the information of a
    } while (next_permutation(a + 1, a + 1 + n));

    vector

    • vector 编号从 00 开始,前闭后开。
    • vector 可以理解成一个变长数组,内部基于倍增思想。设 n,mn, m 分别为 vector 的实际长度与最大长度。
      • 插入元素前,若 n=mn = m,则在内存中申请 2m2m 的连续空间,并把内容转移到新的地址上,再执行插入。
      • 删除元素后,若 n≤m/2n \leq m / 2,则释放一半的空间。
    • vector<int> V(n):指定该容器大小为 nn。
    • vector<int> V(n, m):指定该容器大小为 nn,初始值均为 mm。
    • V.resize(n, m):重新制定该容器大小为 nn,若容器变长,则以值 mm 填充;若容器变短,则超出限制的元素被删除。
    • lower_bound(V.begin(), V.end(), val):指向容器中第一个 ≥val\geq \mathrm{val} 的元素的迭代器,需要保证容器升序排序。
    • upper_bound(V.begin(), V.end(), val):指向容器中第一个 >val> \mathrm{val} 的元素的迭代器,需要保证容器升序排序。
    • V.begin():指向容器中第一个元素的迭代器。
    • V.end():指向容器中最后一个元素的下一个位置的迭代器。即 --V.end() 指向容器中最后一个元素的迭代器。
    • V.front():返回容器的第一个元素,等价于 *V.begin() 和 V[0]。
    • V.back():返回容器的最后一个元素,等价于 *--V.end() 和 V[V.size() - 1]。

    区间计数: upper_bound(V.begin(), V.end(), r) - lower_bound(V.begin(), V.end(), l)。

    priority_queue

    大根堆(默认):priority_queue<int> q。

    小根堆:priority_queue< int, vector<int>, greater<int> > q。

    set

    升序排序(默认):set<int> s。

    降序排序:set< int, greater<int> > s。

    • 设 it 是个迭代器,则 it-- 与 it++ 的时间复杂度均为 O(log⁡n)\mathcal{O}(\log n)。
    • s.lower_bound(val):指向容器中第一个 ≥val\geq \mathrm{val} 的元素的迭代器。
    • s.upper_bound(val):指向容器中第一个 >val> \mathrm{val} 的元素的迭代器。
    • 在 set 中进行二分时,应执行 s.lower_bound(val);而非 lower_bound(s.begin(), s.end(), val)。
    • s.begin():指向容器中最小元素的迭代器。
    • s.end():指向容器中最大元素的下一个位置的迭代器,即 --s.end() 指向容器中最大元素的迭代器。

    multiset

    升序排序(默认):multiset<int> s。

    降序排序:multiset< int, greater<int> > s。

    • s.count(val):返回所有数值为 val\mathrm{val} 的元素个数。时间复杂度为 O(k+log⁡n)\mathcal{O}(k + \log n),其中 kk 为 val\mathrm{val} 的元素个数。
    • s.erase(val):将所有数值为 val\mathrm{val} 的元素删除,返回被删除的元素个数。时间复杂度为 O(k+log⁡n)\mathcal{O}(k + \log n),其中 kk 为 val\mathrm{val} 的元素个数。
    • s.erase(pos):将迭代器 pos\mathrm{pos} 指向的元素删除。
    • 在 multiset 中删除一个数值为 val\mathrm{val} 的元素,应执行 s.erase(s.find(val))。
    • 使用 multiset 维护多关键字的数据,在重载小于号时,应保证两个不同的元素能被有效区分。

    map

    • map 的实现基于红黑树。因此 map 内部的所有元素都是有序的。
    • [] 运算符:h[key] 返回 key\mathrm{key} 映射到的 value\mathrm{value} 的引用,时间复杂度为 O(log⁡n)\mathcal{O}(\log n)。

    特别要注意的是,若查找的 key\mathrm{key} 不存在,则执行 h[key] 后,hh 会自动新建一个二元组 (key,0)(\mathrm{key}, 0),并返回 00 的引用(这里的 00 表示一个广义零值)。该二元组白白地占用了空间,并且会计入 h.size() 的大小中。故推荐在使用 [] 运算符前,先使用 find 检查一下 key\mathrm{key} 的存在性(若 key\mathrm{key} 不存在,则 h.find(key) 会指向 h.end())。

    unordered_map

    • unordered_map 的实现基于 Hash。因此 unordered_map 不保证元素的顺序。
    • [] 运算符:同 map,但时间复杂度为常数级别。

    bitset

    • bitset 编号从 00 开始,前闭后开。
    • bitset 可以进行各种二进制操作,如取反 ~、与 &、或 |、异或 ^、左移 <<、右移 >>。
    • b.count():返回 11 的个数。
    • b.any():查询 bitset 中是否存在 11。
    • b.none():查询 bitset 中是否全 00。
    • b.reset():将所有位改为 00。
    • b.set():将所有位改为 11。
    • b._Find_first():查询低位到高位第一个 11 的位置。
    • b._Find_next():查询当前位置之后下一个 11 的位置。
    • 可以按照如下的方式,遍历一个 bitset:
    for (int i = B._Find_first(); i != B.size(); i = B._Find_next(i))
        // Calculate the information of i

    随机数据生成与对拍

    随机数据生成

    生成一个区间 [l,r][l, r] 中的随机整数:

    • std::mt19937 生成出的随机数的类型为 unsigned int。
    • std::mt19937_64 生成出的随机数的类型为 unsigned long long。
    std::mt19937_64 mt_rnd((unsigned)time(0));
    int R(int l, int r) { // 生成一个区间 [l, r] 中的随机整数
        return mt_rnd() % (r - l + 1) + l;
    }

    生成随机区间列:

    std::mt19937_64 mt_rnd((unsigned)time(0));
    int R(int l, int r) {
        return mt_rnd() % (r - l + 1) + l;
    }
    
    int main() {
        for (int i = 1; i <= m; i ++) {
            int l = R(1, n), r = R(1, n);
            if (l > r) std::swap(l, r);
    
            printf("%d %d\n", l, r);
        }
    }

    生成随机父向树:

    std::mt19937_64 mt_rnd((unsigned)time(0));
    int R(int l, int r) {
        return mt_rnd() % (r - l + 1) + l;
    }
    
    int main() {
        printf("%d\n", n);
        for (int i = 2; i <= n; i ++)
            printf("%d %d\n", R(1, i - 1), i);
    }

    生成随机树(prufer 序列):

    std::mt19937_64 mt_rnd((unsigned)time(0));
    int R(int l, int r) {
        return mt_rnd() % (r - l + 1) + l;
    }
    
    int n;
    int prufer[N];
    
    int deg[N]; 
    
    std::pair<int, int> e[N];
    
    int main() {
        for (int i = 1; i <= n - 2; i ++) prufer[i] = R(1, n);
    
        for (int i = 1; i <= n; i ++) deg[i] = 1;
        for (int i = 1; i <= n - 2; i ++) deg[prufer[i]] ++;
    
        int leaf = 0, p = 0;
        for (int i = 1; i <= n; i ++)
            if (deg[i] == 1) { leaf = p = i; break; }
        for (int i = 1; i <= n - 2; i ++) {
            int x = prufer[i];
    
            e[i] = std::make_pair(leaf, x);
    
            if (-- deg[x] == 1 && x < p) {
                leaf = x;
            } else {
                p ++;
                while (deg[p] != 1) p ++;
                leaf = p;
            }
        }
    
        e[n - 1] = std::make_pair(leaf, n);
    
        for (int i = 1; i < n; i ++)
            printf("%d %d\n", e[i].first, e[i].second);
    }

    生成随机连通图(稀疏图):

    • 先生成一棵 n−1n - 1 条边的随机父向树,保证连通。再生成剩下的 m−n+1m - n + 1 条边。
    std::mt19937_64 mt_rnd((unsigned)time(0));
    int R(int l, int r) {
        return mt_rnd() % (r - l + 1) + l;
    }
    
    int n, m;
    
    std::pair<int, int> e[M];
    std::map< std::pair<int, int>, bool > exist;
    
    int main() {
        for (int i = 1; i < n; i ++) {
            e[i] = std::make_pair(R(1, i), i + 1);
            exist[e[i]] = 1;
        }
    
        for (int i = n; i <= m; i ++) {
            int x, y;
            do {
                x = R(1, n), y = R(1, n);
                if (x > y) std::swap(x, y);
            } while (x == y || exist[std::make_pair(x, y)]);
            e[i] = std::make_pair(x, y);
            exist[e[i]] = 1;
        }
    
        for (int i = 1; i <= m; i ++)
            printf("%d %d\n", e[i].first, e[i].second);
    }

    对拍

    • Windows 系统命令 fc(或类 Unix 系统命令 diff)可以比较两个文件是否一致,一致返回 00,否则返回非零值。
    • clock() 可以返回当前程序已经运行的 CPU 时间,Windows 下单位 ms,Unix 下单位 s。
    #include <bits/stdc++.h>
    
    int main() {
        for (int T = 1; T <= 10000; T ++) {
            printf("Test #%d:\n", T);
    
            system("gen.exe"); // 生成数据
    
            system("std_1.exe"); // 运行程序 1
            system("std_2.exe"); // 运行程序 2
    
            if (system("fc data1.out data2.out")) {
                puts("WA");
                return 0;
            } else {
                puts("AC");
            }
        }
    }

    A - 基础算法 算法基础

    I/O 优化

    读入优化:

    template <class &T>
    inline void read(T &x) {
        static char s;
        static bool opt;
        while (s = getchar(), (s < '0' || s > '9') && s != '-');
        x = (opt = s == '-') ? 0 : s - '0';
        while (s = getchar(), s >= '0' && s <= '9') x = x * 10 + s - '0';
        if (opt) x = ~x + 1;
    }

    位运算

    aor⁡b=aand⁡b+axor⁡ba+b=2(aand⁡b)+axor⁡ba+b=aand⁡b+aor⁡ba−b≤axor⁡b≤a+ba \operatorname{or} b = a \operatorname{and} b + a \operatorname{xor} b \\ a + b = 2(a \operatorname{and} b) + a \operatorname{xor} b \\ a + b = a \operatorname{and} b + a \operatorname{or} b \\ a - b \leq a \operatorname{xor} b \leq a + b

    快速乘

    O(log⁡n)\mathcal{O}(\log n) 快速乘:

    特别要注意的是,模数大小的两倍不能超过 long long 上界。

    typedef long long s64;
    s64 qmul(s64 a, s64 b, s64 p) {
        s64 ans = 0;
        for (; b; b >>= 1) {
            if (b & 1) ans = (ans + a) % p;
            a = 2 * a % p;
        }
        return ans;
    }

    O(1)\mathcal{O}(1) 快速乘:

    注意到:

    a×b mod p=a×b−⌊a×bp⌋×pa \times b \bmod p = a \times b - \left\lfloor \frac{a \times b}{p} \right\rfloor \times p

    利用 long double 来处理 ⌊a×bp⌋\left\lfloor \frac{a \times b}{p} \right\rfloor。

    虽然 a×ba \times b 和 ⌊a×bp⌋×p\left\lfloor \frac{a \times b}{p} \right\rfloor \times p 的数值可能很大,但是两者的差一定在 [0,p)[0, p) 之间,我们只关心它们的前 64 位即可,这正好可以用 long long 运算的自然溢出来处理。

    typedef long long s64;
    s64 qmul(s64 a, s64 b, s64 p) {
        s64 c = (long double)a * b / p + 1e-8;
        s64 ans = a * b - c * p;
        if (ans < 0) ans += p;
        if (ans >= p) ans -= p;
        return ans;
    }

    快速幂

    int qpow(int a, int b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p;
        }
        return ans;
    }

    整数除法 上下取整

    int normal_dn(int x, int y) {
        return x / y;
    }
    
    int normal_up(int x, int y) {
        return (x + y - 1) / y;
        // return x % y == 0 ? x / y : x / y + 1;
    }
    
    int div_dn(int x, int y) {
        bool flag = 0;
        if (x < 0) x = -x, flag ^= 1;
        if (y < 0) y = -y, flag ^= 1;
        return flag ? -normal_up(x, y) : normal_dn(x, y);
    }
    
    int div_up(int x, int y) {
        bool flag = 0;
        if (x < 0) x = -x, flag ^= 1;
        if (y < 0) y = -y, flag ^= 1;
        return flag ? -normal_dn(x, y) : normal_up(x, y);
    }

    二分

    • >> 1 向下取整,/2 向零取整。
    • 在整数域上进行二分时:
      • 若分成的区间为 [l,mid],[mid+1,r][l, \mathrm{mid}], [\mathrm{mid} + 1, r],mid = (l + r) >> 1。
      • 若分成的区间为 [l,mid−1],[mid,r][l, \mathrm{mid} - 1], [\mathrm{mid}, r],mid = (l + r + 1) >> 1。
    • 在实数域上进行二分时,mid = (l + r) / 2。但实数域上的二分容易爆精度,此时可以考虑固定一个二分次数。

    倍增

    从大到小的倍增:从大到小枚举 2i2^i 倍增。

    从小到大的倍增:记 pp 表示上一次成功倍增段的末尾,lenlen 表示当前倍增的步长(初始时为 11)。具体流程为:

    • 尝试加入区间 (p,p+len](p, p + len]。
      • 若加入区间 (p,p+len](p, p + len] 合法,则 p←p+lenp \gets p + len,len←len×2len \gets len \times 2。
      • 若加入区间 (p,p+len](p, p + len] 不合法,则 len←len/2len \gets len / 2。
    • 重复上述流程,直到 len=0len = 0 时,结束倍增。

    二叉树

    n0n_0 与 n2n_2 的关系:n0=n2+1n_0 = n_2 + 1。

    n0n_0 与 n2n_2 的关系证明:

    n=n0+n1+n2=1+n1+2n2⇒n0=n2+1n = n_0 + n_1 + n_2 = 1 + n_1 + 2n_2 \Rightarrow n_0 = n_2 + 1

    贪心

    贪心的常见证明方法:

    • 微扰法(邻项交换)。
    • 范围缩放法。
    • 决策包容性。
    • 反证法。
    • 数学归纳法。

    反悔贪心:待填。

    排序

    选择排序

    • 每轮找出第 ii 小的元素(即 ai∼ana_i \sim a_n 中最小的元素),然后将其与数组的第 ii 位交换。进行 n−1n - 1 轮即可完成排序。
    • 时间复杂度 O(n2)\mathcal{O}(n^2),不稳定。
    void selection_sort() {
        for (int i = 1; i < n; i ++) {
            int ith = i;
            for (int j = i + 1; j <= n; j ++)
                if (a[j] < a[ith]) ith = j;
            std::swap(a[i], a[ith]);
        }
    }

    冒泡排序

    • 每轮检查相邻两个元素,若 ai>ai+1a_i > a_{i + 1} 则交换 ai,ai+1a_i, a_{i + 1}。经过 kk 轮后,数组末尾的 kk 个元素必然是最大的 kk 个元素,故进行 n−1n - 1 轮即可完成排序。
    • 时间复杂度为 O(n2)\mathcal{O}(n^2),稳定。
    • 每轮冒泡排序,对逆序对的影响:记 cic_i 表示以 ii 结尾的逆序对个数,则 ci←max⁡(0,ci+1−1)c_i \gets \max(0, c_{i + 1} - 1)。
    • 每轮冒泡排序的本质:从第一个数开始考虑,将其放到右边第一个比它大的数之前。然后从这个比它大的元素开始考虑,以此类推。设每次考虑的数是 ii(显然 ci=0c_i = 0),将其放到下标 jj 之前的位置,则下标在 i+1∼j−1i + 1 \sim j - 1 中的数均向左移了一位,且逆序对个数减少了一个。
    void bubble_sort() {
        do {
            bool flag = 0;
            for (int i = 1; i < n; i ++)
                if (a[i] > a[i + 1]) {
                    std::swap(a[i], a[i + 1]);
                    flag = 1;
                }
        } while (flag);
    }

    快速排序

    • 通过分治的方式来将一个数组排序:
      • 选取一个中间值 mm,将 ≤m\leq m 的数划分进左子数组,将 >m> m 的数划分进右子数组。
      • 分别对左、右子数组递归进行快速排序。
    • 平均时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n),最坏时间复杂度 O(n2)\mathcal{O}(n^2)。不稳定。

    归并排序

    • 通过分治的方式来将一个数组排序:
      • 取 mid=⌊l+r2⌋\mathrm{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor,将区间 [l,r][l, r] 分成左区间 [l,mid][l, \mathrm{mid}] 与右区间 [mid+1,r][\mathrm{mid} + 1, r]。
      • 分别对左、右子区间递归进行归并排序。
      • 将左、右两个有序子区间,合并成一个大的有序区间。每次比较两个子区间的最小元素,将其中的较小者加入。
    • 时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n),稳定。
    void merge_sort(int l, int r) {
        if (l == r) return;
    
        int mid = (l + r) >> 1;
        merge_sort(l, mid), merge_sort(mid + 1, r);
    
        int i = l, j = mid + 1;
        for (int id = l; id <= r; id ++)
            if (i <= mid && (j > r || a[i] <= a[j]))
                tmp[id] = a[i ++];
            else
                tmp[id] = a[j ++];
    
        for (int id = l; id <= r; id ++)
            a[id] = tmp[id];
    }

    高精度

    • 使用结构体封装,从低位储存到高位。
    • 高精 ++ 高精。对位相加,时间复杂度 O(L)\mathcal{O}(L)。
    • 高精 −- 高精。对位相减,时间复杂度 O(L)\mathcal{O}(L)。
    • 高精 ×\times 低精。对位相乘,时间复杂度 O(L)\mathcal{O}(L)。
    • 高精 ÷\div 低精。模拟竖式长除法,使用低精度除法实现,时间复杂度 O(L)\mathcal{O}(L)。
    • 高精 ×\times 高精。本质上即为 ci+j−1←+ai×bjc_{i + j - 1}\gets_+ a_i\times b_j,时间复杂度 O(L2)\mathcal{O}(L^2)。可以使用 FFT 优化至 O(Llog⁡L)\mathcal{O}(L \log L)。
    • 高精 ÷\div 高精。模拟竖式长除法,使用高精度减法实现,时间复杂度 O(L2)\mathcal{O}(L^2)。
    struct bignum {
        int len, num[SIZE];
     
        bignum() {
            len = 0;
            memset(num, 0, sizeof(num));
        }
     
        void input() {
            static char str[SIZE];
            scanf("%s", str + 1);
     
            len = strlen(str + 1);
            for (int i = 1; i <= len; i ++) num[len - i + 1] = str[i] - '0';
        }
     
        void output() {
            if (!len) {
                puts("0");
            } else {
                for (int i = len; i >= 1; i --) printf("%d", num[i]);
                puts("");
            }
        }
     
        bool operator < (const bignum &b) const {
            if (len ^ b.len) return len < b.len;
            for (int i = len; i >= 1; i --)
                if (num[i] ^ b.num[i]) return num[i] < b.num[i];
            return 0;
        }
     
        bool operator <= (const bignum &b) const {
            if (len ^ b.len) return len < b.len;
            for (int i = len; i >= 1; i --)
                if (num[i] ^ b.num[i]) return num[i] < b.num[i];
            return 1;
        }
     
        bignum operator + (const bignum &b) const {
            bignum c; c.len = std::max(len, b.len);
     
            for (int i = 1; i <= c.len; i ++) c.num[i] = num[i] + b.num[i];
            for (int i = 1; i <= c.len; i ++)
                if (c.num[i] >= 10) c.num[i + 1] ++, c.num[i] -= 10;
     
            while (c.num[c.len + 1]) {
                c.len ++;
                if (c.num[c.len] >= 10) c.num[c.len + 1] ++, c.num[c.len] -= 10;
            }
     
            return c;
        }
     
        bignum operator - (const bignum &b) const {
            bignum c; c.len = len;
     
            for (int i = 1; i <= c.len; i ++) c.num[i] = num[i] - b.num[i];
            for (int i = 1; i <= c.len; i ++)
                if (c.num[i] < 0) c.num[i + 1] --, c.num[i] += 10;
     
            while (c.len && !c.num[c.len]) c.len --;
            return c;
        }
    
        bignum operator * (const int &b) const {
            bignum c; c.len = len;
    
            for (int i = 1; i <= len; i ++) c.num[i] = num[i] * b;
            for (int i = 1; i <= len; i ++) {
                c.num[i + 1] += c.num[i] / 10;
                c.num[i] %= 10;
            }
    
            while (c.num[c.len + 1]) {
                c.len ++;
                c.num[c.len + 1] += c.num[c.len] / 10;
                c.num[c.len] %= 10;
            }
    
            return c;
        }
    
        std::pair<bignum, int> operator / (const int &b) const {
            bignum c; c.len = len;
    
            int r = 0;
            for (int i = len; i >= 1; i --) {
                c.num[i] = (r * 10 + num[i]) / b;
                r = (r * 10 + num[i]) % b;
            }
    
            while (c.len && !c.num[c.len]) c.len --;
            return std::make_pair(c, r); // c 是商,r 是余数
        }
    
        bignum operator * (const bignum &b) const {
            bignum c; c.len = len + b.len;
    
            for (int i = 1; i <= c.len; i ++) {
                for (int j = 1; j <= i; j ++) c.num[i] += num[i - j + 1] * b.num[j];
                c.num[i + 1] += c.num[i] / 10;
                c.num[i] %= 10;
            }
     
            while (c.len && !c.num[c.len]) c.len --;
            return c;
        }
     
        std::pair<bignum, bignum> operator / (const bignum &b) const {
            bignum a = *this;
            if (a < b) return std::make_pair(bignum(), a);
     
            bignum c; c.len = len - b.len + 1;
    
            for (int i = c.len; i >= 1; i --) {
                bignum tmp; tmp.len = b.len + i - 1;
                for (int j = 1; j <= b.len; j ++) tmp.num[j + i - 1] = b.num[j];
     
                while (tmp <= a) a = a - tmp, c.num[i] ++;
            }
     
            while (c.len && !c.num[c.len]) c.len --;
            return std::make_pair(c, a); // c 是商,a 是余数
        }
    };