For the summation of floor(n/i) from i=1 to n, we can compute it in O(sqrt(n)) time. The curve of n/x for 1 ≤ x ≤ n has non-increasing segments where floor(n/i) remains constant. For any segment [l, r], all values of floor(n/i) are equal, and r divides n.

Here's an implementation:

for (ll start = 1; start <= n; start++) {
  ll quotient = n / start;
  ll end = n / quotient;
  // Process segment [start, end]
  start = end;
}

Theorem: The number of distinct values of floor(n/x) for 1 ≤ x ≤ n is O(sqrt(n)).

**Proof:**For x in the range [1, sqrt(n)], there are at most sqrt(n) distinct values of floor(n/x). For x in the range [sqrt(n), n], floor(n/x) is less than sqrt(n), and by the pigeonhole principle, there are at most sqrt(n) distinct values. Since floor(n/x) is non-increasing, each distinct value forms a contiguous segment, resulting in O(sqrt(n)) segments.

O(1) Long Long Multiplication

Given the equation ab = floor(ab/m) * m + (ab mod m), we can compute (a * b) mod m without overflow using several approaches:

1. Using unsigned long long to capture overflow bits
2. Leveraging the precision of long double (64 bits) to represent long long results
3. Using floating-point arithmetic to represent large values like ab/m
4. Accounting for potential precision errors of ±1 in floating-point operations

Here's an implementation:

ll modularMultiply(ll num1, ll num2, ll modulus) {
  ll result = (ull)num1 * num2 - (ull)((long double)num1 * num2 / modulus) * modulus;
  if (result > modulus) result -= modulus;
  if (result < 0) result += modulus;
  return result;
}

Fast Exponentiation

For a number A of type T and an exponent n (decimal integer), where T can be integer, matrix, complex number, etc., we can compute A^n efficiently:

1. Express A^n as a product of terms where each term is A raised to a power of 2:

template<typename t="">
T fastPower(T base, ll exponent) {
  T result = base.identity(); // Identity element for the type
  while (exponent) {
    if (exponent & 1) 
      result = result * base;
    base = base * base;
    exponent >>= 1;
  }
  return result;
}
</typename>

Linear Time Sorting: Radix Sort

3.1 Bucket Sort

Given n numbers with a value range of m, we can sort them in O(n + m) time using bucket sort.

Principle: Use an array to count occurrences of each value, then iterate through the array to output the sorted values.

Implementation:

void bucketSort(int arr[], int n, int maxValue) {
  int* buckets = new int[maxValue + 1]();
  
  // Count occurrences
  for (int i = 0; i < n; i++) 
    buckets[arr[i]]++;
  
  // Output sorted values
  int index = 0;
  for (int i = 0; i <= maxValue; i++) {
    for (int j = 0; j < buckets[i]; j++) {
      arr[index++] = i;
    }
  }
  
  delete[] buckets;
}

Advantages: O(n + m) time complexity can be very fast in certain cases.

Disadvantages: Not suitable when m is large; sorting is not stable.

3.2 Counting Sort

Counting sort extends bucket sort and maintains two arrays: pos and rank.

pos[i] represents the position of the i-th element before sorting.

rank[i] represents the position of the i-th element after sorting.

Implementation:

void countingSort(int arr[], int pos[], int rank[], int n, int maxValue) {
  int* count = new int[maxValue + 1]();
  
  // Initialize count array
  for (int i = 0; i <= maxValue; i++) 
    count[i] = 0;
  
  // Count occurrences
  for (int i = 0; i < n; i++) 
    count[arr[i]]++;
  
  // Compute prefix sums
  for (int i = 1; i <= maxValue; i++) 
    count[i] += count[i - 1];
  
  // Build rank array
  for (int i = n - 1; i >= 0; i--) {
    rank[pos[i]] = count[arr[i]]--;
  }
  
  // Build pos array
  for (int i = 0; i < n; i++) 
    pos[rank[i]] = i;
  
  delete[] count;
}

Advantages: O(n + m) complexity can be very fast in certain cases. The pos and rank arrays are important preprocessing steps in some data structures.

Disadvantages: Not suitable when m is large.

3.3 Radix Sort

Radix sort applies counting sort multiple times based on different digits or keys. It sorts numbers by processing each digit position from least significant to most significant.

Implementation:

void radixSort(int arr[], int n, int maxValue) {
  int* pos = new int[n];
  int* rank = new int[n];
  
  // Initialize pos array
  for (int i = 0; i < n; i++) 
    pos[i] = i;
  
  // Process each digit
  for (int exp = 1; maxValue / exp > 0; exp *= 10) {
    // Extract current digit
    for (int i = 0; i < n; i++) {
      int digit = (arr[i] / exp) % 10;
      arr[i] = digit;
    }
    
    // Apply counting sort
    countingSort(arr, pos, rank, n, 9);
    
    // Update arr based on sorted positions
    int* temp = new int[n];
    for (int i = 0; i < n; i++) 
      temp[i] = arr[pos[i]];
    for (int i = 0; i < n; i++) 
      arr[i] = temp[i];
    delete[] temp;
  }
  
  delete[] pos;
  delete[] rank;
}

Time complexity: O(n * k), where k is the number of digits or keys. Typically k is a small constant.

Subset and Superset Enumeration

5.1 Enumerating Subsets

To enumerate all subsets of a set with n elements, we can use:

for (int i = 0; i < (1 << n); i++)

To enumerate only non-empty subsets of a set represented by bitmask m, we can use:

for (int subset = m; subset; subset = (subset - 1) & m)

For example, if m = 101 (binary), the subsets would be:

• subset = 101
• subset - 1 = 100, subset = 100 & 101 = 100
• subset - 1 = 011, subset = 011 & 101 = 001
• subset - 1 = 0, stop

Correctness: This approach enumerates subsets of m in decreasing order. At each step, it finds the largest subset smaller than the current one.

For problems requiring sum of contributions over all subsets, we might encounter:

int totalSum = 0;
for (int i = 1; i < (1 << n); i++) {
  int contribution = 0;
  for (int j = i; j; j = (j - 1) & i) {
    contribution += j;
  }
  f[i] *= contribution;
  totalSum += f[i];
}

The time complexity of this approach is O(3^n), as each bit has three possibilities: only in i, only in j, or in both.

5.2 Enumerating Supersets

To enumerate all supersets of a set represented by bitmask m:

for (int superset = m; ; superset = (superset + 1) | m) {
  // Process superset
  // if (superset == maximum) break;
}

Correctness: This approach finds the smallest superset larger than the current one while maintaining all bits of m. When we reach the maximum possible superset, we break after processing.

For problems requiring sum of contributions over all supersets:

for (int i = 1; i < (1 << m); i++) {
  for (int j = i; ; j = (j + 1) | m) {
    // Process j
    if (j == (1 << m) - 1) break;
  }
}

Time complexity: O(3^n), where n is the size of the universe.

Stress Testing

6.1 The Strongest Proof Method in Competitions: Contradicsion

In programming competitions, we often quickly find a naive solution to a problem. The process typically involves:

1. Through observation and known knowledge, find an optimized solution based on the naive approach
2. Through manual testing and pattern recognition, determine how to optimize the naive solution
3. Occasionally, through manual testing and pattern recognition, find a better solution not based on the naive approach

After proposing a solution, we typically need to verify it mathematically. In computer science, we can use AC (Accepted) verification or brute-force verification. In algorithmic competitions, we often use brute-force verification since we can delegate the verification process to a computer while solving other problems.

6.2 Stress Testing Concept

Stress testing is a form of brute-force verification. It involves:

• A standard implementation (std.cpp)
• A brute-force implementation (force.cpp)
• A data generator (data.cpp)
• A checker (check.cpp)

The brute-force implementation is the naive solution, and the standard implementation is the solution to be verified. The key is writing the data generator and checker.

6.3 Writing Data Generator

The data generator doesn't need to consider large number theorems; it can generate purely discrete distributions.

Implemantation:

#include <iostream>
#include <random>

int main() {
  std::random_device rd;
  std::mt19937 generator(rd());
  std::uniform_int_distribution<long long=""> range_n(lower_n, upper_n);
  std::uniform_int_distribution<long long=""> range_m(lower_m, upper_m);
  
  while (true) {
    int n = range_n(generator);
    int m = range_m(generator);
    std::cout << n << " " << m << std::endl;
  }
  
  return 0;
}
</long></long></random></iostream>

6.4 Writing Checker

Implementation:

#include <iostream>
#include <cstdlib>

int main() {
  // Generate test data
  system("data.exe > input.txt");
  
  // Run brute-force solution
  system("force.exe < input.txt > brute_output.txt");
  
  // Run standard solution
  system("std.exe < input.txt > standard_output.txt");
  
  // Compare outputs
  system("fc standard_output.txt brute_output.txt");
  
  return 0;
}
</cstdlib></iostream>

Segment Tree Table

A Segment Tree Table (ST Table) is a data structure that allows range minimum/maximum queries in O(1) time after O(n log n) preprocessing. It stores precomputed values for all intervals of length 2^k.

Implementation:

#include <vector>
#include <cmath>
#include <algorithm>

class STTable {
private:
  std::vector<:vector>> st;
  std::vector<int> logTable;
  int n;
  
public:
  STTable(const std::vector<int>& arr) : n(arr.size()) {
    // Precompute logarithms
    logTable.resize(n + 1);
    for (int i = 2; i <= n; i++)
      logTable[i] = logTable[i / 2] + 1;
    
    // Initialize ST table
    int k = logTable[n] + 1;
    st.resize(n, std::vector<int>(k));
    
    // Fill base cases
    for (int i = 0; i < n; i++)
      st[i][0] = arr[i];
    
    // Fill the table
    for (int j = 1; j < k; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        st[i][j] = std::min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
  
  int query(int l, int r) {
    int j = logTable[r - l + 1];
    return std::min(st[l][j], st[r - (1 << j) + 1][j]);
  }
};
</int></int></int></:vector></algorithm></cmath></vector>

Linked Hash Tables

Linked hash tables (or hash maps with chaining) are hash table implementations that use linked lists to handle collisions. They provide average O(1) time complexity for insert, delete, and search operations when properly sized.

Important: Pay attention to the load factor; this is not a mindless data structure.

It can typically solve problems with n ≤ 10^5 by reducing operations to O(1).

Implementation:

#include <vector>
#include <list>

template<typename key="" typename="" value="">
class HashMap {
private:
  static const int DEFAULT_CAPACITY = 10007;
  std::vector<:list value="">>> table;
  int capacity;
  int size;
  
  // Hash function
  int hash(const Key& key) {
    return std::hash<key>()(key) % capacity;
  }
  
public:
  HashMap(int cap = DEFAULT_CAPACITY) : capacity(cap), size(0) {
    table.resize(capacity);
  }
  
  void insert(const Key& key, const Value& value) {
    int index = hash(key);
    for (auto& pair : table[index]) {
      if (pair.first == key) {
        pair.second = value; // Update existing key
        return;
      }
    }
    table[index].emplace_back(key, value); // Insert new key
    size++;
  }
  
  Value* get(const Key& key) {
    int index = hash(key);
    for (auto& pair : table[index]) {
      if (pair.first == key) {
        return &pair.second;
      }
    }
    return nullptr;
  }
  
  bool remove(const Key& key) {
    int index = hash(key);
    for (auto it = table[index].begin(); it != table[index].end(); ++it) {
      if (it->first == key) {
        table[index].erase(it);
        size--;
        return true;
      }
    }
    return false;
  }
  
  int getSize() const {
    return size;
  }
};
</key></:list></typename></list></vector>

Fast Integer I/O

Only the simplest, most effective, and easiest-to-implement versions are discussed here.

Disable iostream and turn off iostream optimization. Fast I/O uses C's fast character output, which conflicts with C++'s standard ios.

Fast Integer Writing

Fast integer writing is rarely used in competitive programming for large output scenarios, but it has advantages:

1. Easy to understand and implement
2. Can output int128

Implementation:

template<typename t="">
void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
</typename>

Fast Integer Reading

Fast integer reading is a simple simulation process.

Implementation:

template<typename t="">
bool read(T& x) {
  char c = getchar();
  int sign;
  
  if (c == EOF) return false;
  
  if (c == '-') {
    sign = -1;
    x = 0;
  } else {
    sign = 1;
    x = c - '0';
  }
  
  while (c = getchar(), c >= '0' && c <= '9') {
    x = x * 10 + (c - '0');
  }
  
  x *= sign;
  return true;
}
</typename>