2384 事后諸葛亮

用L圖形（大小為3，也就是去掉一個(gè)角的2x2的正方形）和1x2的矩形，覆蓋2xn的矩形，問有多少種方案。

覆蓋要求不重不漏，整體翻轉(zhuǎn)和旋轉(zhuǎn)均算作不同的方案。

用于覆蓋的圖形可以旋轉(zhuǎn)，比如可以把L旋轉(zhuǎn)為Г，把1x2的矩形旋轉(zhuǎn)成為2x1的矩形等。

輸出方案數(shù)模10007的結(jié)果。

對(duì)于100%的數(shù)據(jù)，1 <= n <= 10^100000

對(duì)于30%的數(shù)據(jù)，n <= 10^5

對(duì)于60%的數(shù)據(jù)，n <= 10^18

對(duì)于80%的數(shù)據(jù)，n <= 10^1000

輸入

輸入一行一個(gè)整數(shù)n。

輸出

輸出方案數(shù)模10007的結(jié)果。

輸入樣例

5

輸出樣例

24

本題只放代碼：

#include<bits/stdc++.h> #define endline putchar('\n') using namespace std; template <typename T> void read(T &x) {x=0;char c=getchar();int sgn=1;while(c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();x*=sgn; } template <typename T> void out(T x) {if(x<0){putchar('-');x=-x;}if(x>=10)out(x/10);putchar(x%10+'0'); } long long a[100005]; const int p=10007; int main() {a[0]=a[1]=1;a[2]=2;for(int i=3;i<=100000;i++)a[i]=(2*a[i-1]+a[i-3])%p;string str;cin>>str;int n=str.size();long long x=0;for(int i=0;i<n;i++)x=(x*10+str[i]-'0')%10006;cout<<a[x]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的51nod2384 事后诸葛亮的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。