Nguyên lý Dirichlet và tính tuần hoàn

Nguyên lý Dirichlet (nguyên lý chuồng bồ câu, pigeonhole principle) phát biểu một điều hiển nhiên: nhét $n+1$ con bồ câu vào $n$ chuồng thì có chuồng chứa ít nhất $2$ con. Trong lập trình thi đấu, nguyên lý này là công cụ chứng minh sự tồn tại mạnh nhất: nó cho biết một đáp án chắc chắn có (nên chỉ cần tìm, không cần xét trường hợp "vô nghiệm"), cho biết mọi dãy truy hồi trên tập trạng thái hữu hạn đều tuần hoàn (nên $x_K$ với $K={10}^{18}$ tính được bằng $O(\text{số trạng thái})$ thay vì $O(K)$), và cho phép cắt vét cạn: khi dữ liệu đủ lớn thì đáp án đã chắc chắn, chỉ còn trường hợp dữ liệu nhỏ mới phải duyệt.

Ý tưởng / Trực giác

Dạng cơ bản và dạng tổng quát

• Dạng cơ bản. Đặt $n+1$ vật vào $n$ hộp thì có một hộp chứa ít nhất $2$ vật.
• Dạng tổng quát. Đặt $N$ vật vào $k$ hộp thì có một hộp chứa ít nhất $\lceil N/k\rceil$ vật.

Chứng minh dạng tổng quát bằng phản chứng: nếu mọi hộp chứa không quá $\lceil N/k\rceil -1$ vật thì tổng số vật không quá $k(\lceil N/k\rceil -1)<k·(N/k)=N$, mâu thuẫn.

Ví dụ: trong $N$ số nguyên bất kỳ, xếp mỗi số vào "hộp" là số dư của nó khi chia cho $k$. Có một số dư được ít nhất $\lceil N/k\rceil$ số dùng chung, và hiệu hai số bất kỳ trong nhóm đó đều chia hết cho $k$.

Cái khó khi áp dụng không nằm ở nguyên lý mà ở việc chọn đúng "bồ câu" và "chuồng". Ba mô hình dưới đây phủ gần hết các bài thi.

Mô hình 1: tổng tiền tố modulo $n$

Bài toán kinh điển. Cho $n$ số nguyên $a_1,\dots ,a_n$. Chứng minh luôn có một đoạn con liên tiếp khác rỗng có tổng chia hết cho $n$, và in ra một đoạn như vậy.

Đặt $P_0=0$ và $P_j=a_1+\cdots +a_j$. Tổng đoạn $a_{l+1}+\cdots +a_r$ bằng $P_r-P_l$, nên nó chia hết cho $n$ khi và chỉ khi $$P_l\equiv P_r\left(\mathrm{mod}n\right).$$

• Bồ câu: $n+1$ tổng tiền tố $P_0,P_1,\dots ,P_n$.
• Chuồng: $n$ số dư $0,1,\dots ,n-1$.

Vậy có hai chỉ số $l<r$ với $P_l\equiv P_r$, và đoạn $[l+1,r]$ là đáp án. Chú ý vai trò của $P_0=0$: không có nó thì chỉ có $n$ bồ câu cho $n$ chuồng và lập luận sụp đổ.

Lập luận này là kiến tạo: duyệt $j$ từ $0$ lên, ghi lại lần đầu gặp mỗi số dư; gặp lại một số dư đã có là xong. Vì chỉ có $n$ số dư nên vòng lặp dừng sau không quá $n$ bước. Đây là khuôn mẫu chung của các bài "luôn tồn tại đáp án, in một đáp án bất kỳ": chứng minh tồn tại bằng Dirichlet, rồi biến chứng minh thành thuật toán.

Kết quả tổng quát hơn: với modulo $m$ bất kỳ và ít nhất $m$ số, luôn có đoạn con liên tiếp (và do đó cũng là một dãy con) có tổng chia hết cho $m$.

Mô hình 2: dãy trên tập trạng thái hữu hạn thì tuần hoàn

Xét dãy $x_{i+1}=f(x_i)$, trong đó mỗi $x_i$ thuộc một tập $S$ gồm $|S|$ trạng thái. Trong $|S|+1$ giá trị $x_0,x_1,\dots ,x_{|S|}$ phải có hai giá trị trùng nhau. Xét lần đầu tiên dãy gặp lại một giá trị đã xuất hiện: đó là tại chỉ số $\mu +\lambda$, với $x_{\mu +\lambda }=x_{\mu }$, trong đó $\mu$ nhỏ nhất và $\lambda \ge 1$ cũng nhỏ nhất (các giá trị $x_0,\dots ,x_{\mu +\lambda -1}$ đôi một khác nhau). Vì $x_{i+1}$ chỉ phụ thuộc vào $x_i$, từ đó trở đi dãy lặp lại y hệt: $$x_{i+\lambda }=x_i\text{với mọi }i\ge \mu .$$

Hình dạng dãy giống chữ $\rho$ (rho): một "đuôi" dài $\mu$ rồi một "vòng" dài $\lambda$, và $\mu +\lambda \le |S|$ (vì $\mu +\lambda$ giá trị đầu đôi một khác nhau). Đó chính là một đường đi trong đồ thị hàm.

Điều kiện then chốt: trạng thái phải chứa đủ thông tin để xác định bước tiếp theo. Với dãy Fibonacci theo modulo $m$, $F_{i+1}=F_i+F_{i-1}$ phụ thuộc hai số trước, nên trạng thái là cặp $(F_{i}modm,F_{i+1}modm)$. Có $m^2$ cặp, vậy dãy $Fmodm$ tuần hoàn. Hơn nữa phép chuyển $(a,b)\mapsto (b,a+b)$ đảo ngược được ($(b,c)\mapsto (c-b,b)$), nên không có đuôi: dãy tuần hoàn thuần túy từ $F_0$. Chu kỳ này gọi là chu kỳ Pisano $\pi (m)$, và người ta chứng minh được $\pi (m)\le 6m$.

Tổng quát: mọi dãy truy hồi tuyến tính $x_i=c_1{x}_{i-1}+\cdots +c_d{x}_{i-d}\left(\mathrm{mod}m\right)$ đều tuần hoàn (có thể có đuôi nếu $c_d$ không khả nghịch modulo $m$), vì trạng thái $d$ số liên tiếp chỉ có $m^d$ khả năng.

Mô hình 3: "nếu $n$ đủ lớn thì luôn có đáp án"

Nhiều bài có ràng buộc "lệch": $n$ tới ${10}^6$ nhưng $m$ chỉ tới ${10}^3$. Đó thường là dấu hiệu của Dirichlet. Ví dụ: hỏi có dãy con (không cần liên tiếp) nào có tổng chia hết cho $m$ không.

• Nếu $n\ge m$: theo mô hình 1 luôn có đoạn liên tiếp như vậy, in YES ngay.
• Nếu $n<m\le 1000$: quy hoạch động cái túi theo số dư, chỉ tốn $O(n·m)$, không quá ${10}^6$ phép tính.

Quy hoạch động $O(n·m)$ trực tiếp với $n={10}^6$ là ${10}^9$ phép tính, quá chậm. Nhận xét Dirichlet cắt hẳn phần khó. Các dạng cắt tương tự hay gặp:

• Xâu chỉ gồm chữ cái thường ($a..z$) mà có độ dài $>26$ thì chắc chắn có ký tự lặp lại.
• Dãy dài $n\ge 2^m$ gồm các số trong $[0,2^m)$ (tức có $n+1>2^m$ tiền tố XOR, tính cả $P_0=0$) chắc chắn có đoạn con XOR bằng $0$.
• Có hơn $k$ số thì chắc chắn có hai số cùng số dư khi chia cho $k$, nên đáp án của bài "tìm cặp có hiệu chia hết cho $k$" luôn có, chỉ cần xét $k+1$ số đầu.

Ví dụ chạy tay

Đoạn con có tổng chia hết cho $n$

$a=[3,1,4,1,5]$, $n=5$. Tính tổng tiền tố và số dư, ghi lại lần đầu mỗi số dư xuất hiện:

 j        :   0    1    2    3    4    5
 a_j      :   -    3    1    4    1    5
 P_j      :   0    3    4    8    9   14
 P_j mod 5:   0    3    4    3    4    4
                   ^         ^
                   |_________|  cùng số dư 3 (j = 1 và j = 3)

 firstPos:  j=0: dư 0 -> ghi 0
            j=1: dư 3 -> ghi 1
            j=2: dư 4 -> ghi 2
            j=3: dư 3 -> ĐÃ CÓ tại 1  => dừng

Đoạn tìm được là $[l+1,r]=[2,3]$: $a_2+a_3=1+4=5$, chia hết cho $5$. Để ý đoạn này không bắt đầu từ $a_1$; không có tiền tố nào ($3,4,8,9,14$) chia hết cho $5$, nên phải có $P_0$ và phải so sánh mọi cặp số dư, không chỉ tìm $P_j\equiv 0$.

Chu kỳ Pisano modulo $3$

Trạng thái là cặp $(F_i,F_{i+1})mod3$. Dừng khi cặp $(0,1)$ xuất hiện lại:

 i        :  0  1  2  3  4  5  6  7  8  9
 F_i mod 3:  0  1  1  2  0  2  2  1  0  1
             \__/                    \__/
            (0,1)                   (0,1)  lặp lại tại i = 8

 => pi(3) = 8 ; ví dụ F_100 mod 3 = F_(100 mod 8) mod 3 = F_4 mod 3 = 0

Chú ý: giá trị $1$ xuất hiện ở $i=1$ rồi lại ở $i=2$ nhưng dãy chưa lặp, vì cặp $(1,1)\ne (0,1)$. Chỉ một số thì không đủ làm trạng thái. Kiểm tra: $F_{100}=354224848179261915075$ có tổng chữ số $93$, chia hết cho $3$.

Dãy có đuôi: $x_{i+1}=(x_i^2+1)mod10$, $x_0=3$

 i  :  0    1    2    3    4    5    6    7
 x_i:  3 -> 0 -> 1 -> 2 -> 5 -> 6 -> 7 -> 0   (x_7 = x_1)

          3 -> 0 -> 1 -> 2
               ^         |
               |         v
               7 <- 6 <- 5

 đuôi mu = 1 (chỉ có số 3), vòng lambda = 6 (0 1 2 5 6 7)

Để tính $x_{100}$: vì $100\ge \mu$ nên $x_{100}=x_{\mu +(100-\mu )mod\lambda }=x_{1+99mod6}=x_{1+3}=x_4=5$. Nếu quên trừ $\mu$ mà lấy $x_{100mod6}=x_4$ thì tình cờ đúng ở đây, nhưng với $K=102$ ta được $x_{102mod6}=x_0=3$, trong khi đáp án đúng là $x_{1+101mod6}=x_6=7$ (số $3$ không bao giờ xuất hiện lại).

Cài đặt

Tìm đoạn con có tổng chia hết cho $n$

Đọc $n$ và $n$ số (có thể âm), in một cặp $l,r$ với $a_l+\cdots +a_r$ chia hết cho $n$.

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    // firstPos[r] = smallest prefix index j with P_j mod n == r, or -1
    vector<int> firstPos(n, -1);
    firstPos[0] = 0;                        // P_0 = 0
    long long p = 0;
    for (int j = 1; j <= n; j++) {
        p = ((p + a[j]) % n + n) % n;       // keep remainder in [0, n)
        if (firstPos[p] != -1) {            // same remainder seen before
            int l = firstPos[p] + 1, r = j;  // a[l..r] has sum divisible by n
            printf("%d %d\n", l, r);
            return 0;
        }
        firstPos[p] = j;
    }
    // unreachable: n+1 prefixes, only n remainders
    return 0;
}

Bản Python (toán tử % của Python luôn trả về số không âm khi modulo dương):

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    first_pos = [-1] * n      # first prefix index with this remainder
    first_pos[0] = 0          # P_0 = 0
    p = 0
    for j in range(1, n + 1):
        p = (p + a[j - 1]) % n    # Python % is already non-negative
        if first_pos[p] != -1:
            print(first_pos[p] + 1, j)
            return
        first_pos[p] = j

main()

Cắt vét cạn: dãy con có tổng chia hết cho $m$

$n\le {10}^6$, $m\le {10}^3$. Nếu $n\ge m$ thì đáp án chắc chắn là YES; ngược lại quy hoạch động theo số dư.

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

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> a(n);
    for (auto &v : a) { scanf("%d", &v); v %= m; }

    // Pigeonhole: n >= m numbers always contain a block with sum % m == 0
    if (n >= m) { puts("YES"); return 0; }

    // Now n < m <= 1000: subset-sum DP over remainders, O(n*m)
    vector<char> can(m, 0), nxt;
    for (int v : a) {
        nxt = can;
        nxt[v] = 1;                          // subset {v} alone
        for (int r = 0; r < m; r++)
            if (can[r]) nxt[(r + v) % m] = 1;
        can.swap(nxt);
        if (can[0]) { puts("YES"); return 0; }
    }
    puts("NO");
}

Chu kỳ Pisano và $F_{n}modm$ với $n$ khổng lồ

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

// Pisano period of Fibonacci mod m (m >= 2). Always <= 6m.
long long pisano(long long m) {
    long long a = 0, b = 1;                 // (F_0, F_1)
    for (long long i = 1; ; i++) {
        long long c = (a + b) % m;
        a = b; b = c;                       // now (F_i, F_{i+1})
        if (a == 0 && b == 1) return i;     // back to the start pair
    }
}

// F_n mod m for huge n: reduce n by the period, then iterate
long long fibMod(unsigned long long n, long long m) {
    if (m == 1) return 0;
    long long p = pisano(m);
    n %= p;
    long long a = 0, b = 1;
    for (unsigned long long i = 0; i < n; i++) {
        long long c = (a + b) % m;
        a = b; b = c;
    }
    return a;
}

int main() {
    for (int m : {2, 3, 5, 7, 10, 1000}) printf("pi(%d) = %lld\n", m, pisano(m));
    printf("F_(10^18) mod 1000 = %lld\n", fibMod(1000000000000000000ULL, 1000));
}

Kết quả: $\pi (2)=3$, $\pi (3)=8$, $\pi (5)=20$, $\pi (7)=16$, $\pi (10)=60$, $\pi (1000)=1500$ và $F_{{10}^{18}}mod1000=875$. Chỉ cần so sánh với cặp đầu $(0,1)$ vì dãy Fibonacci modulo $m$ tuần hoàn thuần túy (không có đuôi).

Tìm đuôi $\mu$, vòng $\lambda$ rồi tua nhanh tới bước $K$

Khuôn tổng quát cho mọi dãy $x_{i+1}=f(x_i)$ trên $M$ trạng thái đánh số $0..M-1$: lưu thời điểm gặp đầu tiên của mỗi trạng thái.

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

int main() {
    // x_{i+1} = f(x_i) on states 0..M-1; find x_K for huge K
    long long M = 10, x0 = 3, K;
    auto f = [&](long long x) { return (x * x + 1) % M; };
    scanf("%lld", &K);

    vector<long long> seen(M, -1);          // seen[s] = first step index of state s
    vector<long long> seq;                  // seq[i] = x_i
    long long x = x0;
    for (long long i = 0; ; i++) {
        if (i == K) { printf("%lld\n", x); return 0; }  // reached K before any repeat
        if (seen[x] != -1) {                // repeat: x_i == x_mu
            long long mu = seen[x], lam = i - mu;
            printf("mu=%lld lambda=%lld -> x_K = %lld\n",
                   mu, lam, seq[mu + (K - mu) % lam]);
            return 0;
        }
        seen[x] = i;
        seq.push_back(x);
        x = f(x);
    }
}

Với $K=100$ chương trình in mu=1 lambda=6 -> x_K = 5, khớp ví dụ chạy tay. Khi trạng thái là một bộ nhiều thành phần (ô và hướng của robot, cặp số Fibonacci...), mã hóa bộ đó thành một số nguyên để dùng mảng seen, hoặc dùng map. Nếu không đủ bộ nhớ cho seen, dùng thuật toán rùa và thỏ của Floyd trong trang đồ thị hàm, chỉ tốn $O(1)$ bộ nhớ.

Độ phức tạp

So với cách ngây thơ: mô phỏng $K={10}^{18}$ bước là bất khả thi, còn tua nhanh chỉ tốn cỡ số trạng thái. Nhưng nếu số trạng thái lớn (ví dụ Fibonacci modulo $m={10}^9+7$ có $\pi (m)$ có thể lên tới cỡ $2·{10}^9$) thì chu kỳ không giúp được; khi đó dùng lũy thừa ma trận $O(\log K)$.

⚠️ Lỗi thường gặp

• Quên $P_0=0$. Chỉ xét $P_1,\dots ,P_n$ thì còn $n$ bồ câu cho $n$ chuồng, không còn đảm bảo có hai số trùng nhau, và bỏ sót các đoạn bắt đầu từ vị trí $1$. Luôn đặt firstPos[0] = 0 trước vòng lặp.
• Số dư âm trong C++. Với $a_i<0$, p % n có thể âm và truy cập firstPos[-3] gây lỗi bộ nhớ hoặc kết quả sai. Chuẩn hóa bằng ((p % n) + n) % n. Python không bị lỗi này.
• Chỉ tìm tiền tố chia hết. Đi tìm $P_j\equiv 0\left(\mathrm{mod}n\right)$ là chưa đủ: ở ví dụ chạy tay không tiền tố nào chia hết cho $5$, đáp án là đoạn $[2,3]$ nằm giữa dãy. Phải so khớp hai tiền tố cùng số dư bất kỳ.
• Trạng thái thiếu thông tin. Thấy $F_{i}modm$ lặp lại một giá trị rồi kết luận đã hết chu kỳ là sai (dãy modulo $3$: $0,1,1,\dots$ lặp số $1$ ngay nhưng chu kỳ là $8$). Trạng thái phải là cặp $(F_i,F_{i+1})$. Tương tự, robot di chuyển trên lưới cần trạng thái là (ô, hướng), không chỉ ô.
• Quên phần đuôi $\mu$. Dãy có phép chuyển đảo ngược được (như Fibonacci) thì tuần hoàn ngay từ đầu, nhưng dãy tổng quát có thể có đuôi, nên công thức đúng là $x_K=x_{\mu +(K-\mu )mod\lambda }$ khi $K\ge \mu$, và $x_K$ lấy trực tiếp khi $K<\mu$. Dùng $x_{Kmod\lambda }$ sẽ sai như ví dụ $K=102$ ở trên.
• Tràn số khi tính modulo. Với $m$ tới ${10}^6$, tích hai số dư lên tới ${10}^{12}$, vượt int. Dùng long long cho mọi phép nhân modulo và cho chỉ số $K$ tới ${10}^{18}$.
• Tin rằng chu kỳ luôn nhỏ. Số trạng thái của Fibonacci modulo $m$ là $m^2$, nhưng $\pi (m)\le 6m$ nhờ tính chất riêng của Fibonacci. Với truy hồi bậc $d$ khác, chu kỳ có thể cỡ $m^d$. Ước lượng số trạng thái trước khi quyết định tua nhanh hay dùng lũy thừa ma trận.
• Ngưỡng cắt sai một đơn vị. Kết luận "luôn có đáp án" phải được chứng minh đúng ngưỡng. Ở bài dãy con chia hết cho $m$, ngưỡng là $n\ge m$ (có $m+1$ tiền tố). Chọn ngưỡng $n>m$ vẫn đúng nhưng phí; chọn $n\ge m-1$ thì sai (ví dụ $n=1,m=2,a=[1]$ đáp án là NO).

Biến thể / Mở rộng

• Đếm thay vì tìm. Muốn đếm số đoạn con có tổng chia hết cho $n$, đếm số cặp tiền tố cùng số dư: nếu số dư $r$ xuất hiện $c_r$ lần trong $P_0,\dots ,P_n$ thì đáp án là ${\sum }_r\left(\genfrac{}{}{0ex}{}{c_r}{2}\right)$. Muốn tìm đoạn dài nhất, lưu lần xuất hiện đầu tiên của mỗi số dư và lấy $max(j-\text{firstPos}[P_{j}modn])$.
• XOR thay cho tổng. Đoạn con có XOR bằng $0$ tương ứng với hai tiền tố XOR bằng nhau. Các số trong $[0,2^m)$ có $2^m$ giá trị tiền tố khả dĩ, nên dãy dài $n\ge 2^m$ luôn có đoạn con XOR bằng $0$.
• Hai dãy tuần hoàn chạy song song. Nếu dãy $A$ có chu kỳ $p$ và dãy $B$ có chu kỳ $q$ thì cặp $(A_i,B_i)$ có chu kỳ $lcm(p,q)$. Mô phỏng một chu kỳ chung rồi nhân lên.
• Tính chất của chu kỳ Pisano. $\pi (m)$ tính được từ phân tích $m=\prod p_i^{e_i}$: $\pi (m)={lcm}_i\pi (p_i^{e_i})$ (theo định lý số dư Trung Hoa), và $\pi ({10}^k)=15·{10}^{k-1}$ với $k\ge 3$.
• Liên hệ đồ thị hàm. Mọi dãy $x_{i+1}=f(x_i)$ là đường đi trên đồ thị hàm. Khi cần trả lời nhiều truy vấn "đi $K$ bước từ đỉnh $v$" với nhiều $v$ khác nhau, dùng binary lifting ở trang đó thay vì tìm chu trình riêng cho từng truy vấn.
• Khi chu kỳ quá dài. Dãy truy hồi tuyến tính với modulo lớn thì dùng lũy thừa ma trận hoặc nhân ma trận trong quy hoạch động; nếu chỉ biết vài chục số hạng đầu của một dãy tuyến tính, Berlekamp-Massey tìm lại công thức truy hồi.

Bài tập luyện

Luyện kỹ thuật

• Dãy con chia hết cho 7 (div7) (Trung cấp) đoạn con liên tiếp dài nhất có tổng chia hết cho $7$: chỉ có $7$ số dư tiền tố, lưu lần xuất hiện đầu tiên của mỗi số dư như mô hình 1.
• Oẳn tù tì tuần hoàn (rpsgame) (Trung cấp) hai dãy tuần hoàn chu kỳ $m$ và $k$ chạy song song nên cả trận có chu kỳ $lcm(m,k)\le {10}^6$, trong khi $n$ tới $2·{10}^9$: đếm trên một chu kỳ rồi nhân lên.
• Dãy không lặp XOR (woolseq) (Trung cấp) dãy không có đoạn XOR bằng $0$ khi và chỉ khi các tiền tố XOR đôi một khác nhau; Dirichlet cho ngay đáp án $0$ khi $n\ge 2^m$, còn lại là một tích đếm.
• Du Thuyền Xa Xỉ (cruise) (Trung cấp) sau mỗi lượt $M$ lệnh, cảng mới chỉ phụ thuộc cảng cũ; chỉ có $N\le 1000$ cảng nên dãy cảng vào vòng lặp sau không quá $N$ lượt, tìm $\mu ,\lambda$ rồi tua nhanh $K\le {10}^9$ lượt.
• Tổng chia hết cho m (modsum) (Kỳ cựu) bài cắt vét cạn điển hình: $n\ge m$ thì luôn YES, ngược lại $n<m\le 1000$ nên quy hoạch động theo số dư chỉ tốn $O(m^2)$.

Đề VOI

• Bản vanxơ Fibonacci (voi12_fibval) (Nâng cao) VOI 2012: nốt nhạc ở vị trí $i$ chỉ phụ thuộc $F_{i}mod7$. Hãy tính chu kỳ Pisano modulo $7$ và nghĩ xem với đoạn đủ dài thì đáp án còn phụ thuộc vào vị trí bắt đầu hay không.
• Dãy Fibonacci (voi17_fibseq) (Nâng cao) VOI 2017: để ý ràng buộc $k\le n$ và nghĩ xem mô hình tổng tiền tố modulo $k$ nói gì về việc có luôn tồn tại đáp án hay không.
• Robot (voi18_robot) (Nâng cao) VOI 2018: chọn trạng thái đủ thông tin (ô và hướng) trong một vùng hữu hạn quanh mê cung; số trạng thái hữu hạn nên robot phải rơi vào chu trình, khi đó rút gọn thời gian $S$ theo độ dài chu trình.