平铺方案【Ybtoj】

本文主要是介绍平铺方案【Ybtoj】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$Description$

您可以通过几种方式用$2\ast 1$或$2\ast 2$瓦片平铺$2\ast n$矩形？

这是一个$2\ast 17$矩形的样本拼贴:

$Input$

每行一个整数$n$。

$Output$

每行一个整数，表示方案数。

$Sample$ $Input$

2
8
12
100
200

$Sample$ $Output$

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

$Hint$

对于$100\%$的数据，$0\le n\le 250$。

$Train$ $of$ $Thought$

$F_k$表示有k列的方案数
那么可以考虑
$1.F_{k-1}$中最后加一个$2\ast 1$的方块
$2.F_{k-2}$中最后加两个$1\ast 2$的方块，或者一个$2\ast 2$的方块
那么$F_k=F_{k-1}+F_{k-2}\ast 2$
ps
高精压位

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define Mod 10000
#define ll long long
using namespace std;const int N = 500;ll A[300][N + 5];
ll n;void Add(int k)
{int g = 0;for(int i = 1; i <= N; ++i){A[k][i] = 2 * A[k - 2][i] + A[k - 1][i] + g;g = A[k][i] / Mod;A[k][i] %= Mod;}
}int main()
{A[1][1] = 1, A[2][1] = 3;for(int i = 3; i <= 250; ++i)Add(i);scanf("%lld", &n);while(n){int l = N + 1;while(--l && !A[n][l]);printf("%lld", A[n][l]);while(--l > 0){if(A[n][l] < 1000)printf("0");else if(A[n][l] < 100)printf("00");else if(A[n][l] < 10)printf("000");printf("%lld", A[n][l]);}printf("\n");n = 0;scanf("%lld", &n);}
}

这篇关于平铺方案【Ybtoj】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---