In-depth Analysis of Combinatorial Counting and Algorithm Optimization

Core Logic and Mathematical Principles

Combinatorial counting is at the heart of discrete mathematics. In the NOIP competition, all complex counting models can ultimately be reduced to three fundamental pillars: the general term of permutations and combinations, the ball-in-box model (using dividers), and derangements.

1. Basic Formulas for Permutations and Combinations

• Permutation: The number of ways to arrange $m$ elements selected from $n$ distinct elements in a row.

$$A_n^m = \frac{n!}{(n-m)!} = n \cdot (n-1) \dots (n-m+1)$$

• Combination: The number of ways to choose $m$ elements from $n$ distinct elements to form a set (order does not matter).

$$C_n^m = \frac{n!}{m!(n-m)!}$$

The combination satisfies the symmetry $C_n^m = C_n^{n-m}$ and the recursive property (Pascal's triangle formula) $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$.

2. Ball-in-box Model (Using Dividers)

This model is used to solve the counting problem of placing $n$ identical balls into $m$ distinct boxes.

• Case A: Each box must contain at least one ball (not empty)
  Arrange $n$ balls in a row, creating $n-1$ gaps between the balls. By placing $m-1$ dividers, the balls can be divided into $m$ parts, each corresponding to a box. The number of arrangements is:

$$C_{n-1}^{m-1}$$

• Case B: Boxes can be empty
  Introduce virtual chips. Assume we borrow $1$ ball for each box, resulting in a total of $n+m$ balls. The problem transforms to “placing $n+m$ balls into $m$ boxes with at least one ball”, and based on the conclusion from Case A, the number of arrangements is:

$$C_{n+m-1}^{m-1}$$

3. Derangement

A permutation $$ satisfies that for any $i$, $(i) eq i$. The number of derangements of $n$ elements is denoted as $D_n$. Its mathematical recursive formula is:

$$D_n = (n-1)(D_{n-1} + D_{n-2})$$

Proof of Recursive Logic:
Consider the $n^{th}$ element placed in position $k$ (there are $n-1$ choices, where $k eq n$).

• Case 1: If the element at position $k$ is placed in position $n$. In this case, $n$ and $k$ swap positions, and the remaining $n-2$ elements can independently derange, yielding $D_{n-2}$ arrangements.
• Case 2: If the element at position $k$ is not placed in position $n$. In this case, position $n$ can be viewed as a substitute for position $k$, and the remaining $n-1$ elements (including element $k$) will derange, yielding $D_{n-1}$ arrangements. Using the principles of addition and multiplication, we derive the formula. The boundary conditions are $D_1 = 0, D_2 = 1$.

State Design and Algorithm Derivation

When counting within a linear range of multiple queries, directly applying the general term formula is inefficient. We typically need to utilize state preprocessing to achieve $O(1)$ response speed.

• Combination State Design: For regular large prime modulus, preprocess factorials and their inverses (see Chapter 19.6), outputting through an $O(1)$ state equation after $O(N)$ preprocessing.
• Derangement State Design:
  Define a one-dimensional state array $D[i]$ representing the total derangements of size $i$.
  The state transition equation is quite straightforward:

$$D[i] = (i - 1) \cdot (D[i - 1] + D[i - 2]) \bmod \text{MOD}$$

This transition only relies on the previous two terms and can fill the state table in linear scan with $O(N)$ complexity.

C++ Standard Source Code

#include <iostream>
#include <vector>

const int MOD = 1000000007;
const int MAXN = 1000000;

long long fact[MAXN + 5];
long long invFact[MAXN + 5];
long long D[MAXN + 5];

// Fast exponentiation
long long quick_power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// Preprocess basic states of combinatorial mathematics and derangement states
void init_structures(int n) {
    // 1. Preprocess combinations
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = (fact[i - 1] * i) % MOD;

    invFact[n] = quick_power(fact[n], MOD - 2);
    for (int i = n; i >= 1; --i) invFact[i - 1] = (invFact[i] * i) % MOD;

    // 2. Preprocess derangement states
    D[1] = 0;
    D[2] = 1;
    for (int i = 3; i <= n; ++i) {
        // Strictly mod-safe addition to prevent overflow
        D[i] = (i - 1) * ((D[i - 1] + D[i - 2]) % MOD) % MOD;
    }
}

// O(1) Retrieve combination
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}

// O(1) Solve the ball-in-box model with empty boxes: n identical balls in m distinct boxes
long long balls_in_boxes(int n, int m) {
    return C(n + m - 1, m - 1);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    init_structures(MAXN);

    int t;
    if (std::cin >> t) {
        while (t--) {
            int n, m;
            std::cin >> n >> m;
            // Example: Output the combination of choosing m from n elements, and the derangement of n elements
            std::cout << C(n, m) << " " << D[n] << "\n";
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

1. Modulo Overflow Due to Missing Modulo in Derangement Multiplication
   When executing D[i] = (i - 1) * (D[i - 1] + D[i - 2]), the maximum value of D[i - 1] + D[i - 2] could approach $2 \times 10^9$. If we do not immediately take modulo before multiplying by the outer (i - 1) (if $i \approx 10^6$), the intermediate result could reach $2 \times 10^{15}$, causing an overflow in int and flipping the sign bit. It is essential to ensure that every addition and multiplication step is followed by % MOD.
2. Confusion Between Identical and Distinct Balls in the Ball-in-box Model
   The divider method only applies to identical balls and distinct boxes. If the problem states “$n$ distinct balls placed in $m$ distinct boxes”, some contestants may mistakenly apply $C_{n+m-1}^{m-1}$, leading to a complete logical collapse (placing distinct balls into distinct boxes essentially represents the second kind of Stirling number or channel counting model $m^n$). It is crucial to keenly capture the qualifiers "identical" and "distinct" during problem analysis.

Classic NOIP/Luogu Problems

1. Luogu P4071 [SDOI2016] Permutation Counting

• Problem Description: Determine how many permutations of length $n$ have exactly $m$ positions satisfying $(i) = i$ (i.e., exactly $m$ fixed points). The result should be taken modulo $10^9 + 7$.
• Core of the Problem: A composite model of combination selection and derangement.
• Key Solution Idea: First, select $m$ positions from $n$ as fixed points, yielding $C_n^m$ arrangements. After determining these $m$ positions, the remaining $n-m$ positions must all be deranged, yielding $D_{n-m}$ arrangements. By the multiplication principle, the final answer is $C_n^m \cdot D_{n-m} \bmod \text{MOD}$. Directly use the double state preprocessing table from the source code above to achieve $O(1)$ single query response.

2. Luogu P3182 [HAOI2016] Ball Arrangement

• Problem Description: There are $n$ positions, each initially containing one ball numbered from $1$ to $n$. Now, the balls must be rearranged such that no ball is in its original position, and the relative order of the balls cannot follow a specific cycle (i.e., specific derangement rules).
• Core of the Problem: Counting derangements of large numbers (requiring high precision or large modulus support).
• Key Solution Idea: Essentially, this is a pure derangement counting model. Establish the state transition equation $D_n = (n-1)(D_{n-1} + D_{n-2})$. Note that some problems may not require modulo, necessitating the use of __int128_t or high-precision addition/multiplication to derive the state table.