跳转至

模板

这里用来放一些常用的模板，主要是有些东西不想放到 User snippet 里面。

其实我对模板依赖性不是很强，所以这里东西比较少。

起手式ψ(｀∇´)ψ

通用模板ψ(｀∇´)ψ

 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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);



    return 0;
}

注意如果是交互题要把 endl 的 define 删掉。

Freopenψ(｀∇´)ψ

1
2
3
4
5
#ifndef Enonya
    string fileName = "";
    freopen((fileName + ".in").c_str(), "r", stdin);
    freopen((fileName + ".out").c_str(), "w", stdout);
#endif

快速 IOψ(｀∇´)ψ

取消流同步ψ(｀∇´)ψ

1
2
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

注意取消流同步之后输出会统一集合到一起。

exceptions 是用来判读入是否合法的，不合法会 RE，用来查错。

FastIOψ(｀∇´)ψ

抄的 lcx 的并魔改了一下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <cctype>

template <typename __Tp> void read(__Tp &x) {
    int f = x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
void read(char &ch) { for (ch = getchar(); isspace(ch); ch = getchar()); }
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &... y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
void write(const char *s) { fputs(s, stdout); }
void write(string s) { write(s.c_str()); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ... y) { write(x), write(y...); }

自动取模ψ(｀∇´)ψ

抄的 Atcoder-modint，但是是从佳爸那里 copy 的，可能被佳爸魔改过，因为还带了 BR。

略微做了一点改动。

  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
107
108
109
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
  public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
struct dynamic_modint {
    using _mint = dynamic_modint;
  public:
    static void set_mod(int m) { assert(1 <= m), bt = Barrett_Reduction(m); }
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    dynamic_modint() :_v(0) {}
    template<class __Tp> dynamic_modint(__Tp v) { i64 x = v % (int)bt.m; _v = x < 0 ? x + bt.m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == bt.m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = bt.m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v += bt.m - rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator *= (const _mint& rhs) { _v = bt.mul(_v, rhs._v); return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const { auto eg = inv_gcd(_v, bt.m); assert(eg.first == 1); return eg.second; }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static Barrett_Reduction bt;
};
using modint = dynamic_modint;
using barrett = Barrett_Reduction;

// using modint = static_modint<998244353>;
barrett modint::bt = 998244353;

void read(modint &x) { i64 __value; read(__value); x = __value; return; } 
void write(modint x) { write(x.val()); }

火车头ψ(｀∇´)ψ

1
2
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast", "inline", "-ffast-math")

对拍ψ(｀∇´)ψ

Bash（抄的佳爸的）:

1
2
3
4
5
6
7
while true; do
    ./gen > _in
    ./bf < _in > _ans
    ./my < _in > _usr
    diff _ans _usr
    if [ $? -ne 0 ] ; then break; fi
done

cmd

1
2
3
4
5
6
7
:loop
    gen.exe > _in
    bf.exe < _in > _ans
    my.exe < _in > _usr
    fc _ans _usr
    if %errorlevel%==0 goto loop
pause
最后更新: October 12, 2023