POJ 2506 Tiling(大数)
发布时间:2020-12-14 02:23:30 所属栏目:大数据 来源:网络整理
导读:Tiling Time Limit: 1000MS ? Memory Limit: 65536K Total Submissions: 8300 ? Accepted: 4002 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
Tiling
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 规律题:F(n)=F(n-2)*2+F(n-1) ac代码:#include<stdio.h> #include<string.h> #define MAXN 10010 int num[255][MAXN+10]; void db() { memset(num,sizeof(num)); num[0][0]=0; num[1][0]=1; num[2][0]=3; int i,j; int c; for(i=3;i<=250;i++) { c=0; for(j=0;j<=MAXN;j++) { num[i][j]=(num[i-2][j]*2+num[i-1][j]+c)%10; c=(num[i-2][j]*2+num[i-1][j]+c)/10; } } } int main() { int i,j,n; db(); while(scanf("%d",&n)!=EOF) { if(n==0) { printf("1n"); continue; } for(i=MAXN;i>=0;i--) if(num[n][i]) break; for(j=i;j>=0;j--) printf("%d",num[n][j]); printf("n"); } return 0; }? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |