POJ 2506

 
 

  
  Tiling
 
 
 
 

  
  



Time Limit:?1000MS
 
     
?
 
     

Memory Limit:?65536K
 
    


Total Submissions:?8097
 
     
?
 
     

Accepted:?3921
 
    

Description
 
 

  
  In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles??
Here is a sample tiling of a 2x17 rectangle.?

  
   
   



 
 
Input
 
 

  
  Input is a sequence of lines,each line containing an integer number 0 <= n <= 250.
 
 
Output
 
 

  
  For each line of input,output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.?

 
 
Sample Input
2
8
12
100
200
Sample Output
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char s[260][250];
int main()
{
    int n,m;
    memset(s'0'sizeof));
    s[0][0]='1';s[1[2]='3'[3]='5';
    for(i=4;i<=250++)
    {
        for(j=0;j<200++)
        {
            k=(2*(s[i-2][j]-'0')+s[i-1+s[i);//之所以还要加上s[i][j]，这是前一位向后一位的进位。
            s]=k%10+'0';
            s][j+1/10;
        }
    }

    while(cin>>n)
    {
        int x=200;
        for>=0--)
        {
            if[n][i]!='0')
            {
                x=i;
                break;
            }
        }
        for=x--)
        {
            printf("%c"]);
        }
        cout<<endl;
    }
    return 0;
}

方法二：

   JAVA 过大数feel excellent!

import java.util.*;
import java.io.*;
import java.math.*;
public class Main
{
static BigInteger[] ans;
public static void main(String srga[])
{
Scanner cin=new Scanner(System.in);
ans=new BigInteger[260];
ans[0]=BigInteger.valueOf(1);
ans[1]=BigInteger.valueOf(1);
ans[2]=BigInteger.valueOf(3);
int i;
for(i=3;i<=255;i++)
{
ans[i]=ans[i-1].add( ans[i-2].multiply(BigInteger.valueOf(2)) ? );
}
while(cin.hasNext())
{
int a;
a=cin.nextInt();
System.out.println(ans[a]);
}
cin.close();
}
}