比赛的时候刷了一点小聪明，发现这个数列是卢卡斯数，一个递推关系像斐波拉契数列的数列；

我不知道怎么证明，如果哪天无意中会证了再加上；

这题唯一的难点就是大数运算；

直接用JAVA

代码：

1 import java.io.PrintWriter; 2 import java.math.BigInteger; 3 import java.util.Scanner; 4   5 public class Main { 6     Scanner scan=new Scanner(System.in); 7     PrintWriter out=new PrintWriter(System.out); 8     BigInteger c[]=new BigInteger[10005]; 9     int n;10      11     void getc(){12         c[3]=BigInteger.valueOf(4);13         c[4]=BigInteger.valueOf(7);14         for(int i=5;i<=10001;i++)15             c[i]=c[i-2].add(c[i-1]);16     }17      18     void run(){19         getc();20         while(scan.hasNextInt()){21             n=scan.nextInt();22             out.println(c[n]);23             out.flush();24         }25     }26     public static void main(String[] args) {27         new Main().run();28     }29 }