杭电OJ（HDOJ）1865题：1sting（大数操作——Fibonacci数列）

题意：

给出一个长度不超过200的序列，该序列只由数字1组成，只可进行两种操作：1、两个1合并成一个2，2、移动1和2的位置。比如：长度为4的序列1111，经过以上两种操作后可以得到以下5种不同的新序列1111,121,112,211,22。先一个整数n(表示测试实例次数),每次输入一个长度不超200的序列，求不同排列的个数。

示例输入：

3
1
11
22222

示例输出：

1
2
8

解决方案：

使用int型会越界，傻呼呼的用double去保存，发现WA后，但因为偷懒，也算是初学，就用了java的大数类，很简单，写之前顺便查了下java documentation。输入长度为200时其结果应为453973694165307953197296969697410619233826。老长了。但数组一定要开到201，开到200就WA了。同样HDOJ1715题也是这个问题。

附：Java 1.7 APIs

import java.math.*;
import java.util.Scanner;
public class Main {
    public static void main(String args[])    {
        Scanner input = new Scanner(System.in);
        BigInteger arr[]= new BigInteger[201];//大数数组声明
        int i;
        String str;
        arr[0]=new BigInteger("1");//赋初值
        arr[1]=new BigInteger("2");        
        for(i=2;i<201;i++)//计算fibnacci
            arr[i]=arr[i-1].add(arr[i-2]);        
        i=input.nextInt();
        while(i>0)
        {
            str=input.next();            
            System.out.println(arr[str.length()-1]);
            i--;
        }
        
    }

}