代数结构#

结构	结构性质	逆运算
$\oplus$ ,Z	阿贝尔群	$\oplus$
$\odot$ ,Z	阿贝尔群	$\odot$
$+$ ,R	阿贝尔群	-
$\times$ ,R/{0}	阿贝尔群	/
&	半格（无逆元的交换群）	$\varnothing$
\|	半格（无逆元的交换群）	$\varnothing$
max	半格（无逆元的交换群）	$\varnothing$
min	半格（无逆元的交换群）	$\varnothing$
$+$ ,所有矩阵，即矩阵加法	阿贝尔群	-
$\times$ ,所有矩阵，即矩阵乘法	幺半群	$\varnothing$

$\oplus$ #

和同或有 $a \odot b = a \oplus b \oplus 1$ 的关系

& 和 |和max和min#

a | b = a + b\leftrightarrow a \& b == 0

&

单位元：-1

性质

$0 \le a\space \& \space b \le min(a,b)\text{当且仅当}a=b\text{时取等，全存在}0\text{时最小}$

|#

单位元：0

性质

$max(a,b) \le a\space | \space b \le a + b\text{当且仅当}a\text{和}b\text{相加无进位时取等}$

max#

单位元：LLONG_MAX

min#

单位元：LLONG_MIN

高精度#

高 + 高#

1
// 高 + 高
2
vector<int> add(vector<int> a, vector<int> b) {
3
    if (a.size() < b.size()) return add(b, a);
4

5
    vector<int> c;
6

7
    int t = 0;
8
    for (int i = 0; i < a.size(); ++i) {
9
        t += a[i];
10
        if (i < b.size()) t += b[i];
11
        c.emplace_back(t % 10);
12
        t /= 10;
13
    }
14

15
    if (t) c.emplace_back(t);
16
    return c;
17
}

高 - 高#

1
// 高 - 高
2
vector<int> sub(vector<int> a, vector<int> b) {
3
    vector<int> c;
4

5
    int t = 0;
6
    for (int i = 0; i < a.size(); ++i) {
7
        t += a[i];
8
        if (i < b.size()) t -= b[i];
9
        c.emplace_back((t + 10) % 10);
10
        if (t < 0) t = -1;
11
    }
12

13
    while (c.size() > 1 && c.back() == 0) c.pop_back();
14

15
    return c;
16
}

高 * 低#

1
// 高 * 低
2
vector<int> mul(vector<int> a, int b) {
3
    vector<int> c;
4

5
    int t = 0;
6
    for (int i = 0; i < a.size() || t; ++i) {
7
        if (i < a.size()) t += a[i] * b;
8
        c.emplace_back(t % 10);
9
        t /= 10;
10
    }
11

12
    while (c.size() > 1 && c.back() == 0) c.pop_back();
13
    return c;
14
}

高 / 低#

1
// 高 / 低
2
vector<int> div(vector<int> a, int b) {
3
    vector<int> c;
4

5
    int r = 0;
6
    for (int i = a.size() - 1; i >= 0; --i) {
7
        r = r * 10 + a[i];
8
        c.emplace_back(r / b);
9
        r %= b;
10
    }
11

12
    reverse(c.begin(), c.end());
13
    while (c.size() > 1 && c.back() == 0) c.pop_back();
14
    return c;
15
}

高 * 高#

1
vector<int> mul(vector<int>& a, vector<int>& b) {
2
    vector<int> c(a.size() + b.size(), 0);
3

4
    for (int i = 0; i < a.size(); ++i) {
5
        for (int j = 0; j < b.size(); ++j) {
6
            c[i + j] += a[i] * b[j];
7
        }
8
    }
9

10
    int t = 0;
11
    for (int i = 0; i < c.size(); ++i) {
12
        t += c[i];
13
        c[i] = t % 10;
14
        t /= 10;
15
    }
16

17
    while (c.size() > 1 && c.back() == 0) c.pop_back();
18
    return c;
19
}

高 / 高#

1
bool cmp(vector<int>& a, vector<int>& b) {
2
    if (a.size() != b.size()) return a.size() > b.size();
3
    for (int i = a.size() - 1; i >= 0; --i)
4
        if (a[i] != b[i]) return a[i] > b[i];
5
    return true;
6
}
7

8
vector<int> div(vector<int>& a, vector<int>& b, vector<int>& r) {
9
    vector<int> c;
10
    r.clear();
11

12
    for (int i = a.size() - 1; i >= 0; --i) {
13
        r.insert(r.begin(), a[i]);
14

15
        while (r.size() > 1 && r.back() == 0) r.pop_back();
16

17
        int x = 0;
18
        while (cmp(r, b)) {
19
            r = sub(r, b);
20
            x++;
21
        }
22

23
        c.push_back(x);
24
    }
25

26
    reverse(c.begin(), c.end());
27
    while (c.size() > 1 && c.back() == 0) c.pop_back();
28

29
    return c;
30
}

多项式#

基础约定#

1
// a[i] 表示 x^i 的系数（低位在前）
2
using poly = vector<int>;
3

4
const int mod = 998244353;
5
const int G = 3;

加法#

1
poly add(poly a, poly b) {
2
    if (a.size() < b.size()) swap(a, b);
3
    for (int i = 0; i < b.size(); ++i)
4
        a[i] = (a[i] + b[i]) % mod;
5
    return a;
6
}

减法#

1
poly sub(poly a, poly b) {
2
    if (a.size() < b.size()) a.resize(b.size());
3
    for (int i = 0; i < b.size(); ++i)
4
        a[i] = (a[i] - b[i] + mod) % mod;
5

6
    while (a.size() > 1 && a.back() == 0) a.pop_back();
7
    return a;
8
}

朴素乘法#

1
poly mul(poly a, poly b) {
2
    poly c(a.size() + b.size() - 1);
3

4
    for (int i = 0; i < a.size(); ++i)
5
        for (int j = 0; j < b.size(); ++j)
6
            c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % mod;
7

8
    return c;
9
}

NTT乘除法#

快速幂#

1
int qpow(int a, int b) {
2
    int res = 1;
3
    while (b) {
4
        if (b & 1) res = 1LL * res * a % mod;
5
        a = 1LL * a * a % mod;
6
        b >>= 1;
7
    }
8
    return res;
9
}
10

11
int inv(int x) {
12
    return qpow(x, mod - 2);
13
}

核心#

1
void ntt(poly &a, bool invert) {
2
    int n = a.size();
3
    static vector<int> rev;
4
    static vector<int> roots{0, 1};
5

6
    if ((int)rev.size() != n) {
7
        int k = __builtin_ctz(n);
8
        rev.resize(n);
9
        for (int i = 0; i < n; ++i)
10
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
11
    }
12

13
    if ((int)roots.size() < n) {
14
        int k = __builtin_ctz(roots.size());
15
        roots.resize(n);
16
        while ((1 << k) < n) {
17
            int e = qpow(G, (mod - 1) >> (k + 1));
18
            for (int i = 1 << (k - 1); i < (1 << k); ++i) {
19
                roots[2 * i] = roots[i];
20
                roots[2 * i + 1] = 1LL * roots[i] * e % mod;
21
            }
22
            k++;
23
        }
24
    }
25

26
    for (int i = 0; i < n; ++i)
27
        if (i < rev[i]) swap(a[i], a[rev[i]]);
28

29
    for (int len = 1; len < n; len <<= 1) {
30
        for (int i = 0; i < n; i += 2 * len) {
31
            for (int j = 0; j < len; ++j) {
32
                int u = a[i + j];
33
                int v = 1LL * a[i + j + len] * roots[len + j] % mod;
34
                a[i + j] = (u + v) % mod;
35
                a[i + j + len] = (u - v + mod) % mod;
36
            }
37
        }
38
    }
39

40
    if (invert) {
41
        reverse(a.begin() + 1, a.end());
42
        int inv_n = inv(n);
43
        for (int &x : a) x = 1LL * x * inv_n % mod;
44
    }
45
}

NTT乘法#

1
poly mul_ntt(poly a, poly b) {
2
    int n = 1;
3
    while (n < a.size() + b.size()) n <<= 1;
4

5
    a.resize(n);
6
    b.resize(n);
7

8
    ntt(a, false);
9
    ntt(b, false);
10

11
    for (int i = 0; i < n; ++i)
12
        a[i] = 1LL * a[i] * b[i] % mod;
13

14
    ntt(a, true);
15

16
    return a;
17
}

NTT带余除法#

1
poly rev(poly a) {
2
    reverse(a.begin(), a.end());
3
    return a;
4
}
5

6
poly poly_div(poly a, poly b) {
7
    int n = a.size() - 1;
8
    int m = b.size() - 1;
9

10
    if (n < m) return {0};
11

12
    int k = n - m + 1;
13

14
    poly ra = rev(a);
15
    poly rb = rev(b);
16

17
    rb.resize(k);
18

19
    poly inv_rb = poly_inv(rb, k);
20

21
    poly rq = mul_ntt(ra, inv_rb);
22
    rq.resize(k);
23

24
    poly q = rev(rq);
25
    return q;
26
}
27

28
poly poly_mod(poly a, poly b) {
29
    poly q = poly_div(a, b);
30
    poly prod = mul_ntt(b, q);
31

32
    poly r = sub(a, prod);
33

34
    r.resize(b.size() - 1);
35

36
    while (r.size() > 1 && r.back() == 0) r.pop_back();
37
    return r;
38
}
39

40
pair<poly, poly> poly_divmod(poly a, poly b) {
41
    poly q = poly_div(a, b);
42
    poly r = poly_mod(a, b);
43
    return {q, r};
44
}

乘法逆元#

1
poly poly_inv(poly a, int n) {
2
    if (n == 1) return {inv(a[0])};
3

4
    poly b = poly_inv(a, (n + 1) >> 1);
5

6
    int size = 1;
7
    while (size < 2 * n) size <<= 1;
8

9
    poly tmp = a;
10
    tmp.resize(size);
11
    b.resize(size);
12

13
    ntt(tmp, false);
14
    ntt(b, false);
15

16
    for (int i = 0; i < size; ++i)
17
        b[i] = 1LL * b[i] * (2 - 1LL * tmp[i] * b[i] % mod + mod) % mod;
18

19
    ntt(b, true);
20
    b.resize(n);
21

22
    return b;
23
}

导数#

1
poly deriv(poly a) {
2
    if (a.size() == 1) return {0};
3
    for (int i = 1; i < a.size(); ++i)
4
        a[i - 1] = 1LL * a[i] * i % mod;
5
    a.pop_back();
6
    return a;
7
}

积分#

1
poly integ(poly a) {
2
    a.push_back(0);
3
    for (int i = a.size() - 1; i > 0; --i)
4
        a[i] = 1LL * a[i - 1] * inv(i) % mod;
5
    a[0] = 0;
6
    return a;
7
}

多项式ln#

1
poly poly_ln(poly a, int n) {
2
    poly da = deriv(a);
3
    poly inva = poly_inv(a, n);
4

5
    poly res = mul_ntt(da, inva);
6
    res.resize(n - 1);
7

8
    return integ(res);
9
}

多项式exp#

1
poly poly_exp(poly a, int n) {
2
    if (n == 1) return {1};
3

4
    poly b = poly_exp(a, (n + 1) >> 1);
5

6
    poly ln_b = poly_ln(b, n);
7

8
    poly diff = sub(a, ln_b);
9
    diff[0] = (diff[0] + 1) % mod;
10

11
    b = mul_ntt(b, diff);
12
    b.resize(n);
13

14
    return b;
15
}

多项式快速幂#

1
poly poly_pow(poly a, int k, int n) {
2
    poly ln_a = poly_ln(a, n);
3

4
    for (int &x : ln_a)
5
        x = 1LL * x * k % mod;
6

7
    return poly_exp(ln_a, n);
8
}

线性基#

普通#

1
struct LinearBasis {
2
    static const int LOG = 60; // long long
3

4
    long long d[LOG + 1]{};
5

6
    // 插入一个数
7
    void insert(long long x) {
8
        for (int i = LOG; i >= 0; --i) {
9
            if (!(x >> i & 1)) continue;
10

11
            if (!d[i]) {
12
                d[i] = x;
13
                return;
14
            }
15

16
            x ^= d[i];
17
        }
18
    }
19

20
    // 查询最大异或值
21
    long long query_max() {
22
        long long res = 0;
23
        for (int i = LOG; i >= 0; --i)
24
            res = max(res, res ^ d[i]);
25
        return res;
26
    }
27
};

可求第k小#

1
struct LinearBasis {
2
    static const int LOG = 60;
3
    long long d[LOG + 1]{};
4
    vector<long long> p; // 重构后的基
5

6
    void insert(long long x) {
7
        for (int i = LOG; i >= 0; --i) {
8
            if (!(x >> i & 1)) continue;
9
            if (!d[i]) {
10
                d[i] = x;
11
                return;
12
            }
13
            x ^= d[i];
14
        }
15
    }
16

17
    // 重构（变成上三角）
18
    void rebuild() {
19
        for (int i = 0; i <= LOG; ++i)
20
            for (int j = 0; j < i; ++j)
21
                if (d[i] >> j & 1)
22
                    d[i] ^= d[j];
23

24
        for (int i = 0; i <= LOG; ++i)
25
            if (d[i]) p.push_back(d[i]);
26
    }
27

28
    // 第 k 小（0-based）
29
    long long kth(long long k) {
30
        if (k >= (1LL << p.size())) return -1;
31

32
        long long res = 0;
33
        for (int i = 0; i < p.size(); ++i)
34
            if (k >> i & 1)
35
                res ^= p[i];
36
        return res;
37
    }
38
};

高斯消元#

浮点数#

1
const int N = 110;
2
const double eps = 1e-8;
3

4
double a[N][N]; // 增广矩阵 n 行 n+1 列
5

6
// 返回值：
7
// 0 = 无解
8
// 1 = 唯一解
9
// 2 = 无穷多解
10
int gauss(int n) {
11
    int r = 0, c = 0;
12

13
    while (c < n) {
14
        // 1️ 找主元（绝对值最大）
15
        int t = r;
16
        for (int i = r; i < n; ++i)
17
            if (fabs(a[i][c]) > fabs(a[t][c]))
18
                t = i;
19

20
        // 2️ 这一列全是0 → 自由变量
21
        if (fabs(a[t][c]) < eps) {
22
            c++;
23
            continue;
24
        }
25

26
        // 3️ 换行
27
        for (int j = c; j <= n; ++j)
28
            swap(a[t][j], a[r][j]);
29

30
        // 4️ 归一化
31
        double div = a[r][c];
32
        for (int j = c; j <= n; ++j)
33
            a[r][j] /= div;
34

35
        // 5️ 消元（上下都消）
36
        for (int i = 0; i < n; ++i) {
37
            if (i != r && fabs(a[i][c]) > eps) {
38
                double factor = a[i][c];
39
                for (int j = c; j <= n; ++j)
40
                    a[i][j] -= factor * a[r][j];
41
            }
42
        }
43

44
        r++, c++;
45
    }
46

47
    // 6️ 判断解的情况
48
    for (int i = r; i < n; ++i)
49
        if (fabs(a[i][n]) > eps)
50
            return 0; // 无解
51

52
    return r < n ? 2 : 1;
53
}

模2高斯消元#

1
const int N = 110;
2

3
int a[N][N]; // n 行 n+1 列，值为 0/1
4

5
// 返回：0无解，1唯一解，2多解
6
int gauss_xor(int n) {
7
    int r = 0;
8

9
    for (int c = 0; c < n; ++c) {
10
        int t = r;
11
        for (int i = r; i < n; ++i)
12
            if (a[i][c]) {
13
                t = i;
14
                break;
15
            }
16

17
        if (!a[t][c]) continue;
18

19
        for (int j = c; j <= n; ++j)
20
            swap(a[t][j], a[r][j]);
21

22
        for (int i = 0; i < n; ++i)
23
            if (i != r && a[i][c])
24
                for (int j = c; j <= n; ++j)
25
                    a[i][j] ^= a[r][j];
26

27
        r++;
28
    }
29

30
    for (int i = r; i < n; ++i)
31
        if (a[i][n]) return 0;
32

33
    return r < n ? 2 : 1;
34
}

音乐

音乐

4-抽象代数

代数结构#

⊕\oplus⊕#

& 和 |和max和min#

&

|#

max#

min#

高精度#

高 + 高#

高 - 高#

高 * 低#

高 / 低#

高 * 高#

高 / 高#

多项式#

基础约定#

加法#

减法#

朴素乘法#

NTT乘除法#

快速幂#

核心#

NTT乘法#

NTT带余除法#

乘法逆元#

导数#

积分#

多项式ln#

多项式exp#

多项式快速幂#

线性基#

普通#

可求第k小#

高斯消元#

浮点数#

模2高斯消元#

文章分享

评论区

音乐

目录

$\oplus$ #