BZOJ 1002 輪狀病毒：遞推公式 f[n] = 3f[n-1] - f[n-2] + 2

題目描述

給定 n (≤ 100)，計算 n 輪狀病毒數量。樣例：n=3 → 16。答案極大，需高精度。

遞推公式推導

輪狀病毒結構對應輪圖 W_n 的生成樹數。由 Kirchhoff 矩陣樹定理或組合推導得遞推：
f[1]=1, f[2]=5, f[3]=16
f[n] = 3*f[n-1] - f[n-2] + 2 (n ≥ 4)

Java 高精度實現

import java.util.*;
import java.math.*;

public class Main {
    BigInteger[] f = new BigInteger[120];
    void init() {
        f[1] = BigInteger.ONE;
        f[2] = BigInteger.valueOf(5);
        f[3] = BigInteger.valueOf(16);
        for (int i=4; i<=100; ++i) {
            f[i] = f[i-1].multiply(BigInteger.valueOf(3))
                    .subtract(f[i-2])
                    .add(BigInteger.valueOf(2));
        }
    }
    public static void main(String[] args) {
        new Main().run();
    }
    void run() {
        init();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(f[n]);
    }
}

C++ 高精度（手寫大整數或用 boost::multiprecision::cpp_int）

#include 
using boost::multiprecision::cpp_int;

cpp_int f[105];
int main() {
    f[1]=1; f[2]=5; f[3]=16;
    for(int i=4;i<=100;++i) f[i]=3*f[i-1]-f[i-2]+2;
    int n; while(cin>>n) cout<