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
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/extc++.h>
#include <cassert>
using namespace std;
// using namespace __gnu_pbds;
#define int long long
#define endl '\n'
typedef long long ll;
typedef array<int, 2> aii;
typedef unsigned long long ull;
typedef long double ld;
typedef __int128_t lll;
constexpr int mod = 998244353;
constexpr int inf = LLONG_MAX / 2;
const vector<array<int, 2>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void cold_beans()
{

}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);
    int _ = 1;
    cin >> _;
    while (_--)
        cold_beans();
    return 0;
}

fpow/inv/C/P🧀

 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
ll fpow(ll a, ll b)
{
    ll ans = 1;
    a %= mod; 
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

ll inv(int b) { return fpow(b, mod - 2) % mod; }

vector<ll> fac(N), ifac(N);

void initc(int n)
{
    fac[0] = 1;
    for (int i = 1; i < n; i++)
        fac[i] = fac[i - 1] * i % mod;
    ifac[n - 1] = inv(fac[n - 1]); 
    for (int i = n - 2; i >= 0; i--)
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
}

ll C(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    return fac[n] * ifac[k] % mod * ifac[n - k] % mod;
}

ll P(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    return fac[n] * ifac[n - k] % mod;
}

lll🧀

1
2
lll a = 0;
cout << format("{}", a) << endl;

sieve&minp🧀

 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
vector<int> eulerSieve(int n)
{
    vector<char> isPrime(n + 1, 1);
    vector<int> primes;            
    isPrime[0] = isPrime[1] = 0; 
    for (int i = 2; i <= n; ++i)
    {
        if (isPrime[i])
            primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
        {
            isPrime[i * primes[j]] = 0; 
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

template <typename T>
vector<T> preprocess_min_prime(T n)
{
    vector<T> min_prime(n + 1); 
    vector<T> primes;          
    for (T i = 0; i <= n; i++)
        min_prime[i] = i;
    for (T i = 2; i <= n; i++)
    {
        if (min_prime[i] == i)
            primes.push_back(i);
        for (size_t j = 0; j < primes.size(); j++)
        {
            T p = primes[j];
            if (p * i > n)
                break; 
            min_prime[p * i] = p; 
            if (i % p == 0)
                break;
        }
    }
    return min_prime;
}

umap hash🧀

 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
struct chash
{
    static uint64_t u64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const
    {
        static const uint64_t rg = chrono::steady_clock::now().time_since_epoch().count();
        return u64(x + rg);
    }

    template <typename T1, typename T2>
    size_t operator()(const pair<T1, T2> &p) const
    {
        static const uint64_t rg = chrono::steady_clock::now().time_since_epoch().count();
        uint64_t h1 = u64(p.first + rg);
        uint64_t h2 = u64(p.second + rg);
        return h1 ^ (h2 + 0x9e3779b97f4a7c15 + (h1 << 6) + (h1 >> 2));
    }

    template <typename Range>
    size_t operator()(const Range &arr) const
    {
        static const uint64_t rg = chrono::steady_clock::now().time_since_epoch().count();
        uint64_t hash = 0;
        for (auto x : arr)
            hash ^= u64(x + rg) + 0x9e3779b97f4a7c15 + (hash << 6) + (hash >> 2);
        return hash;
    }
};

zmod🧀

  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
using i64 = long long;

template <class T>
constexpr T fpow(T n, i64 k)
{
    T r = 1;
    for (; k; k >>= 1, n *= n)
        if (k & 1)
            r *= n;
    return r;
}

template <int MOD>
struct Zmod
{
    int x;

    constexpr Zmod(int x = 0) : x(norm(x % MOD)) {}

    static constexpr int norm(int x)
    {
        if (x < 0) x += MOD;
        if (x >= MOD) x -= MOD;
        return x;
    }

    constexpr int val() const { return x; }

    constexpr Zmod operator-() const
    {
        return Zmod(MOD - x);
    }

    constexpr Zmod inv() const
    {
        assert(x != 0);
        return fpow(*this, MOD - 2);
    }

    /* IO */
    friend std::istream &operator>>(std::istream &in, Zmod &a)
    {
        int v;
        in >> v;
        a = Zmod(v);
        return in;
    }

    friend std::ostream &operator<<(std::ostream &out, const Zmod &a)
    {
        return out << a.val();
    }

    /* 自增自减 */
    constexpr Zmod &operator++() { return x = norm(x + 1), *this; }
    constexpr Zmod &operator--() { return x = norm(x - 1), *this; }

    /* 复合赋值 */
    constexpr Zmod &operator+=(const Zmod &o)
    {
        x = norm(x + o.x);
        return *this;
    }

    constexpr Zmod &operator-=(const Zmod &o)
    {
        x = norm(x - o.x);
        return *this;
    }

    constexpr Zmod &operator*=(const Zmod &o)
    {
        x = (i64)x * o.x % MOD;
        return *this;
    }

    constexpr Zmod &operator/=(const Zmod &o)
    {
        return *this *= o.inv();
    }

    /* 二元运算 */
    friend constexpr Zmod operator+(Zmod a, const Zmod &b) { return a += b; }
    friend constexpr Zmod operator-(Zmod a, const Zmod &b) { return a -= b; }
    friend constexpr Zmod operator*(Zmod a, const Zmod &b) { return a *= b; }
    friend constexpr Zmod operator/(Zmod a, const Zmod &b) { return a /= b; }

    /* 比较 */
    friend constexpr bool operator==(const Zmod &a, const Zmod &b) { return a.x == b.x; }
    friend constexpr bool operator!=(const Zmod &a, const Zmod &b) { return a.x != b.x; }
    friend constexpr bool operator<(const Zmod &a, const Zmod &b) { return a.x < b.x; }
    friend constexpr bool operator>(const Zmod &a, const Zmod &b) { return a.x > b.x; }
};

constexpr int MOD[] = {998244353, 1000000007};
using Z = Zmod<MOD[0]>;

/* 示例：2^n */
Z power(int n)
{
    return fpow(Z(2), n);
}

三分🧀

整数三分🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int l = 1, r = 1e9, ans = inf;
while (r - l > 3)
{
    int m1 = l + (r - l) / 3;
    int m2 = r - (r - l) / 3;
    if (calc(m1, i) >= calc(m2, i))
        l = m1;
    else
        r = m2;
}
for (int j = l; j <= r; j++)
    ans = min(ans, calc(j, i));

实数三分🧀

 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
auto calc = [&](double x) -> double 
{

};

auto ternary = [&](double l, double r) -> double
{
    const double PHI = (sqrt(5.0) - 1.0) / 2.0;
    double m1 = r - PHI * (r - l);
    double m2 = l + PHI * (r - l);
    double f1 = calc(m1);
    double f2 = calc(m2);

    while (r - l > eps)
        if (f1 < f2)
        {
            l = m1;
            m1 = m2;
            f1 = f2;
            m2 = l + PHI * (r - l);
            f2 = calc(m2);
        }
        else
        {
            r = m2;
            m2 = m1;
            f2 = f1;
            m1 = r - PHI * (r - l);
            f1 = calc(m1);
        }
    return (l + r) / 2.0;
};

random🧀

1
2
3
4
5
6
7
static random_device rd;
static mt19937 g(rd());

shuffle(a.begin() + 1, a.end(), g); // 随机打乱数组

uniform_real_distribution<double> dist01(0.0, 1.0); // [0,1)
uniform_real_distribution<double> dist11(-1.0, 1.0); // [-1,1)

模拟退火🧀

 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
const int down = 0.997;

auto start = clock();

static random_device rd;
static mt19937 g(rd());
uniform_real_distribution<double> dist01(0.0, 1.0);  // [0,1)
uniform_real_distribution<double> dist11(-1.0, 1.0); // [-1,1)

auto TIME = [&]() -> double
{ return (double)(clock() - start) / CLOCKS_PER_SEC; };

auto cal = [&](double x, double y) -> double
{
    // 代价函数
};

x /= n, y /= n, w = cal(x, y);
double bx = x, by = y, bw = w;

auto anneal = [&]() -> void
{
    double t = 3000;
    while (t > 1e-9)
    {
        double ex = x + dist11(g) * t * 1e4;
        double ey = y + dist11(g) * t * 1e4;
        double ew = cal(ex, ey);
        double de = ew - w; // 注意代价越大越好还是越小越好

        if (de < 0)
        {
            x = ex;
            y = ey;
            w = ew;
        }
        else if (exp(-de / t) > dist01(g))
        {
            x = ex;
            y = ey;
            w = ew;
        }
        if (w < bw)
        {
            bw = w;
            bx = x;
            by = y;
        }
        t *= down;
    }
};