BZOJ 1002: [FJOI2007]輪狀病毒 遞推/基爾霍夫矩陣樹定理

f[n]=3*f[n-1]-f[n-2]+2

Description

給定n(N<=100)，編程計算有多少個不同的n輪狀病毒。

Input

第一行有1個正整數n。

Output

將編程計算出的不同的n輪狀病毒數輸出

Sample Input

Sample Output

/**************************************************************
    Problem: 1002
    User: CKboss
    Language: Java
    Result: Accepted
    Time:888 ms
    Memory:14824 kb
****************************************************************/
 
import java.util.*;
import java.math.*;
 
 
public class Main {
     
    BigInteger[] ct = new BigInteger[120];
     
    void init(){
        ct[1]=BigInteger.valueOf(1);
        ct[2]=BigInteger.valueOf(5);
        ct[3]=BigInteger.valueOf(16);
         
        for(int i=4;i<=100;i++){
            ct[i]=ct[i-1].multiply(BigInteger.valueOf(3)).subtract(ct[i-2]).add(BigInteger.valueOf(2));
        }
    }
     
    Main(){
        Scanner in = new Scanner(System.in);
        init();
        int n=in.nextInt();
        System.out.println(ct[n]);
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new Main();
    }
 
}