Luogu P1045 — Mersenne Numbers

link: https://www.luogu.com.cn/problem/P1045

1. Problem Statement

A Mersenne number is an integer of the form $2^P - 1$ where $P$ is prime. Given $P$ ($1000 \lt P \lt 3,100,000$), the task is to compute:

  1. The number of decimal digits of $2^P - 1$;
  2. The last $500$ decimal digits of $2^P - 1$, printed in $10$ rows of $50$ digits each, zero-padded on the left if necessary.

It is not required to verify the primality of $2^P - 1$ or $P$.

2. Key Observations & Theoretical Background

2.1 Number of Digits

The number of digits of a positive integer $N$ in base $10$ is $\lfloor \log_{10} N \rfloor + 1$. For $N = 2^P - 1$, since subtracting $1$ changes the digit count only when $2^P$ is an exact power of $10$ (which never happens for $P \ge 1$), we have:

$$ \text{digits}(2^P - 1) = \lfloor P \cdot \log_{10} 2 \rfloor + 1 $$

This avoids the need to compute the full high-precision integer just for the digit count.

2.2 Truncation to the Last 500 Digits

High-precision arithmetic can be truncated: when only the last $k$ digits are needed, any carry beyond position $k$ can be discarded. This transforms the time complexity of each multiplication from $O(L^2)$ to $O(k^2)$, where $L$ is the full length (up to $\approx 9.3 \times 10^5$) and $k = 500$. The speedup is on the order of $\left(\frac{L}{k}\right)^2 \approx 3.5 \times 10^6$.

2.3 Binary Exponentiation (Fast Power)

Computing $2^P$ by repeated multiplication requires $P$ steps — infeasible for $P \le 3.1 \times 10^6$. Instead, binary exponentiation reduces the number of multiplications to $O(\log P)$ by exploiting:

$$ 2^P = \prod_{i: b_i = 1} 2^{2^i}, \quad \text{where } (b_k b_{k-1} \dots b_0)_2 = P $$

2.4 The Trailing Digit of $2^P$

The sequence of the units digit of $2^n$ (for $n \ge 1$) cycles through ${2, 4, 8, 6}$. Hence $2^P$ always ends in an even digit, and $2^P - 1$ requires no borrow — a simple a[1]-- suffices. Recognizing this removes an unnecessary borrow-loop that would be both error-prone and irrelevant.

3. Implementation

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1005;   // enough for 500-digit intermediate products

struct BigInt {
    int len;
    int a[MAXN];

    void init(int x) {
        int index = 1;
        memset(a, 0, sizeof(a));
        while (x) {
            a[index++] = x % 10;
            x /= 10;
        }
        len = max(index - 1, 1);
    }

    int& operator[](int i) { return a[i]; }

    void flatten(int L) {
        len = L;
        for (int i = 1; i <= len; i++) {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        len++;
        while (len > 1 && !a[len])
            len--;
        if (len > 500)
            len = 500;     // truncate: we only need last 500 digits
    }

    BigInt operator*(const BigInt& other) const {
        BigInt res;
        res.init(0);
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= other.len; j++)
                res.a[i + j - 1] += a[i] * other.a[j];
        res.flatten(len + other.len);
        return res;
    }
};

BigInt quick_pow(BigInt base, int exp) {
    BigInt res;
    res.init(1);
    while (exp) {
        if (exp & 1)
            res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

int main() {
    int p;
    cin >> p;

    BigInt base;
    base.init(2);
    BigInt res = quick_pow(base, p);
    res.a[1]--;   // 2^P always even, no borrow needed

    // output digit count
    cout << (int)(p * log10(2)) + 1 << endl;

    // output last 500 digits, 10 rows × 50 columns
    int cnt = 0;
    for (int i = 500; i >= 1; i--) {
        printf("%d", res[i]);
        cnt++;
        if (cnt == 50 && i > 1) {
            printf("\n");
            cnt = 0;
        }
    }
    return 0;
}

4. Debugging Chronicle

The solution progressed through 5 iterations. The errors, in order of discovery:

TLE → WA → RE → AC

Stage Symptom Root Cause Fix
1 TLE while(p--) linear exponentiation ($\Theta(P)$) Binary exponentiation ($\Theta(\log P)$)
2 WA×5 len = index-- off-by-one; parameter len shadows member; res.a[...] = overwrites instead of accumulating; log10(p) instead of log10(2); cnt == 10 instead of 50 Correct each individually (see §4.1)
3 RE MAXN = 550 while i+j-1 reaches 999 MAXN ≥ 1000
4 WA len = 505 typo, missing <algorithm>, while(!a[len]) no lower-bound guard 500, add header, len > 1 &&

Meta-cognitive takeaway: The most instructive failure was not a code bug but a mindset one — reflexively writing a full borrow-subtraction loop for 2^P - 1 without realizing $2^P$ always ends in an even digit, so borrowing is impossible. Pause before coding: does the operand have special structure that simplifies the operation?

4.1 Key Pitfalls in BigInt Implementation

# Location Wrong Right
1 init() len = index-- (post-decrement: use-then-subtract) len = max(index - 1, 1)
2 flatten() signature void flatten(int len) shadows this->len Rename parameter to int L
3 flatten() body while(!a[l]) (l is the immutable parameter) while(len > 1 && !a[len])
4 operator* = a[i] * other.a[j] (assignment) += a[i] * other.a[j] (accumulation)
5 flatten() end if (len > 500) len = 505 (typo) len = 500
6 Header missing <algorithm> for std::max #include <algorithm>

5. Summary of BigInt Design Principles

Principle Rationale
Use memset + loop-based init Avoids manual zero-reset bugs; consistent initialization
Return int& from operator[] Enables both read and write access through the same interface
Accumulate with += in multiplication loops Multiple $(i,j)$ pairs may map to the same result position
Guard while(!a[len]) with len > 1 Prevents underflow when the value is zero
Truncate len after flatten() Only the last $k$ digits influence subsequent operations
Explicitly assign this->len in flatten() Avoids parameter-name shadowing of member variables
Mark operator* as const Signals no mutation of operands; enables chaining

Luogu P1177 — Quick Sort

Link: https://www.luogu.com.cn/problem/P1177

1. Problem Statement (P1177)

Sort $N$ integers in ascending order and output them space-separated. For $100%$ of the testdata, $1 \leq N \leq 10^5$, $1 \le a_i \le 10^9$.

The challenge: writing a sorting algorithm from scratch that passes the anti-quicksort testcases — i.e., already-sorted input, reverse-sorted input, and arrays where all elements are equal.

2. Algorithm Overview

Quick sort is a divide-and-conquer algorithm. It picks a pivot, partitions the array into “less than pivot” and “greater than pivot” halves, then recurses on each half. When a subarray has length $\le 1$, it is trivially sorted.

flowchart TD
    A["quick_sort(l, r)"] --> B{"l >= r ?"}
    B -->|Yes| C["return (empty or single-element, stop)"]
    B -->|No| D["1. Pick pivot = a[(l+r)/2]"]
    D --> E["2. Partition: two pointers i, j move towards each other"]
    E --> E1["i scans left, stops at element >= pivot"]
    E --> E2["j scans right, stops at element <= pivot"]
    E1 --> F{"i < j ?"}
    E2 --> F
    F -->|Yes| G["swap(a[i], a[j])"]
    G --> E1
    F -->|No| H["Partition done, mid = j"]
    H --> I["3. Divide and conquer"]
    I --> I1["quick_sort(l, mid)"]
    I --> I2["quick_sort(mid+1, r)"]
    I1 --> J["Left half sorted"]
    I2 --> K["Right half sorted"]
    J --> L["Entire sequence sorted"]
    K --> L

2.1 Partition Step in Detail

The core of quick sort is the partition step (Hoare’s scheme). We use two pointers $i$ and $j$:

  • $i$ scans left to right, skipping elements already smaller than pivot.
  • $j$ scans right to left, skipping elements already larger than pivot.
  • When both stop, they point at elements that belong on the other side — swap them.
sequenceDiagram
    participant Array as "a[l..r]"
    participant i as "Pointer i"
    participant j as "Pointer j"

    Note over Array: pivot = 4
    Array->>i: i = l-1 (starts outside the interval)
    Array->>j: j = r+1 (starts outside the interval)
    loop while i < j
        i->>i: do i++ while a[i] < pivot
        Note over i: Stops at first element >= pivot
        j->>j: do j-- while a[j] > pivot
        Note over j: Stops at first element <= pivot
        alt i < j
            i->>j: swap(a[i], a[j])
            Note over i,j: Swap and continue next round
        else i >= j
            Note over i,j: Pointers crossed, partition done
        end
    end
    Note over Array: mid = j, left side <= pivot, right side >= pivot

3. Key Design Decisions & Rationale

3.1 Why i = l-1, j = r+1?

The loop uses do...while, which executes the body before checking the condition. If we initialized i = l, j = r, the very first do i++ would skip a[l] — missing the first element entirely.

By starting one step outside the interval, do i++ moves i to l on the first iteration, and do j-- moves j to r. This guarantees every element in $[l, r]$ is examined.

Initialization First do i++ effect Correct?
i = l i becomes l+1, skips a[l] No
i = l-1 i becomes l, starts at a[l] Yes

3.2 Why pivot = a[(l+r)/2] (middle element)?

Choosing the middle element as pivot avoids the worst-case $O(n^2)$ degradation on already-sorted arrays. If we always chose a[l] or a[r], a sorted input would produce maximally unbalanced partitions every time.

3.3 Why mid = j (not i)?

After the while(i < j) loop exits, $i$ and $j$ have crossed. The invariant at exit is:

$$a[l \dots j] \le \text{pivot} \le a[j+1 \dots r]$$

Thus $j$ (not $i$) is the correct split point. Using $i$ would cause overlapping intervals and potential infinite recursion.

4. Implementation

#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];

void quick_sort(int l, int r) {
    // Empty or single-element interval: recursion terminates.
    // When every subarray has length < 1, the whole sequence is sorted.
    if (l >= r) return;

    // 1. Pick a pivot — the array will be split into < pivot and > pivot halves.
    int pivot = a[(l + r) / 2];
    int i = l - 1, j = r + 1; // Works with do-while; pointers start outside the interval.

    // 2. Partition: two pointers move towards each other, swapping misfits.
    int mid; // mid records the final split point after the pointers cross.
    while (i < j) {
        do i++; while (a[i] < pivot); // Scan left for the first element >= pivot.
        do j--; while (a[j] > pivot); // Scan right for the first element <= pivot.
        if (i < j) swap(a[i], a[j]);  // Swap into the correct side.
    }
    mid = j; // j is the split point: left <= pivot, right >= pivot.

    // 3. Divide and conquer: recursively sort the two subarrays.
    quick_sort(l, mid);
    quick_sort(mid + 1, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    quick_sort(1, n);

    // Avoid trailing space: print the first element, then " " + each remaining.
    cout << a[1];
    for (int i = 2; i <= n; i++)
        cout << " " << a[i];
    return 0;
}

5. Debugging Chronicle

Stage Symptom Root Cause Fix
1 WA / infinite loop do j--; while (a[i] > pivot) — typo: used i instead of j in the condition; a[i] does not change as j decrements a[i] → a[j]
2 WA (format) No spaces in output, all numbers concatenated cout << a[i] << " ", and print the first element separately to avoid trailing space

Meta-cognitive takeaway: The a[i] vs a[j] typo is especially dangerous because it doesn’t always crash — it silently produces wrong results or infinite loops depending on the data. When using dual pointers, double-check that each pointer’s condition references the correct variable.

6. Complexity Analysis

Case Time Condition
Best $O(n \log n)$ Pivot always splits array into equal halves
Average $O(n \log n)$ Random pivot yields balanced partitions in expectation
Worst $O(n^2)$ Pivot always extreme (min or max), e.g. sorted array with naive pivot choice
  • Space: $O(\log n)$ for recursion stack (balanced case), $O(n)$ worst case.
  • Stability: Quick sort is not stable — equal elements may be swapped across the pivot.

6.1 Why the Worst Case Matters for P1177

Luogu P1177 includes adversarial testcases designed to break naive quick sort:

Testcase Naive pivot (a[l]) Middle pivot (a[(l+r)/2])
Already sorted $O(n^2)$ — fail $O(n \log n)$ — pass
Reverse sorted $O(n^2)$ — fail $O(n \log n)$ — pass
All elements equal $O(n^2)$ — fail $O(n^2)$ — fail (still degrades!)

For the “all equal” case, even middle-pivot degrades. The fix is three-way partitioning (§7.1).

7. Further Optimizations

graph LR
    A["Basic quicksort<br/>O(n²) worst"] --> B["Random pivot<br/>Avoid sorted-input degradation"]
    B --> C["Three-way partitioning<br/>Handle many duplicates"]
    C --> D["Insertion sort for small n<br/>Reduce constant factor"]
    D --> E["Tail-recursion elimination<br/>Control stack depth"]
    E --> F["Introspective sort<br/>Guaranteed O(n log n)"]

    style A fill
    style F fill

7.1 Three-Way Partitioning (Handling All-Equal Data)

When many elements equal the pivot, the standard two-way partition still degrades. Three-way partitioning splits into < pivot | = pivot | > pivot:

void quick_sort_3way(int l, int r) {
    if (l >= r) return;
    int pivot = a[l + rand() % (r - l + 1)];
    int lt = l, gt = r, i = l;
    while (i <= gt) {
        if (a[i] < pivot)      swap(a[i++], a[lt++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]); // Don't advance i — the swapped-in element hasn't been checked yet.
        else                   i++;
    }
    quick_sort_3way(l, lt - 1);
    quick_sort_3way(gt + 1, r);
    // All elements in [lt, gt] equal pivot — already in place, no recursion needed.
}

7.2 Small-Array Insertion Sort

When $r - l \le 15$, insertion sort has lower constant factor:

if (r - l <= 15) {
    for (int i = l + 1; i <= r; i++) {
        int key = a[i], j = i - 1;
        while (j >= l && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
    return;
}

7.3 Optimization Summary

Technique Solves Added Complexity
Random / median-of-three pivot Degradation on sorted input Low
Three-way partitioning Degradation on many duplicates Medium
Insertion sort for small $n$ High constant factor at leaves Low
Tail-recursion elimination Stack overflow on deep recursion Low
Introspective sort (switch to heapsort) Guarantees $O(n \log n)$ worst case High (≈ std::sort)

8. Key Pitfalls in Quick Sort Implementation

# Pitfall Wrong Right
1 Pointer initialization i = l, j = r (with do-while, skips a[l]) i = l-1, j = r+1
2 Wrong variable in condition do j--; while (a[i] > pivot) do j--; while (a[j] > pivot)
3 Wrong split point mid = i (i and j have already crossed) mid = j
4 Overlapping recursive intervals quick_sort(l, mid-1) + quick_sort(mid, r) quick_sort(l, mid) + quick_sort(mid+1, r)
5 Pivot at endpoint pivot = a[l] (degrades on sorted arrays) pivot = a[(l+r)/2] or random
6 Output format Trailing space / no spaces Print first element separately, then " " + a[i]

9. Connection to std::sort

The C++ standard library’s std::sort uses Introsort:

  1. Uses quicksort as the primary algorithm.
  2. Switches to heapsort when recursion depth exceeds $2\lfloor \log_2 n \rfloor$ (prevents $O(n^2)$).
  3. Switches to insertion sort when the subarray is smaller than a threshold (usually 16).

For competitive programming, using std::sort directly is the safest choice; hand-writing quicksort is mainly for understanding divide-and-conquer and for interview preparation.

Luogu P1923 — Quick Select ($k$-th Smallest Element)

This problem is a simliar version of the former one, only a little difference.

Link: https://www.luogu.com.cn/problem/P1923

1. Problem Statement (P1923)

Given $n$ integers $a_i$ and an integer $k$ ($0 \le k < n$), output the $k$-th smallest number. The smallest number is the 0-th smallest (0-indexed).

This is the selection problem: find the $k$-th order statistic. A full sort would solve it in $O(n \log n)$, but quick select achieves $O(n)$ average time by recursing into only one partition per level.

2. Algorithm Overview (Quick Select)

Quick select is obtained by modifying exactly one part of quick sort — the recursive calls. After partitioning, we check which side contains the $k$-th element and recurse only there.

flowchart TD
    A["quick_select(l, r)"] --> B{"l >= r ?"}
    B -->|Yes| C["return (single element is the answer)"]
    B -->|No| D["1. Pick pivot = a[(l+r)/2]"]
    D --> E["2. Partition: i, j two-pointer scan"]
    E --> E1["i scans left, stops at >= pivot"]
    E --> E2["j scans right, stops at <= pivot"]
    E1 --> F{"i < j ?"}
    E2 --> F
    F -->|Yes| G["swap(a[i], a[j])"]
    G --> E1
    F -->|No| H["Partition done"]
    H --> I{"k <= j ?"}
    I -->|Yes| I1["quick_select(l, j)"]
    I -->|No| I2["quick_select(j+1, r)"]
    I1 --> J["k-th element found in left half"]
    I2 --> K["k-th element found in right half"]

3. Key Insight: Why if-else on $j$?

The only difference between quick sort and quick select lies in the final two recursive calls:

Quick Sort Quick Select
quick_sort(l, mid); if (k <= j) quick_select(l, j);
quick_sort(mid + 1, r); else quick_select(j + 1, r);

Why can’t we unconditionally recurse into one side?

3.1 Post-Partition Invariant

After the while (i < j) loop exits, the following invariant holds:

$$a[l \dots j] \le \text{pivot} \le a[j+1 \dots r]$$

The pivot’s final resting position (call it pos) is not guaranteed to equal $j$. Depending on the data, it may land anywhere relative to $i$ and $j$:

Case Layout Description
A $[i,\ \text{pos},\ j]$ Pivot sits strictly between the crossed pointers
B $[\text{pos}(i),\ j]$ Pivot lands at or to the left of $i$
C $[i,\ \text{pos}(j)]$ Pivot lands at or to the right of $j$

Because the pivot’s exact position is ambiguous, we cannot blindly assume which side contains $k$. The if-else resolves this: if $k \le j$, the $k$-th element lies in $[l, j]$; otherwise in $[j+1, r]$.

3.2 Why Use $j$ (Not $i$) as the Split Decision Point?

By the loop invariant, $j$ is the conservative split: everything in $[l, j]$ is $\le$ pivot, everything in $[j+1, r]$ is $\ge$ pivot. The intervals $[l, j]$ and $[j+1, r]$ are guaranteed to be disjoint and cover the full range. Using $i$ would risk overlapping or missing elements, since $i \ge j+1$ after the pointers cross.

4. Implementation (Quick Select)

#include <iostream>
using namespace std;
const int MAXN = 5e6 + 5;
int a[MAXN];
int k; // global: the 0-indexed rank to locate

// Standard quick sort — for comparison
void quick_sort(int l, int r) {
    if (l >= r) return;
    int pivot = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    int mid;
    while (i < j) {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]);
    }
    mid = j;
    quick_sort(l, mid);
    quick_sort(mid + 1, r);
}

// Quick select: only the recursive calls differ
void quick_select(int l, int r) {
    if (l >= r) return;              // Single element — this is our answer
    int pivot = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]);
    }
    // Only recurse into the half that contains the k-th element
    if (k <= j)
        quick_select(l, j);
    else
        quick_select(j + 1, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n >> k;
    k++; // Problem uses 0-indexed k; our array is 1-indexed — adjust
    for (int i = 1; i <= n; i++) cin >> a[i];
    quick_select(1, n);
    cout << a[k] << endl;
    return 0;
}

Note: Luogu P1923 uses 0-indexed $k$ (the smallest is the 0-th). Since our array starts at index $1$, we pre-increment $k$ so a[k] points to the correct element after the partial sort.

5. Complexity Analysis

Case Time Condition
Best $O(n)$ Pivot is the $k$-th element itself — one partition suffices
Average $O(n)$ Each partition roughly halves the search space
Worst $O(n^2)$ Pivot always extreme (min or max), same degradation as naive quick sort

The expected recurrence:

$$T(n) = T!\left(\frac{n}{2}\right) + O(n) \implies T(n) = O(n)$$

  • Space: $O(\log n)$ for recursion stack in the balanced case, $O(n)$ in the worst case.

6. Pitfalls & Debugging Notes

# Pitfall Wrong Right
1 Blind recursion Always recurse into (j+1, r) Check if (k <= j) to decide the correct side
2 Wrong split variable Use i instead of j Always use j — the post-partition invariant guarantees correctness
3 0-index / 1-index mismatch Forget to adjust $k$ when array is 1-indexed k++ before calling quick_select
4 Overlapping intervals quick_select(l, i) + quick_select(i+1, r) Use j: quick_select(l, j) + quick_select(j+1, r)

7. Connection to std::nth_element

The C++ standard library provides std::nth_element, which implements quick select (typically as introselect — falling back to heapsort when recursion depth is excessive):

// Equivalent to the hand-written quick_select above:
nth_element(a + 1, a + k, a + n + 1);
cout << a[k] << endl;

Hand-writing quick select reinforces the two-pointer partition invariant — the same reasoning that underpins quick sort, three-way partitioning (Dutch national flag), and partial sorting. Once you understand that $j$ is the safe split point, both algorithms become two variations of the same idea.