2384 事后诸葛亮

用L图形（大小为3，也就是去掉一个角的2x2的正方形）和1x2的矩形，覆盖2xn的矩形，问有多少种方案。

覆盖要求不重不漏，整体翻转和旋转均算作不同的方案。

用于覆盖的图形可以旋转，比如可以把L旋转为Г，把1x2的矩形旋转成为2x1的矩形等。

输出方案数模10007的结果。

对于100%的数据，1 <= n <= 10^100000

对于30%的数据，n <= 10^5

对于60%的数据，n <= 10^18

对于80%的数据，n <= 10^1000

输入

输入一行一个整数n。

输出

输出方案数模10007的结果。

输入样例

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; }

总结

以上是生活随笔为你收集整理的51nod2384 事后诸葛亮的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。