1002: [FJOI2007]轮状病毒

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 5691  Solved: 3090

[][][]

Description

　　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子

和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示

　　N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不

同的3轮状病毒，如下图所示

　　现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

Input

　　第一行有1个正整数n

Output

　　计算出的不同的n轮状病毒数输出

Sample Input

3

Sample Output

16

HINT

import java.math.BigInteger;import java.util.Scanner;/* 打表程序（矩阵树定理）LL g[205][205];LL d[205][205];int sign;LL n;void getc(){//求C矩阵    memset(d,0,sizeof d);    for(int i=0;i
     
      */public class Main {    public static void main(String[] args) {    // write your code here        int n;        Scanner in=new Scanner(System.in);        n=in.nextInt();        BigInteger a=new BigInteger("1");        BigInteger b=new BigInteger("5");        BigInteger pos;        if(n<3){            switch (n){                case 1:                    System.out.println("1");                case 2:                    System.out.println("5");            }            return ;        }        for(int i=3;i<=n;i++){            pos=b.multiply(new BigInteger("3"));            pos=pos.subtract(a);            pos=pos.add(new BigInteger("2"));            a=b;            b=pos;        }        System.out.println(b);    }}