POJ 2506 Tiling(大数版递推)
发布时间:2020-12-14 02:21:01 所属栏目:大数据 来源:网络整理
导读:Tiling Time Limit: ?1000MS ? Memory Limit: ?65536K Total Submissions: ?8334 ? Accepted: ?4023 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 se
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 看这题前可以先做做这题HDOJ 2501; 由此题找出规律后即可用大数解决这一道题。 具体代码如下: ?? <span style="font-size:18px;">#include<cstdio> #include<cstring> int a[260][2010]; void count() { int i,j,k,s; memset(a,sizeof(a)); a[0][0]=1; a[1][0]=1; a[2][0]=3; for(i=3;i<260;++i) { k=0; for(j=0;j<=2000;++j) { s=a[i-1][j]+2*a[i-2][j]+k; a[i][j]=s%10; k=s/10; } } } int main() { count(); int n,i; while(scanf("%d",&n)!=EOF) { for(i=2000;i>=0;i--) if(a[n][i]) break; for(;i>=0;i--) printf("%d",a[n][i]); printf("n"); } return 0; }</span> (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |