Untitled

 avatar
unknown
plain_text
3 months ago
24 kB
4
Indexable
{
	"Base Template": {
	  "prefix": "cpcpp",
	  "body": [
		"// Authored by Gaurav Kabra",
		"#include <bits/stdc++.h>",
		"using namespace std;",
		"#define ll long long",
		"#define vll vector<long long>",
		"#define vi vector<int>",
		"#define vpll vector<pair<long long, long long>>",
		"#define mll map<long long, long long>",
		"#define pb push_back",
		"#define mp make_pair",
		"#define fi first",
		"#define se second",
		"#define yes cout << \"Yes\\n\"",
		"#define no cout << \"No\\n\"",
		"#define mod 1000000007",
		"#define endl \"\\n\"",
		"#define invll(x, n) \\",
		"    vll x(n);       \\",
		"    rep(i, 0, n) cin >> x[i];",
		"#define invi(x, n) \\",
		"    vi x(n);       \\",
		"    rep(i, 0, n) cin >> x[i];",
		"#define inarrll(x, n) \\",
		"    ll x[n];          \\",
		"    rep(i, 0, n) cin >> x[i];",
		"#define inarrint(x, n) \\",
		"    int x[n];          \\",
		"    rep(i, 0, n) cin >> x[i];",
		"#define makegraph(graph, edges)    \\",
		"    for (ll i = 0; i < edges; i++) \\",
		"    {                              \\",
		"        ll a, b;                   \\",
		"        cin >> a >> b;             \\",
		"        graph[a].pb(b);            \\",
		"        graph[b].pb(a);            \\",
		"    }",
		"#define inll(...)   \\",
		"    ll __VA_ARGS__; \\",
		"    read(__VA_ARGS__);",
		"#define inint(...)   \\",
		"    int __VA_ARGS__; \\",
		"    read(__VA_ARGS__);",
		"#define debug(arg) cerr << __LINE__ << \" \" << (#arg) << \"-->\" << arg << endl;",
		"#define clr(n) memset(n, 0, sizeof(n))",
		"#define all(n) n.begin(), n.end()",
		"#define lb lower_bound",
		"#define ub upper_bound",
		"#define rep(i, k, n) for (ll i = k; i < n; i++)",
		"#define repit(i, k) for (auto i = k.start(); i != n.end(); i++)",
		"#define repr(i, k, n) for (ll i = k; i >= n; i--)",
		"#define repeat(n) for (ll _ = 0; _ < n; _++)",
		"#define valset(arr, size, val) rep(i, 0, size) arr[i] = val;",
		"#define setbits(x) __builtin_popcount(x)",
		"#define setbitsll(x) __builtin_popcountll(x)",
		"mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());",
		"#define orz return 0",
		"template <typename... T>",
		"void read(T &...args)",
		"{",
		"    ((cin >> args), ...);",
		"}",
		"template <typename... T>",
		"void print(T... args)",
		"{",
		"    ((cout << args << \" \"), ...);",
		"    cout << endl;",
		"}",
		"",
		"//---------IO Operator Overloading---------",
		"template <typename T>",
		"istream &operator>>(istream &is, vector<T> &v)",
		"{",
		"    for (ll i = 0; i < v.size(); i++)",
		"    {",
		"        is >> v[i];",
		"    }",
		"    return is;",
		"}",
		"template <typename T>",
		"ostream &operator<<(ostream &os, vector<T> &v)",
		"{",
		"    for (auto i : v)",
		"        os << i << \" \";",
		"    os << endl;",
		"    return os;",
		"}",
		"template <typename T>",
		"ostream &operator<<(ostream &os, set<T> &s)",
		"{",
		"    for (auto i : s)",
		"        os << i << \" \";",
		"    os << endl;",
		"    return os;",
		"}",
		"template <typename T>",
		"ostream &operator<<(ostream &os, multiset<T> &s)",
		"{",
		"    for (auto i : s)",
		"        os << i << \" \";",
		"    os << endl;",
		"    return os;",
		"}",
		"//----------------------------------------------------------",
		"",
		"#define fast                          \\",
		"    ios_base::sync_with_stdio(false); \\",
		"    cin.tie(NULL);                    \\",
		"    cout.tie(NULL);",
		"",
		"bool comp(pair<ll, ll> &a, pair<ll, ll> &b)",
		"{",
		"    return (a.se < b.se);",
		"}",
		"",
		"ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }",
		"ll binpow(ll a, ll b)",
		"{",
		"    ll res = 1;",
		"    while (b > 0)",
		"    {",
		"        if (b & 1)",
		"            res = res * a;",
		"        a = a * a;",
		"        b >>= 1;",
		"    }",
		"    return res;",
		"}",
		"",
		"//-------------Solution-------------",
		"",
		"void solve()",
		"{",
		"}",
		"",
		"signed main()",
		"{",
		"    fast;",
		"#ifndef ONLINE_JUDGE",
		"    freopen(\"Input.txt\", \"r\", stdin);",
		"    freopen(\"Output.txt\", \"w\", stdout);",
		"    freopen(\"Error.txt\", \"w\", stderr);",
		"#endif",
		"    inll(n);",
		"    // ll n = 1;",
		"    rep(i, 1, n + 1)",
		"    {",
		"        solve();",
		"    }",
		"#ifndef ONLINE_JUDGE",
		"    cerr << \"time taken : \" << (float)clock() / CLOCKS_PER_SEC << \" secs\"",
		"         << \"\\n\";",
		"#endif",
		"    orz;",
		"}"
	  ],
	  "description": "Base Template"
	},
	"Factorial Filler": {
	  "prefix": "factfill",
	  "body": [
		"factorial[0] = 1;",
		"for (ll i = 1; i < 1000001; i++){factorial[i] = (factorial[i - 1] * i) % mod;}"
	  ],
	  "description": "Factorial Filler"
	},
	"Binary Exponentiation Modulus": {
	  "prefix": "binexpm",
	  "body": [
		"ll binexpmod(ll a, ll b, ll m)",
		"{",
		"    ll res = 1;",
		"    while (b > 0)",
		"    {",
		"        if (b & 1)",
		"            res = (res * a) % m;",
		"        a = (a * a) % m;",
		"        b >>= 1;",
		"    }",
		"    return res;",
		"}"
	  ],
	  "description": "Binary Exponentiation Modulus"
	},
	"nCr": {
	  "prefix": "ncr",
	  "body": [
		"ll ncr(ll n, ll r)",
		"{",
		"    ll den = factorial[n - r] * factorial[r] % mod;",
		"    return (factorial[n] * binexpmod(den, mod - 2, mod)) % mod;",
		"}"
	  ],
	  "description": "nCr"
	},
	"Ordered Set Initialiser": {
	  "prefix": "ordset",
	  "body": [
		"#include <ext/pb_ds/assoc_container.hpp>",
		"#include <ext/pb_ds/tree_policy.hpp>",
		"using namespace __gnu_pbds;",
		"  ",
		"#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>"
	  ],
	  "description": "Ordered Set Initialiser"
	},
	"Segment Tree": {
	  "prefix": "segtree",
	  "body": [
		"#define segtree",
		"#ifdef segtree",
		"#define leftindex index * 2 + 1",
		"#define rightindex index * 2 + 2",
		"#define mid (start + end) / 2",
		"#define leftside start, mid, leftindex, seg",
		"#define rightside mid + 1, end, rightindex, seg",
		"#endif",
		" ",
		"ll mergeseg(ll leftval, ll rightval)",
		"{",
		"    return leftval + rightval;",
		"}",
		" ",
		"void maketree(ll arr[], ll start, ll end, ll index, ll seg[])",
		"{",
		"    if (start == end)",
		"    {",
		"        seg[index] = arr[start];",
		"        return;",
		"    }",
		"    maketree(arr, leftside);",
		"    maketree(arr, rightside);",
		"    seg[index] = mergeseg(seg[leftindex], seg[rightindex]);",
		"}",
		" ",
		"void update(ll left, ll right, ll value, ll start, ll end, ll index, ll seg[])",
		"{",
		"    if (left > end or right < start)",
		"        return;",
		"    else if (left <= start and end <= right)",
		"    {",
		"        if (start == end)",
		"        {",
		"            //? Change this to change update function",
		"            seg[index] = value;",
		"            return;",
		"        }",
		"        //? Update this area to make lazy",
		"        update(left, right, value, leftside);",
		"        update(left, right, value, rightside);",
		"        seg[index] = mergeseg(seg[leftindex], seg[rightindex]);",
		"    }",
		"    else",
		"    {",
		"        if (start == end)",
		"        {",
		"            //? Change this to change update function",
		"            seg[index] = value;",
		"            return;",
		"        }",
		"        update(left, right, value, leftside);",
		"        update(left, right, value, rightside);",
		"        seg[index] = mergeseg(seg[leftindex], seg[rightindex]);",
		"    }",
		"}",
		" ",
		"ll getans(ll left, ll right, ll start, ll end, ll index, ll seg[])",
		"{",
		"    if (start > right or left > end)",
		"        return 0;",
		"    else if (left <= start and end <= right)",
		"    {",
		"        return seg[index];",
		"    }",
		"    else",
		"    {",
		"        auto a = getans(left, right, leftside);",
		"        auto b = getans(left, right, rightside);",
		"        auto c = a + b;",
		"        return c;",
		"    }",
		"}"
	  ],
	  "description": "Segment Tree"
	},
	"Sieve": {
	  "prefix": "spf",
	  "body": [
		"int spf[100010];",
		"",
		"void sieve()",
		"{",
		"    for (int i = 1; i < 100010; i++)",
		"    {",
		"        spf[i] = i;",
		"    }",
		"    for (int i = 2; i < 100010; i += 2)",
		"    {",
		"        spf[i] = 2;",
		"    }",
		"    for (int i = 3; i * i < 100010; i++)",
		"    {",
		"        if (spf[i] == i)",
		"        {",
		"            for (int j = i * i; j < 100010; j += i)",
		"            {",
 		"                if (spf[j] == j)",
		"                    spf[j] = i;",
		"            }",
		"        }",
		"    }",
		"}"
	  ],
	  "description": "Sieve"
	},
	"Parent Marker with times": {
	  "prefix": "dfsparenttime",
	  "body": [
		"void dfs(int node, vector<vector<int>> &graph, vector<int> &parent)",
		"{",
		"    t_in[node] = ++tym;",
		"    for (auto ele : graph[node])",
		"    {",
		"        if (parent[node] != ele)",
		"        {",
		"            parent[ele] = node;",
		"            dfs(ele, graph, parent);",
		"        }",
		"    }",
		"    t_out[node] = ++tym;",
		"}"
	  ],
	  "description": "Parent Marker with times"
	},
	"Binary Lifting Filler": {
	  "prefix": "binarylift",
	  "body": [
		"void binary_lift(int node, vector<int> &parent, vector<vector<int>> &graph)",
		"{",
		"    par[node][0] = parent[node];",
		"    rep(i, 1, 20)",
		"    {",
		"        if (par[node][i - 1] == -1)",
		"        {",
		"            par[node][i] = -1;",
		"        }",
		"        else",
		"        {",
		"            par[node][i] = par[par[node][i - 1]][i - 1];",
		"        }",
		"    }",
		"    for (auto ele : graph[node])",
		"    {",
		"        if (ele != parent[node])",
		"        {",
		"            binary_lift(ele, parent, graph);",
		"        }",
		"    }",
		"}"
	  ],
	  "description": "Binary Lifting Filler"
	},
	"Ancestor Boolean": {
	  "prefix": "isancof",
	  "body": [
		"bool is_anc_of(int a, int b)",
		"{",
		"    return (t_in[a] <= t_in[b] and t_out[a] >= t_out[b]);",
		"}"
	  ],
	  "description": "Ancestor Boolean"
	},
	"Lowest Common Ancestor": {
	  "prefix": "lca",
	  "body": [
		"int LCA(int a, int b)",
		"{",
		"    //! Make the ancestor boolean and par binary lift",
		"    if (is_anc_of(a, b))",
		"        return a;",
		"    repr(i, 19, 0)",
		"    {",
		"        if (par[a][i] != -1 and !is_anc_of(par[a][i], b))",
		"        {",
		"            a = par[a][i];",
		"        }",
		"    }",
		"    return par[a][0];",
		"}"
	  ],
	  "description": "Lowest Common Ancestor"
	},
	"String Hashing": {
	  "prefix": "stringhash",
	  "body": [
		"ll binexpmod(ll a, ll b, ll m)",
		"{",
		"    ll res = 1;",
		"    while (b > 0)",
		"    {",
		"        if (b & 1)",
		"            res = (res * a) % m;",
		"        a = (a * a) % m;",
		"        b >>= 1;",
		"    }",
		"    return res;",
		"}",
		"",
		"ll basepowers[2][1000010], base = 31;",
		"int primes[] = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123};",
		"int pr[2];",
		"",
		"void initiateHashingTemplate()",
		"{",
		"    pr[0] = primes[abs(int(rng())) % 9];",
		"    pr[1] = primes[abs(int(rng())) % 9];",
		"    while (pr[0] == pr[1])",
		"    {",
		"        pr[1] = primes[abs(int(rng())) % 9];",
		"    }",
		"    basepowers[0][0] = 1;",
		"    basepowers[1][0] = 1;",
		"    rep(i, 1, 1000010)",
		"    {",
		"        basepowers[0][i] = ((basepowers[0][i - 1] % pr[0]) * base) % pr[0];",
		"        basepowers[1][i] = ((basepowers[1][i - 1] % pr[1]) * base) % pr[1];",
		"    }",
		"    cerr << pr[0] << \" \" << pr[1] << endl;",
		"}",
		"",
		"struct stringHash",
		"{",
		"    ll length;",
		"    ll hash[2] = {0};",
		"    // string curr;",
		"",
		"    stringHash()",
		"    {",
		"        if (!pr[0])",
		"            initiateHashingTemplate();",
		"        length = 0;",
		"    }",
		"    stringHash(string s)",
		"    {",
		"        if (!pr[0])",
		"        {",
		"            initiateHashingTemplate();",
		"        }",
		"        length = 0;",
		"        for (auto c : s)",
		"            this->push_back(c);",
		"    }",
		"",
		"    void mult(ll &a, ll b, ll c)",
		"    {",
		"        a *= b;",
		"        a %= c;",
		"    }",
		"",
		"    void add(ll &a, ll b, ll c)",
		"    {",
		"        a += (b % c);",
		"        a -= (a >= c) ? c : 0;",
		"    }",
		"",
		"    void sub(ll &a, ll b, ll c)",
		"    {",
		"        a -= (b % c);",
		"        a += (a < 0) ? c : 0;",
		"    }",
		"",
		"    void div(ll &a, ll b, ll c)",
		"    {",
		"        a *= binexpmod(b, c - 2, c);",
		"        a %= c;",
		"    }",
		"",
		"    void push_back(char c)",
		"    {",
		"        this->length++;",
		"        int val = c - 'a' + 1;",
		"        // this->curr.pb(val);",
		"        rep(i, 0, 2)",
		"        {",
		"            mult(hash[i], base, pr[i]);",
		"            add(hash[i], val, pr[i]);",
		"        }",
		"    }",
		"",
		"    void pop_back(char c)",
		"    {",
		"        this->length--;",
		"        int val = c - 'a' + 1;",
		"        // this->curr.pop_back();",
		"        rep(i, 0, 2)",
		"        {",
		"            sub(hash[i], val, pr[i]);",
		"            div(hash[i], base, pr[i]);",
		"        }",
		"    }",
		"",
		"    void push_front(char c)",
		"    {",
		"        this->length++;",
		"        int val = c - 'a' + 1;",
		"        // this->curr = c + this->curr;",
		"        rep(i, 0, 2)",
		"        {",
		"            add(hash[i], val * basepowers[i][length - 1], pr[i]);",
		"        }",
		"    }",
		"",
		"    void pop_front(char c)",
		"    {",
		"        this->length--;",
		"        int val = c - 'a' + 1;",
		"        // this->curr = this->curr.substr(1, length);",
		"        rep(i, 0, 2)",
		"        {",
		"            sub(hash[i], val * basepowers[i][length], pr[i]);",
		"        }",
		"    }",
		"",
		"    void pop_front(stringHash h)",
		"    {",
		"        int ldiff = this->length - h.length;",
		"        this->length -= h.length;",
		"        // this->curr = this->curr.substr(h.length, length);",
		"        rep(i, 0, 2)",
		"        {",
		"            mult(h.hash[i], basepowers[i][ldiff], pr[i]);",
		"            sub(hash[i], h.hash[i], pr[i]);",
		"        }",
		"    }",
		"",
		"    bool operator==(stringHash h)",
		"    {",
		"        if (this->length != h.length)",
		"            return false;",
		"        rep(i, 0, 2)",
		"        {",
		"            if (this->hash[i] != h.hash[i])",
		"            {",
		"                return false;",
		"            }",
		"        }",
		"        return true;",
		"    }",
		"",
		"    stringHash operator+(stringHash h)",
		"    {",
		"        this->length += h.length;",
		"        rep(i, 0, 2)",
		"        {",
		"            mult(hash[i], basepowers[i][h.length], pr[i]);",
		"            add(hash[i], h.hash[i], pr[i]);",
		"        }",
		"        return *this;",
		"    }",
		"",
		"    stringHash operator-(stringHash h)",
		"    {",
		"        this->length -= h.length;",
		"        rep(i, 0, 2)",
		"        {",
		"            sub(hash[i], h.hash[i], pr[i]);",
		"            div(hash[i], basepowers[i][h.length], pr[i]);",
		"        }",
		"        return *this;",
		"    }",
		"",
		"    stringHash operator=(stringHash h)",
		"    {",
		"        this->length = h.length;",
		"        rep(i, 0, 2)",
		"        {",
		"            hash[i] = h.hash[i];",
		"        }",
		"        return *this;",
		"    }",
		"};"
	  ],
	  "description": "String Hashing"
	},
	"Rabin Karp": {
	  "prefix": "rabinkarp",
	  "body": [
		"vector<int> rabin_karp(string &s, string &t)",
		"{",
		"    int a = s.size(), b = t.size();",
		"    vector<int> occurences;",
		"    vector<stringHash> prefixHashes(s.size() + 1);",
		"    prefixHashes[0].pb(s[0]);",
		"    rep(i, 1, a)",
		"    {",
		"        prefixHashes[i] = prefixHashes[i - 1];",
		"        prefixHashes[i].pb(s[i]);",
		"    }",
		"    stringHash two(t);",
		"    if (prefixHashes[b - 1] == two)",
		"    {",
		"        occurences.pb(b - 1);",
		"    }",
		"    rep(i, b, a)",
		"    {",
		"        stringHash temp = prefixHashes[i];",
		"        temp.pop_front(prefixHashes[i - b]);",
		"        if (temp == two)",
		"        {",
		"            occurences.pb(i);",
		"        }",
		"    }",
		"    return occurences;",
		"}",
		"",
		"vector<int> rabin_karp(vector<stringHash> &prefixHashes, string &t)",
		"{",
		"    int a = prefixHashes.size(), b = t.size();",
		"    vector<int> occurences;",
		"    stringHash two(t);",
		"    if (prefixHashes[b - 1] == two)",
		"    {",
		"        occurences.pb(b - 1);",
		"    }",
		"    rep(i, b, a)",
		"    {",
		"        stringHash temp = prefixHashes[i];",
		"        temp.pop_front(prefixHashes[i - b]);",
		"        if (temp == two)",
		"        {",
		"            occurences.pb(i);",
		"        }",
		"    }",
		"    return occurences;",
		"}",
		"bool rabin_karp_bool(vector<stringHash> &prefixHashes, string &t)",
		"{",
		"    int a = prefixHashes.size(), b = t.size();",
		"    stringHash two(t);",
		"    if (prefixHashes[b - 1] == two)",
		"    {",
		"        return true;",
		"    }",
		"    rep(i, b, a)",
		"    {",
		"        stringHash temp = prefixHashes[i];",
		"        temp.pop_front(prefixHashes[i - b]);",
		"        if (temp == two)",
		"        {",
		"            return true;",
		"        }",
		"    }",
		"    return false;",
		"}"
	  ],
	  "description": "Rabin Karp"
	},
	"Prefix Function for KMP": {
	  "prefix": "prefkmp",
	  "body": [
		"vector<int> prefix_function(string &s)",
		"{",
		"    int n = s.size();",
		"    vector<int> pref(n);",
		"    rep(i, 1, n)",
		"    {",
		"        int j = pref[i - 1];",
		"        while (j > 0 && s[i] != s[j])",
		"            j = pref[j - 1];",
		"        if (s[i] == s[j])",
		"            j++;",
		"        pref[i] = j;",
		"    }",
		"    return pref;",
		"}"
	  ],
	  "description": "Prefix Function for KMP"
	},
	"DSU (With Merging)": {
	  "prefix": "dsumerge",
	  "body": [
		"",
		"template <typename T>",
		"class DSU",
		"{",
		"    vector<int> root;",
		"    vector<int> sz;",
		"    vector<set<T>> elements;",
		"",
		"public:",
		"    DSU(int n)",
		"    {",
		"        root = vector<int>(n + 1);",
		"        sz = vector<int>(n + 1, 1);",
		"        elements = vector<set<int>>(n + 1);",
		"        iota(all(root), 0);",
		"        rep(i, 0, n + 1)",
		"        {",
		"            elements[i].insert(i);",
		"        }",
		"    }",
		"    int find(int x)",
		"    {",
		"        if (root[x] != x)",
		"            root[x] = find(root[x]);",
		"        return root[x];",
		"    }",
		"    void join(int x, int y)",
		"    {",
		"        x = find(x);",
		"        y = find(y);",
		"        if (x == y)",
		"            return;",
		"        if (sz[x] > sz[y])",
		"        {",
		"            swap(x, y);",
		"        }",
		"        root[x] = y;",
		"        sz[y] += sz[x];",
		"        sz[x] = 0;",
		"        for (auto i : elements[x])",
		"        {",
		"            elements[y].insert(i);",
		"            root[i] = y;",
		"        }",
		"        elements[x].clear();",
		"    }",
		"};"
	  ],
	  "description": "DSU (With Merging)"
	},
	"DSU": {
	  "prefix": "dsu",
	  "body": [
		"class DSU",
		"{",
		"    vector<int> root;",
		"    vector<int> sz;",
		"",
		"public:",
		"    DSU(int n)",
		"    {",
		"        root = vector<int>(n + 1);",
		"        sz = vector<int>(n + 1, 1);",
		"        iota(all(root), 0);",
		"    }",
		"    int find(int x)",
		"    {",
		"        if (root[x] != x)",
		"            root[x] = find(root[x]);",
		"        return root[x];",
		"    }",
		"    void join(int x, int y)",
		"    {",
		"        x = find(x);",
		"        y = find(y);",
		"        if(x == y) return;",
		"        if(sz[x] > sz[y]) swap(x, y);",
		"        sz[y] += sz[x];",
		"        sz[x] = 0;",
		"        root[x] = y;",
		"    }",
		"};"
	  ],
	  "description": "DSU"
	},
	"Dijkstra": {
		"prefix": "Dijkstra",
		"body": [
		  "priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;",
		  "    pq.push({0, src});",
		  "    vll distances(k + 1, INT_MAX);",
		  "    vll locked(k + 1);",
		  "    while (!pq.empty())",
		  "    {",
		  "        auto ele = pq.top();",
		  "        pq.pop();",
		  "        if (locked[ele.se])",
		  "            continue;",
		  "        locked[ele.se] = 1;",
		  "        distances[ele.se] = ele.fi;",
		  "        for (auto neighbour : graph[ele.se])",
		  "        {",
		  "            if (distances[neighbour.fi] > distances[ele.se] + neighbour.se)",
		  "            {",
		  "                pq.push({distances[ele.se] + neighbour.se, neighbour.fi});",
		  "            }",
		  "        }",
		  "    }"
		],
		"description": "Dijkstra"
	  },
	  "Mod Integer Struct": {
		"prefix": "modint",
		"body": [
		  "template <int MOD>",
		  "struct mint",
		  "{",
		  "    int value;",
		  "    mint() : value() {}",
		  "    mint(ll value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD",
		  "                                                                            : value_) {}",
		  "    mint(int value_, nullptr_t) : value(value_) {}",
		  "    explicit operator bool() const { return value; }",
		  "    inline mint<MOD> operator+(mint<MOD> other) const { return mint<MOD>(*this) += other; }",
		  "    inline mint<MOD> operator-(mint<MOD> other) const { return mint<MOD>(*this) -= other; }",
		  "    inline mint<MOD> operator*(mint<MOD> other) const { return mint<MOD>(*this) *= other; }",
		  "    inline mint<MOD> &operator+=(mint<MOD> other)",
		  "    {",
		  "        this->value = this->value + other.value;",
		  "        if (this->value >= MOD)",
		  "            this->value -= MOD;",
		  "        return *this;",
		  "    }",
		  "    inline mint<MOD> &operator-=(mint<MOD> other)",
		  "    {",
		  "        this->value = this->value - other.value;",
		  "        if (this->value < 0)",
		  "            this->value += MOD;",
		  "        return *this;",
		  "    }",
		  "    inline mint<MOD> &operator*=(mint<MOD> other)",
		  "    {",
		  "        this->value = ((ll)this->value * other.value) % MOD;",
		  "        return *this;",
		  "    }",
		  "    inline mint<MOD> operator-() const",
		  "    {",
		  "        return mint<MOD>(this->value ? MOD - this->value : 0, nullptr);",
		  "    }",
		  "    inline bool operator==(mint<MOD> other) const { return value == other.value; }",
		  "    inline bool operator!=(mint<MOD> other) const { return value != other.value; }",
		  "",
		  "    inline mint<MOD> pow(ll x, ll k)",
		  "    {",
		  "        ll y = 1;",
		  "        for (; k; k >>= 1)",
		  "        {",
		  "            if (k & 1)",
		  "                (y *= x) %= MOD;",
		  "            (x *= x) %= MOD;",
		  "        }",
		  "        return mint<MOD>(y);",
		  "    }",
		  "    inline mint<MOD> inv()",
		  "    {",
		  "        return pow((ll)this->value, MOD - 2);",
		  "    }",
		  "    inline mint<MOD> operator/(mint<MOD> other) const { return *this * other.inv(); }",
		  "    inline mint<MOD> &operator/=(mint<MOD> other) { return *this *= other.inv(); }",
		  "};",
		  "template <int MOD>",
		  "mint<MOD> operator+(ll value, mint<MOD> n) { return mint<MOD>(value) + n; }",
		  "template <int MOD>",
		  "mint<MOD> operator-(ll value, mint<MOD> n) { return mint<MOD>(value) - n; }",
		  "template <int MOD>",
		  "mint<MOD> operator*(ll value, mint<MOD> n) { return mint<MOD>(value) * n; }",
		  "template <int MOD>",
		  "mint<MOD> operator/(ll value, mint<MOD> n) { return mint<MOD>(value) / n; }",
		  "template <int MOD>",
		  "mint<MOD> operator+(int value, mint<MOD> n) { return mint<MOD>(value) + n; }",
		  "template <int MOD>",
		  "mint<MOD> operator-(int value, mint<MOD> n) { return mint<MOD>(value) - n; }",
		  "template <int MOD>",
		  "mint<MOD> operator*(int value, mint<MOD> n) { return mint<MOD>(value) * n; }",
		  "template <int MOD>",
		  "mint<MOD> operator/(int value, mint<MOD> n)",
		  "{",
		  "    print(value);",
		  "    return mint<MOD>(value) / n;",
		  "}",
		  "",
		  "template <int MOD>",
		  "std::istream &operator>>(std::istream &in, mint<MOD> &n)",
		  "{",
		  "    inll(value);",
		  "    n = value;",
		  "    return in;",
		  "}",
		  "template <int MOD>",
		  "std::ostream &operator<<(std::ostream &out, mint<MOD> n) { return out << n.value; }",
		  ""
		],
		"description": "Mod Integer Struct"
	  }
  }
  
Editor is loading...
Leave a Comment