UVA 10497 Sweet Child Makes Trouble：錯排問題與大整數處理

問題背景

Tintin 偷拿了 n 件物品（n ≤ 800），將它們重新排列且每件物品都不在原位置。求排列方案數。輸入以 -1 結束。

數學模型：錯排公式

錯排數 D(n) 滿足遞推：

• D(1) = 0, D(2) = 1
• D(n) = (n-1) × [D(n-1) + D(n-2)] (n ≥ 3)

因 n ≤ 800，結果極大，需用高精度整數（Java BigInteger 或 C++ 大整數類）。

Java 參考實現

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int MAXN = 805;
        BigInteger[] f = new BigInteger[MAXN];
        f[1] = BigInteger.ZERO;
        f[2] = BigInteger.ONE;
        for (int i = 3; i < MAXN; i++)
            f[i] = f[i-2].add(f[i-1]).multiply(BigInteger.valueOf(i-1));

        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt();
            if (n == -1) break;
            System.out.println(f[n]);
        }
    }
}

關鍵點

• 預計算所有 D(n) 至 800，查詢 O(1)。
• BigInteger 自動處理任意大小整數。
• 遞推公式來源：考慮第 n 個位置放入 k (k≠n)，分 k 在原位 n 的位置與否兩種情況。