### ModInt Template Example (C++) - Benq

Source: https://usaco.guide/gold/modular

An example demonstrating the usage of a ModInt template, likely from Benq's competitive programming library. It sets up a custom modulus and shows basic arithmetic operations within that modulus. Includes standard headers and a MOD constant.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MOD = 1e9 + 7;


// Code Snippet: ModInt (Click to expand)


int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;
		
	}

```

--------------------------------

### ModInt Template Example (C++) - AtCoder

Source: https://usaco.guide/gold/modular

An example using AtCoder's ModInt library, commonly available in competitive programming environments. It includes the necessary header, defines a mint type, and sets a modulus. Shows how to include and use the library.

```cpp
#include <bits/stdc++.h>
using namespace std;


// https://atcoder.github.io/ac-library/document_en/modint.html
// (included in atcoder grading)
#include <atcoder/modint>
using mint = atcoder::modint;


const int MOD = 1e9 + 7;



```

--------------------------------

### ModInt Template Example (Benq's C++)

Source: https://usaco.guide/gold/modular_lang=cpp

A C++ code snippet demonstrating the use of a ModInt template, likely from Benq's competitive programming library. It includes standard headers, a MOD constant, and shows a basic structure for using modular arithmetic within main.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MOD = 1e9 + 7;


int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;

```

--------------------------------

### Using gp_hash_table resize() in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

Example demonstrating the usage of the `resize()` function for the custom `ht` hash table. It shows how to set the initial size and query the actual size versus the number of elements.

```cpp
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class K, class V>
using ht =
    gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>, 
                  linear_probe_fn<>, 
                  hash_standard_resize_policy<hash_exponential_size_policy<>, 
                                              hash_load_check_resize_trigger<>, true>>;

int main() {
	ht<int, null_type> g;
	g.resize(5);
	cout << g.get_actual_size() << "\n";  // 8
	cout << g.size() << "\n";             // 0
}

```

--------------------------------

### Bit Inversions: Initial Setup with Set and Multiset (C++)

Source: https://usaco.guide/gold/intro-sorted-sets_lang=cpp

This C++ code snippet initializes the necessary data structures for the Bit Inversions problem. It includes a set 'dif' to store indices where adjacent bits differ and a multiset 'ret' to store the lengths of contiguous identical bit segments. The 'sz' macro is a utility for getting the size of containers.

```cpp
#include <bits/stdc++.h>
using namespace std;


#define sz(x) (x).size()


string s;
int m;
set<int> dif;
multiset<int> ret;



```

--------------------------------

### DFS for Subtree Start and End Times

Source: https://usaco.guide/gold/tree-euler_lang=cpp

This code snippet demonstrates a Depth First Search (DFS) traversal used to calculate the start and end times for each node in a tree. These times define a range that encompasses all nodes within a node's subtree. The timer is incremented as nodes are visited and their subtrees are fully explored. This is fundamental for various tree-based algorithms.

```c++
#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


// This section appears to be a placeholder or related to a BIT implementation.
// Code for BIT (from PURS module) would typically involve operations like
// update and query on a Binary Indexed Tree.


// Placeholder for BIT structure/functions if available
// struct BIT {
//     vector<int> tree;
//     BIT(int size) { tree.assign(size + 1, 0); }
//     void update(int idx, int val) { ... }
//     int query(int idx) { ... }
// };
```

```c++
int n;  // The number of nodes in the graph
vector<int> graph[100000];
int timer = 0, tin[100000], euler_tour[200000];
int segtree[800000];  // Segment tree for RMQ


void dfs(int node = 0, int parent = -1) {
	tin[node] = timer;  // The time when we first visit a node
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {
            // Recursive call to DFS for children
            // dfs(i, node);
            // The actual code for recursive calls is omitted in the input.
            // euler_tour[timer++] = node; // This line would typically appear after visiting all children
        }
	}
    // The end time would typically be set here after visiting all children
    // tout[node] = timer++; 
}
```

--------------------------------

### C++ Standard Library Setup

Source: https://usaco.guide/gold/dp-trees

Includes common C++ headers and defines type aliases for competitive programming. Sets up basic utilities for data structures like vectors and pairs.

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
```

--------------------------------

### Haybale Distribution Problem Setup

Source: https://usaco.guide/gold/ternary-search_lang=cpp

Includes standard headers and initializes variables for a competitive programming problem. This snippet sets up input reading for the number of elements and a vector to store them, likely for a problem involving optimization.

```cpp
#include <bits/stdc++.h>


using ll = long long;


int main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	for (int &i : x) { std::cin >> i; }




```

--------------------------------

### GCDEX Problem Solution Setup - C++

Source: https://usaco.guide/gold/divisibility_lang=cpp

Sets up variables and memoization for solving the GCDEX problem, which involves sums of greatest common divisors. It uses a `phi` array for precomputed totient values and an `unordered_map` for memoizing results of a recursive function `solve(n)`. The `solve` function is intended to compute sums related to GCDs.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MAX_N = 1e6;
// phi[i] = how many pairs of numbers <=i are coprime
long long phi[MAX_N + 1];
// Store the values found to speed up the recursion process
unordered_map<int, long long> memo;


long long solve(long long n) {
```

--------------------------------

### Initializing gp_hash_table with minimum size in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

Illustrates how to initialize a `gp_hash_table` with a minimum actual size using specific template arguments. The last argument must be a power of 2.

```cpp
ht<int, null_type> g({}, {}, {}, {}, {1 << 16});

```

--------------------------------

### Modular Arithmetic with atcoder::modint (C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Demonstrates the use of the atcoder::modint library for handling modular arithmetic, specifically setting the modulus and performing operations within that modulus.

```cpp
#include <atcoder/modint>
#include <bits/stdc++.h>


using namespace std;
using mint = atcoder::modint;


int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);


```

--------------------------------

### Bit Inversions: Optimized Setup with Priority Queue and Counter (C++)

Source: https://usaco.guide/gold/intro-sorted-sets_lang=cpp

This C++ code snippet presents an optimized approach for the Bit Inversions problem. It replaces the multiset 'ret' with a priority queue and an auxiliary array 'cnt' to count element occurrences. This optimization aims to reduce the constant factor and improve runtime performance.

```cpp
#include <bits/stdc++.h>
using namespace std;


#define sz(x) (int)(x).size()


string s;
int m;
set<int> dif;
priority_queue<int> ret;
int cnt[200005];


```

--------------------------------

### C++ Basic Input for Meet in the Middle

Source: https://usaco.guide/gold/meet-in-the-middle

This C++ code snippet demonstrates basic input reading for a problem that likely uses the Meet in the Middle technique. It reads the number of elements (n) and a target value (x), then populates a vector 'a' with 'n' integer elements. This is a common starting point for problems where subset sums or similar calculations are involved.

```cpp
#include <bits/stdc++.h> 
using namespace std; 
using ll = long long; 


int main() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }



```

--------------------------------

### Bit Inversions Solution Setup - C++

Source: https://usaco.guide/gold/intro-sorted-sets

Initializes variables and data structures for the Bit Inversions problem. It uses a set `dif` to store indices where adjacent bits differ and a multiset `ret` to store the lengths of contiguous segments of identical bits.

```cpp
#include <bits/stdc++.h>
using namespace std;


#define sz(x) (x).size()


string s;
int m;
set<int> dif;
multiset<int> ret;


```

--------------------------------

### Meet in the Middle C++ Skeleton Code

Source: https://usaco.guide/gold/meet-in-the-middle_lang=cpp

This C++ code snippet provides a basic structure for implementing the Meet in the Middle algorithm. It includes input reading for the array size 'n' and target value 'x', and initializes a vector 'a' to store the array elements. It's a starting point for developing the core logic of the Meet in the Middle solution.

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }




```

--------------------------------

### Sparse Table Implementation (C++)

Source: https://usaco.guide/gold/tree-euler_lang=cpp

A C++ template class for implementing a Sparse Table. It supports O(N log N) preprocessing and O(1) range minimum queries. This implementation is suitable for static RMQ problems.

```cpp
#include <bits/stdc++.h>
using namespace std;


template <typename T> class SparseTable {
  private:
	int n, log2dist;
	vector<vector<T>> st;


  public:
	SparseTable(const vector<T> &v) {


```

--------------------------------

### C++ Basic Structure for Probability Calculations with Vectors

Source: https://usaco.guide/gold/combo_lang=cpp

A C++ code snippet that includes headers for iostream, iomanip, and vector, along with the standard namespace. It defines the main function and declares an integer variable 'n'. This setup is typical for problems involving calculations and data structures.

```cpp
#include <iomanip>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {
	int n;

```

--------------------------------

### Euler Tour Implementation for Tree Flattening (C++)

Source: https://usaco.guide/gold/tree-euler

This C++ code demonstrates the implementation of the Euler Tour technique for flattening a tree. It uses an adjacency list to represent the graph and auxiliary arrays (start and end times) to mark the entry and exit points of each node during the tour, enabling subtree queries.

```cpp
#include <iostream>
#include <vector>


using std::vector;


// The graph represented as an adjacency list (0-indexed)
vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};
vector<int> start(neighbors.size());
vector<int> end(neighbors.size());
int timer = 0;

```

--------------------------------

### Precomputing Factorials and Modular Inverses

Source: https://usaco.guide/gold/combo

Precomputes factorials and their modular inverses up to MAXN. This allows for O(1) calculation of binomial coefficients modulo a prime.

```cpp
#include <iostream>
using namespace std;
using ll = long long;


const int MAXN = 1e6;
const int MOD = 1e9 + 7;


ll fac[MAXN + 1];
ll inv[MAXN + 1];


void precompute() {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) {
		fac[i] = (fac[i - 1] * i) % MOD;
	}
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD); // Using Fermat's Little Theorem for modular inverse
	for (int i = MAXN - 1; i >= 0; i--) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}
```

--------------------------------

### Precomputing Factorials and Modular Inverses (C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Precomputes factorials and their modular inverses up to a maximum value (MAXN) modulo a prime (MOD). This allows for O(1) calculation of binomial coefficients.

```cpp
#include <iostream>
using namespace std;
using ll = long long;


const int MAXN = 1e6;
const int MOD = 1e9 + 7;


ll fac[MAXN + 1];
ll inv[MAXN + 1];




```

--------------------------------

### C++ Basic Structure for Probability Calculations

Source: https://usaco.guide/gold/combo_lang=cpp

Provides a basic C++ structure including necessary headers for mathematical operations and input/output, commonly used in probability problems. It initializes integer variables n and k.

```cpp
#include <cmath>
#include <iomanip>
#include <iostream>


using std::cout;
using std::endl;


int main() {
	int n;
	int k;

```

--------------------------------

### C++ Stack Operations

Source: https://usaco.guide/gold/stacks

Demonstrates the basic usage of a stack in C++. It shows how to push elements onto the stack, access the top element, remove elements, and check the stack's size. This is fundamental for understanding stack data structures.

```cpp
#include <iostream>
#include <stack>

using namespace std;

int main() {
	stack<int> s;
	s.push(1);				// [1]
	s.push(13);				// [1, 13]
	s.push(7);				// [1, 13, 7]
	cout << s.top() << endl;	// 7
	s.pop();				// [1, 13]
	cout << s.size() << endl;	// 2

	return 0;
}
```

--------------------------------

### Sparse Table Implementation (C++)

Source: https://usaco.guide/gold/tree-euler

A C++ implementation of a Sparse Table data structure. It supports O(N log N) preprocessing and O(1) queries for range minimum queries. The template allows it to work with different data types.

```cpp
#include <bits/stdc++.h>
using namespace std;


template <typename T> class SparseTable {
  private:
	int n, log2dist;
	vector<vector<T>> st;


  public:
	SparseTable(const vector<T> &v) {

```

--------------------------------

### Modular Exponentiation for Factorials

Source: https://usaco.guide/gold/combo

Calculates x raised to the power of n modulo m efficiently using binary exponentiation. This is a crucial subroutine for modular inverse calculations.

```cpp
const int MAXN = 1e6;


long long fac[MAXN + 1];
long long inv[MAXN + 1];


/** @return x^n modulo m in O(log p) time. */
long long exp(long long x, long long n, long long m) {
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) res = (res * x) % m;
		x = (x * x) % m;
		n /= 2;
	}
	return res;
}
```

--------------------------------

### C++ Random Base Generation for Hashing

Source: https://usaco.guide/gold/hashing

Demonstrates how to generate a random base (B) for polynomial hashing in C++ using `<random>` and `<chrono>`. This is crucial for minimizing collision probability in competitive programming scenarios, especially with open hacking.

```cpp
#include <random>
#include <chrono>

using namespace std;

// Define M and B if they are not defined globally or within the class
// const long long M = 1e9 + 9; // Example modulus

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);

```

--------------------------------

### C++ Combinations (n choose k)

Source: https://usaco.guide/gold/combo

Calculates 'n choose k' (binomial coefficient) using a naive iterative approach. This method is suitable when intermediate results do not overflow standard integer types, as indicated by the comment.

```cpp
#include <iostream>


/** @return n choose k, computed naively since the problem has no overflow */
long long comb(int n, int k) {
	if (k > n - k) { k = n - k; }
	long long ret = 1;
	for (int i = 0; i < k; i++) {
		// this is done instead of *= for divisibility issues
		ret = ret * (n - i) / (i + 1);
	}

```

--------------------------------

### C++ Boilerplate for Competitive Programming

Source: https://usaco.guide/gold/hashmaps_lang=cpp

A common C++ include and type definition boilerplate used in competitive programming. It includes standard libraries and defines type aliases for convenience.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

```

--------------------------------

### Precomputing Modular Inverses (C++)

Source: https://usaco.guide/gold/modular

An iterative C++ loop to precompute modular inverses for numbers from 2 up to MOD. This is efficient for scenarios where many modular divisions are needed. Requires a pre-defined 'inv' array and MOD constant.

```cpp
inv[1] = 1;  // assume we already defined this array
for (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }
```

--------------------------------

### Initialize Digit DP Array in C++

Source: https://usaco.guide/gold/digit-dp_lang=cpp

Initializes a 4D DP array used for Digit DP problems. The dimensions represent position, a counter for digit property, an 'under' flag, and a 'started' flag for leading zeros. This setup is crucial for the recursive DP solution.

```cpp
#include <bits/stdc++.h>


using namespace std;
using ll = long long;

ll dp[19][50][2][2];  // dp[pos][k][under][started]
string num;


/** Reset the dp array to its initial values. */
void reset() {

}
```

--------------------------------

### Haybale Distribution Problem Setup

Source: https://usaco.guide/gold/ternary-search

Sets up input reading for the Haybale Distribution problem. This typically involves reading the number of barns and the positions of the haybales. The problem often involves finding an optimal delivery point that minimizes transportation costs, leveraging the convexity/unimodality of the cost function. Dependencies: <iostream>, <vector>. Standard C++ libraries are assumed.

```cpp
#include <bits/stdc++.h>


using ll = long long;


int main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	for (int &i : x) { std::cin >> i; }



```

--------------------------------

### Push DP Implementation (C++)

Source: https://usaco.guide/gold/intro-dp

This C++ code snippet demonstrates the Push DP approach for calculating minimum costs to reach stones. It initializes heights and the DP array, with dp[N] representing the minimum cost to reach the Nth stone. The transitions are based on jumping one or two stones forward.

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	int N;
	cin >> N;
	vector<int> height(N);
	for (int i = 0; i < N; i++) { cin >> height[i]; }


	// dp[N] is the minimum cost to get to the Nth stone

```

--------------------------------

### C++ Sorting Vector of Edges with Functor

Source: https://usaco.guide/gold/custom-cpp-stl_lang=cpp

Sorts a vector of Edge structs using a functor 'cmp' that defines the comparison logic. This example shows how to use a custom functor with the std::sort algorithm.

```cpp
int main() {
	int M = 4;
	vector<Edge> v;
	for (int i = 0; i < M; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		v.push_back({a, b, w});
	}
	sort(begin(v), end(v), cmp());
	for (Edge e : v) cout << e.a << " " << e.b << " " << e.w << "\n";
}
```

--------------------------------

### BFS Initialization for Message Route

Source: https://usaco.guide/gold/unweighted-shortest-paths_lang=cpp

Initializes distance and parent arrays for a BFS traversal to find shortest paths in an unweighted graph. The distance array is initialized to INT_MAX, and the parent array to 0. This setup is typical for problems requiring path reconstruction.

```cpp
#include <bits/stdc++.h>
using namespace std;


using vi = vector<int>;
#define pb push_back


int main() {
	int N, M;
	cin >> N >> M;
	vi dist(N + 1, INT_MAX), parent(N + 1);

```

--------------------------------

### DFS for LCA and Euler Tour

Source: https://usaco.guide/gold/tree-euler

This C++ code snippet implements a Depth First Search (DFS) to prepare for Lowest Common Ancestor (LCA) queries using an Euler tour and a segment tree for Range Minimum Queries (RMQ). It initializes timer, tin (time of insertion), and the euler_tour array.

```cpp
int n;
vector<int> graph[100000];
int timer = 0, tin[100000], euler_tour[200000];
int segtree[800000];


void dfs(int node = 0, int parent = -1) {
	tin[node] = timer;
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {

```

--------------------------------

### C++ Implementation for Longest Non-Increasing Subsequence

Source: https://usaco.guide/gold/lis

This C++ code snippet appears to be an incomplete setup for a competitive programming problem, likely related to finding the longest non-increasing subsequence or similar dynamic programming tasks. It initializes variables and includes standard competitive programming optimizations.

```cpp
#include <bits/stdc++.h>
using namespace std;


int lis = 0;
pair<int, int> a[100000];
set<int> s;


int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);

```

--------------------------------

### Modular Inverse using Fermat's Little Theorem in C++

Source: https://usaco.guide/gold/modular

Calculates the modular multiplicative inverse of an integer 'a' modulo a prime 'p' using Fermat's Little Theorem (a^(p-2) mod p). This example demonstrates finding the inverse of 2 modulo 1e9 + 7.

```C++
const int MOD = 1e9 + 7;


int main() {
	ll x = exp(2, MOD - 2, MOD);
	cout << x << "\n";  // 500000004
	assert(2 * x % MOD == 1);
}
```

--------------------------------

### C++ Stack Operations: Push, Pop, Top, Size

Source: https://usaco.guide/gold/stacks_lang=cpp

Demonstrates the basic usage of the `std::stack` container in C++. It shows how to push elements onto the stack, retrieve the top element using `top()`, remove the top element using `pop()`, and check the number of elements with `size()`.

```cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);                 // Stack: [1]
    s.push(13);                // Stack: [1, 13]
    s.push(7);                 // Stack: [1, 13, 7]
    std::cout << s.top() << std::endl;   // Output: 7
    s.pop();                   // Stack: [1, 13]
    std::cout << s.size() << std::endl;  // Output: 2
    return 0;
}
```

--------------------------------

### C++ Sorted Map Operations using Iterators

Source: https://usaco.guide/gold/intro-sorted-sets_lang=cpp

Illustrates the usage of `lower_bound` and `upper_bound` with `std::map` in C++ for key-value pairs. The example shows insertion, accessing elements via iterators, and deletion. It highlights how `upper_bound` helps in checking if an element is beyond the map's range.

```cpp
map<int, int> m;
m[3] = 5;     // [(3, 5)]
m[11] = 4;    // [(3, 5); (11, 4)]
m[10] = 491;  // [(3, 5); (10, 491); (11, 4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << '\n';  // 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << '\n';  // 11 4
m.erase(11);  // [(3, 5); (10, 491)]
if (m.upper_bound(10) == m.end()) {
	cout << "end" << endl;  // Prints end
}

```

--------------------------------

### Shorter LCS DP with Macros in C++

Source: https://usaco.guide/gold/paths-grids

This C++ code provides a more concise implementation of the Longest Common Subsequence problem using macros for common operations like getting size, iterating, and checking maximum values. It uses a 1-based indexing for the DP table for simpler boundary condition handling.

```cpp
class Solution {
  public:
	int longestCommonSubsequence(str a, str b) {
		V<vi> dp(sz(a) + 1, vi(sz(b) + 1));
		F0R(i, sz(a) + 1) F0R(j, sz(b) + 1) {
			if (i < sz(a)) ckmax(dp[i + 1][j], dp[i][j]);
			if (j < sz(b)) ckmax(dp[i][j + 1], dp[i][j]);
			if (i < sz(a) && j < sz(b))
				ckmax(dp[i + 1][j + 1], dp[i][j] + (a[i] == b[j]));
		}
		return dp[sz(a)][sz(b)];
	}
};

```

--------------------------------

### Euler Tour Implementation for Tree Flattening (C++)

Source: https://usaco.guide/gold/tree-euler_lang=cpp

This C++ code demonstrates the core structure for performing an Euler Tour on a graph, which is essential for flattening a tree into an array. It utilizes an adjacency list representation and maintains timer variables to record the start and end times of each node's traversal, crucial for subtree range identification.

```C++
#include <iostream>
#include <vector>


using std::vector;


// The graph represented as an adjacency list (0-indexed)
vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};
vector<int> start(neighbors.size());
vector<int> end(neighbors.size());
int timer = 0;
```

--------------------------------

### Prim's Algorithm Structure (C++)

Source: https://usaco.guide/gold/mst_lang=cpp

This C++ code snippet outlines the basic structure for implementing Prim's algorithm, another method for finding a Minimum Spanning Tree. It includes necessary headers and standard namespace usage for graph algorithms involving priority queues and vectors.

```c++
#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::vector;


```

--------------------------------

### LIS Calculation with Coordinate Compression and RMQ Setup

Source: https://usaco.guide/gold/lis

This C++ code snippet initializes the process for calculating the Longest Increasing Subsequence (LIS) by applying coordinate compression to the input array 'a'. It sorts the elements to prepare for mapping them to compressed indices, which is a common preprocessing step when using data structures that rely on element values as indices.

```cpp
#include <bits/stdc++.h++.h>
using namespace std;


int find_lis(vector<int> a) {
	// apply coordinate compression to all elements of the array
	vector<int> sorted(a);
	sort(sorted.begin(), sorted.end());
	int at = 0;

```

--------------------------------

### C++ Sorted Map Operations (lower_bound, upper_bound)

Source: https://usaco.guide/gold/intro-sorted-sets

Illustrates the usage of `lower_bound` and `upper_bound` with `std::map` in C++ to find entries based on keys. `lower_bound` returns an iterator to the first element not less than the key, while `upper_bound` returns an iterator to the first element strictly greater than the key. The example includes map insertion, access, deletion, and checking for the end iterator.

```cpp
map<int, int> m;
m[3] = 5;     // [(3, 5)]
m[11] = 4;    // [(3, 5); (11, 4)]
m[10] = 491;  // [(3, 5); (10, 491); (11, 4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << '\n';  // 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << '\n';  // 11 4
m.erase(11);  // [(3, 5); (10, 491)]
if (m.upper_bound(10) == m.end()) {
	cout << "end" << endl;  // Prints end
}
```

--------------------------------

### Order Statistic Tree Implementation in C++

Source: https://usaco.guide/gold/PURS_lang=cpp

This C++ code snippet demonstrates the use of an order statistic tree, which is a policy-based data structure providing set-like operations along with order statistics. It requires the `ext/pb_ds` library and is primarily supported on GCC. The `Tree` template alias simplifies its usage for storing elements and finding elements by order.

```cpp
#include <bits/stdc++.h>
using namespace std;


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {


```

--------------------------------

### Longest Increasing Subsequence (Fast Binary Search) - C++

Source: https://usaco.guide/gold/lis

Finds the length of the longest increasing subsequence in O(N log N) time using binary search. It maintains a 'dp' vector where dp[j] stores the smallest ending element of an increasing subsequence of length j+1. For each element in the input array, it finds the position to insert it using lower_bound, potentially extending an existing subsequence or starting a new longer one.

```cpp
#include <algorithm>
#include <vector>
using namespace std;


int find_lis(const vector<int> &a) {
	vector<int> dp;
	for (int i : a) {
		int pos = lower_bound(dp.begin(), dp.end(), i) - dp.begin();
		if (pos == dp.size()) {
			// we can have a new, longer increasing subsequence!

```

--------------------------------

### Modular Exponentiation (C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Calculates x raised to the power of n modulo m efficiently using binary exponentiation. This is a common utility for modular arithmetic operations.

```cpp
const int MAXN = 1e6;


long long fac[MAXN + 1];
long long inv[MAXN + 1];


/** @return x^n modulo m in O(log p) time. */
long long exp(long long x, long long n, long long m) {
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	long long res = 1;
	while (n > 0) {


```

--------------------------------

### Frequency Table Hashing for Substring Matching (C++)

Source: https://usaco.guide/gold/hashing

This C++ snippet initializes frequency arrays for comparing substrings using a sliding window approach. It's intended for problems where the relative order of characters doesn't matter, focusing on character counts. Dependencies include standard C++ libraries.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


int freq_target[26], freq_curr[26];
string n, h;

```

--------------------------------

### Resizable gp_hash_table in C++

Source: https://usaco.guide/gold/hashmaps_lang=cpp

This snippet shows how to define a custom hash table type `ht` based on `gp_hash_table` that supports resizing. The `hash_standard_resize_policy` is modified to enable this functionality.

```cpp
template <class K, class V>
using ht =
    gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>, 
                  linear_probe_fn<>, 
                  hash_standard_resize_policy<hash_exponential_size_policy<>, 
                                              hash_load_check_resize_trigger<>, true>>;

```

--------------------------------

### Binary Indexed Tree: Dynamic Range Sum Queries Implementation (C++)

Source: https://usaco.guide/gold/PURS_lang=cpp

This C++ code demonstrates an implementation of a Binary Indexed Tree (BIT) for dynamic range sum queries. BITs offer a more concise implementation compared to Segment Trees, though potentially less intuitive initially. It's suitable for problems requiring point updates and range sum queries.

```cpp
#include <cassert>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


/**
 * Short for "binary indexed tree",

```

--------------------------------

### BIT Implementation (PURS Module)

Source: https://usaco.guide/gold/tree-euler

A Binary Indexed Tree (BIT) implementation, likely from a 'PURS module', is provided. BITs are efficient data structures for range queries and updates, commonly used in competitive programming for problems involving prefix sums or similar operations.

```cpp
#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;

```

--------------------------------

### Binomial Coefficient Calculation (Dynamic Programming - C++)

Source: https://usaco.guide/gold/combo_lang=cpp

Calculates the binomial coefficient (n choose k) modulo p using dynamic programming. This bottom-up approach optimizes the naive recursion by storing and reusing results for smaller subproblems, improving efficiency to O(n*k). It initializes a DP table and fills it based on Pascal's identity.

```cpp
/** @return nCk mod p using dynamic programming */
int binomial(int n, int k, int p) {
	// dp[i][j] stores iCj
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));


	// base cases described above
	for (int i = 0; i <= n; i++) {
		/*
		 * i choose 0 is always 1 since there is exactly one way
		 * to choose 0 elements from a set of i elements
		 */
```

--------------------------------

### C++ Standard Containers with Custom Comparators

Source: https://usaco.guide/gold/custom-cpp-stl_lang=cpp

Illustrates the usage of custom comparators with various C++ standard library containers, including std::set, std::map, and std::priority_queue. Demonstrates how to use 'greater<int>' for reverse ordering.

```cpp
set<int, greater<int>> a;
map<int, string, greater<int>> b;
priority_queue<int, vector<int>, greater<int>> c;

```

--------------------------------

### Topological Sort using DFS (C++)

Source: https://usaco.guide/gold/toposort

This C++ code snippet demonstrates a Depth-First Search (DFS) approach to perform a topological sort on a directed acyclic graph (DAG). It initializes global vectors for the graph and the sorted order. This method is suitable for DAGs and relies on visiting nodes and their descendants before adding the node to the sorted list.

```cpp
#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


vector<int> top_sort;
vector<vector<int>> graph;

```

--------------------------------

### Modular Arithmetic with atcoder library

Source: https://usaco.guide/gold/combo

Sets the modulus for calculations using the atcoder::modint library. This is useful for problems involving large numbers that need to be computed modulo a specific value.

```cpp
#include <atcoder/modint>
#include <bits/stdc++.h>


using namespace std;
using mint = atcoder::modint;


int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);

	// ... rest of the code using mint objects

	return 0;
}
```

--------------------------------

### Message Route BFS Initialization - C++

Source: https://usaco.guide/gold/unweighted-shortest-paths

Initializes distance and parent arrays for a BFS on an unweighted graph. The `dist` array stores the shortest distance from the source, initialized to infinity, and the `parent` array stores the predecessor of each node in the shortest path tree.

```cpp
#include <bits/stdc++.h++.h>
using namespace std;


using vi = vector<int>;
#define pb push_back


int main() {
	int N, M;
	cin >> N >> M;
	vi dist(N + 1, INT_MAX), parent(N + 1);

```