BZOJ 1002: [FJOI2007]轮状病毒 递推/基尔霍夫矩阵树定理

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

Description

Input

Output

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();
    }
 
}

BZOJ 1002: [FJOI2007]轮状病毒 递推/基尔霍夫矩阵树定理

原文：http://blog.csdn.net/ck_boss/article/details/45338537