Horace He Chillee
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int binExp(int b, int pw) { | |
| if (pw == 0) | |
| return 1; | |
| return binExp(b * b % MOD, pw / 2) * (pw & 1 ? b : 1) % MOD; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ll bin_exp(ll base, ll exp){ | |
| if (exp==0) return 1; | |
| return bin_exp(base*base%MOD, exp/2)*(exp%2==1 ? base : 1)%MOD; | |
| } | |
| ll mod_inv(ll a){ | |
| return bin_exp(a, MOD-2); | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define all(x) begin(x), end(x) | |
| typedef long long ll; | |
| using namespace std; | |
| signed main() { | |
| ios::sync_with_stdio(0); | |
| cin.tie(0); | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| struct Trie { | |
| const static int MAXCHAR = 26; | |
| struct Vertex { | |
| int nxt[MAXCHAR]; | |
| bool leaf = false; | |
| Vertex() { fill(begin(nxt), end(nxt), -1); } | |
| int &operator[](int x) { return nxt[x]; } | |
| }; | |
| Trie() : trie(1) {} | |
| vector<Vertex> trie; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| vector<int> Z(string S) { // z[i] = Longest common prefix of S[i:] and S | |
| vector<int> z(S.size()); | |
| for (int i = 1, l = -1, r = -1; i < S.size(); i++) { | |
| z[i] = i >= r ? 0 : min(r - i, z[i - l]); | |
| while (i + z[i] < S.size() && S[i + z[i]] == S[z[i]]) | |
| z[i]++; | |
| if (i + z[i] > r) | |
| l = i, r = i + z[i]; | |
| } | |
| return z; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| struct AhoCorasick { | |
| struct Vertex { | |
| int next[MAXCHAR], go[MAXCHAR]; | |
| int leaf = -1; | |
| int p = -1; | |
| char pch; | |
| int link = -1, leaflink = -1; | |
| Vertex(int p = -1, char ch = '$') : p(p), pch(ch) { | |
| fill(begin(next), end(next), -1); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| vector<array<int, 2>> adj[MAXN]; | |
| int dist[MAXN]; | |
| void dijkstra(int start) { | |
| fill(begin(dist), end(dist), INF); | |
| priority_queue<array<int, 2>, vector<array<int,2>>, greater<array<int, 2>>> pq; | |
| pq.push({0, start}); | |
| while (!pq.empty()) { | |
| auto t = pq.top(); | |
| pq.pop(); | |
| if (dist[t[1]] <= t[0]) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| template <int MAXN> struct SCC { | |
| int num[MAXN], low[MAXN]; | |
| bool curProcess[MAXN]; | |
| stack<int> curVis; | |
| int dfsCnt = 0; | |
| SCC() { fill(begin(num), end(num), -1), fill(begin(low), end(low), -1); } | |
| void dfs(int cur) { | |
| num[cur] = low[cur] = dfsCnt++; | |
| curProcess[cur] = true; | |
| curVis.push(cur); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| struct H { | |
| ull x; | |
| H(ull x = 0) : x(x) {} | |
| ull get() const { return x; } | |
| const static ull M = (1ull << 61) - 1; | |
| H operator+(H o) { | |
| o.x += x + 1; | |
| o.x = (o.x & M) + (o.x >> 61); | |
| return o.x - 1; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| bool vis[MAXN]; | |
| void topodfs(int cur, vector<int> &ans) { | |
| if (vis[cur]) | |
| return; | |
| vis[cur] = true; | |
| for (auto i : adj[cur]) | |
| topodfs(i, ans); | |
| ans.push_back(cur); | |
| } | |
| vector<int> toposort() { |
OlderNewer