HDU 4927 Series 1 - 楊輝三角組合數計算大數差分序列

問題描述

給定 n 個數 a_1..a_n，反覆做相鄰差分（b_i = a_{i+1} - a_i）直到剩 1 個數，求該數。多組測試，n ≤ 3000，數值極大需大整數。

規律發現：楊輝三角係數

經觀察，最終結果 = Σ_{i=1}^n (-1)^{n-i} * C(n-1, i-1) * a_i。即第 n-1 行楊輝三角係數，符號交替，最後一項為正。證明：差分運算子 Δ，Δ^{n-1} a_1 = Σ (-1)^{n-1-k} C(n-1,k) a_{k+1}。

大數計算

使用 Java BigInteger 或 C++ 高精度類。楊輝三角係數可迭代計算：C(n-1,0)=1，C(n-1,k) = C(n-1,k-1) * (n-k) / k。從最後一項開始累加（最後一項係數為正），符號交替。

複雜度

每組 O(n) 計算係數並累加，大整數乘除 O(log n) 位操作，總時間極快。

參考代碼 (Java)

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int cas = 0; cas < T; ++cas) {
            int n = in.nextInt();
            BigInteger[] a = new BigInteger[n+1];
            for (int i = 1; i <= n; ++i) a[i] = in.nextBigInteger();
            BigInteger coeff = BigInteger.ONE; // C(n-1, 0)
            BigInteger sum = BigInteger.ZERO;
            // 從最後一項倒序累加，符號交替，最後一項為正
            for (int i = n; i >= 1; --i) {
                BigInteger term = a[i].multiply(coeff);
                if ((n - i) % 2 == 0) sum = sum.add(term);
                else sum = sum.subtract(term);
                // 更新係數到下一個 (i-1)
                if (i > 1) {
                    coeff = coeff.multiply(BigInteger.valueOf(i-1))
                               .divide(BigInteger.valueOf(n-i+1));
                }
            }
            System.out.println(sum);
        }
    }
}