Skip to content
TechMind

数学

高斯消元🧀

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vec vector
#define fir first
#define sec second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mxe max_element
#define mne min_element
#define ppc __builtin_popcount
#define ctz __builtin_ctzll
#define clz __builtin_clzll
#define pcs(n) cout << fixed << setprecision(n)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef unsigned long long ull;
typedef __int128_t lll;
const int mod = 998244353;
const int N = 200005;
const int inf = 0x3f3f3f3f3f3f3f;
const int bs = 433;
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const double eps = 1e-8;

// 高斯消元法解线性方程组
int gauss(vector<vector<double>> &a)
{
    int n = a.size();
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r;
        // 找到当前列绝对值最大的行
        for (int i = r; i < n; i++)
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if (fabs(a[t][c]) < eps)
            continue;

        // 将绝对值最大的行换到最顶端
        for (int i = c; i <= n; i++)
            swap(a[t][i], a[r][i]);

        // 将当前行的首位变成1
        for (int i = n; i >= c; i--)
            a[r][i] /= a[r][c];

        // 用当前行将下面所有的列消成0
        for (int i = r + 1; i < n; i++)
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];
        r++;
    }
    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps)
                return -1; // 无解
        return 0;          // 无穷多解
    }
    // 回代求解
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];
    return 1; // 有唯一解
}

void Thirstarfish()
{
    int n;
    cin >> n;
    vector<vector<double>> a(n, vector<double>(n + 1));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            cin >> a[i][j];
    int res = gauss(a);
    if (res == -1)
        cout << -1 << endl;
    else if (res == 0)
        cout << 0 << endl;
    else
    {
        pcs(2);
        for (int i = 0; i < n; i++)
            cout << "x" << i + 1 << "=" << a[i][n] << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _; // 如果是单测记得注释掉这一行
    while (_--)
        Thirstarfish();
    return 0;
}

拉格朗日插值🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vec vector
#define fir first
#define sec second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mxe max_element
#define mne min_element
#define ppc __builtin_popcount
#define ctz __builtin_ctzll
#define clz __builtin_clzll // 二进制前导零的个数
#define pcs(n) cout << fixed << setprecision(n)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef unsigned long long ull;
typedef __int128_t lll;
const int mod = 998244353;
const int N = 200005;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int bs = 433;
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

ll fast_pow(ll a, ll b)
{
    ll ans = 1;
    a %= mod; // 先取模，防止a过大
    while (b)
    {
        if (b & 1)
        { // 等价于 b % 2
            ans = (ans * a) % mod;
        }
        b >>= 1; // 等价于 b /= 2
        a = (a * a) % mod;
    }
    return ans;
}

ll inv(int a, int b)
{
    return a * fast_pow(b, mod - 2) % mod;
}

void Thirstarfish()
{
    int n, k, _x, _y, ans = 0;
    cin >> n >> k;
    vec<int> x{0}, y{0};
    for (int i = 1; i <= n; i++)
    {
        cin >> _x >> _y;
        x.pb(_x);
        y.pb(_y);
    }
    for (int i = 1; i <= n; i++)
    {
        ll a = y[i], b = 1;
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            a = a * (k - x[j]) % mod;
            b = b * (x[i] - x[j]) % mod;
        }
        ans = (ans + inv(a, b)) % mod;
    }
    cout << (ans + mod) % mod << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _; // 如果是单测记得注释掉这一行
    while (_--)
        Thirstarfish();
    return 0;
}

线性基🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct LB
{
    vector<ll> p;
    int cnt;
    const int base = 60;
    bool flag;
    LB() : cnt(0), flag(0) { p.assign(base, 0); };

    LB operator+(const LB &other) const
    {
        LB ans = other;
        for (int i = base - 1; i >= 0; i--)
            if (p[i])
                ans.insert(p[i]);
        return ans;
    }

    bool insert(ll x)
    {
        for (int i = base - 1; i >= 0; i--)
        {
            if (!(x >> i))
                continue;
            if (!p[i])
            {
                for (int j = i - 1; j >= 0; j--)
                    if (p[j] && (x >> j & 1))
                        x ^= p[j];
                for (int j = base - 1; j > i; j--)
                    if (p[j] && (p[j] >> i & 1))
                        p[j] ^= x;
                p[i] = x;
                cnt++;
                return true;
            }
            x ^= p[i];
        }
        flag = true;
        return false;
    }

    bool check(ll x)
    {
        for (int i = base - 1; i >= 0; i--)
            if (x >> i & 1)
            {
                if (!p[i])
                    return false;
                x ^= p[i];
            }
        return true;
    }

    ll querymx()
    {
        ll ans = 0;
        for (int i = base - 1; i >= 0; i--)
            ans ^= p[i];
        return ans;
    }

    ll querymn()
    {
        if (flag)
            return 0;
        for (int i = 0; i <= base - 1; i++)
            if (p[i])
                return p[i];
    }

    ll kth(ll k)
    {
        if (flag)
            k--;
        if (k == 0)
            return 0;
        if (k >= 1ll << cnt)
            return -1;
        ll ans = 0;
        int idx = 0;
        for (int i = 0; i <= base - 1; i++)
            if (p[i])
            {
                if (k >> idx & 1)
                    ans ^= p[i];
                idx++;
            }
        return ans;
    }
};

EXGCD🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

ll inv(ll a, ll mod)
{
    ll x, y;
    ll d = exgcd(a, mod, x, y);
    if(d > 1)
        return 0;
    return (x % mod + mod) % mod;
}

EXCRT🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct exCRT
{
    // x ≡ r (mod m)
    struct Equation
    {
        ll m, r;
    };

    vector<Equation> eqs;

    void add(ll m, ll r) { eqs.push_back({m, (r % m + m) % m}); }

    ll exgcd(ll a, ll b, ll &x, ll &y)
    {
        if (!b)
        {
            x = 1;
            y = 0;
            return a;
        }
        ll d = exgcd(b, a % b, y, x);
        y -= (a / b) * x;
        return d;
    }

    ll work()
    {
        if (eqs.empty())
            return 0;
        ll M = eqs[0].m, R = eqs[0].r;
        for (size_t i = 1; i < eqs.size(); ++i)
        {
            ll m = eqs[i].m, r = eqs[i].r;
            ll x, y;
            ll d = exgcd(M, m, x, y);
            ll c = (r % m - R % m + m) % m;
            if (c % d != 0)
                return -1;
            ll step = m / d;
            x = (ll)((lll)(x % step + step) % step * (c / d) % step);
            R = (ll)((R + (lll)M * x) % (M * step));
            M *= step;
        }
        return (R % M + M) % M;
    }
};