Problem Description
Bob's school has a big playground, boys and girls always play games here afterschool. To protect boys and girls from getting hurt when playing happily on theplayground, rich boy Bob decided to cover the playground using his carpets. Meanwhile, Bob is a mean boy, so he acquired that his carpets can not overlapone cell twice or more. He has infinite carpets with sizes of 1×2 and 2×1, and the sizeof the playground is 4×n. Can you tell Bob the total number of schemes where the carpets can cover theplayground completely without overlapping?
Input
There are no more than 5000 test cases. Each test case only contains one positive integer n in a line. 1≤n≤1018
Output
For each test cases, output the answer mod 1000000007 in a line.
Sample Input
1
2
Sample Output
1
5
【题意】
用 1 * 2 的小长方形完全覆盖 4 * n的矩形有多少方案。
【思路】
这道题显然可以想到用状态压缩DP去做，详细做法可以参考我之前的一片博客
传送门
但是可以观察到此题的数据范围很大，达到了1e18，我们自然而然的想到应该要找规律，可能要用到矩阵快速幂云云。。。
于是用状压DP的代码来打表，果然结果是有规律的。规律为：
dp[i]=dp[i-1]+5*dp[i-2]+dp[i-3]-dp[i-4] （i>=5）
这样我们就可以构造出矩阵的转移方程。
| 1 5 1 -1 | | F[n-1] | | F[n] |
| 1 0 0 0 | * | F[n-2] | = | F[n-1] |
| 0 1 0 0 | |F[n-3] | | F[n-2] |
| 0 0 1 0 | | F[n-4]| | F[n-3] |
然后就是一个矩阵快速幂的模板题了。
值得注意的是由于矩阵系数有负数，在做矩阵相乘时注意+mod再取膜
#include <cstdio> #include <vector> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define rush() int T,scanf("%d",&T),while(T--) typedef long long ll; const int maxn = 4; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; struct Matrix { ll temp[maxn][maxn]; } a; void init() { for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) { a.temp[i][j]=0; } a.temp[0][0]=a.temp[0][2]=1; a.temp[0][1]=5; a.temp[0][3]=-1; a.temp[1][0]=a.temp[2][1]=a.temp[3][2]=1; } Matrix mul(Matrix a,Matrix b) { Matrix ans; for (int i=0; i<maxn; i++) for (int j=0; j<maxn; j++) { ans.temp[i][j]=0; for (int k=0; k<maxn; k++) { ans.temp[i][j]+=(a.temp[i][k]*b.temp[k][j]+mod)%mod; //特别注意 ans.temp[i][j]%=mod; } } return ans; } void fun(Matrix ans,ll k) { for(int i=0; i<maxn; i++) for(int j=0; j<maxn; j++) a.temp[i][j]=(i==j); while(k) { if(k%2) a=mul(a,ans); ans=mul(ans,ans); k/=2; } } int main() { Matrix t; ll n; for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) { t.temp[i][j]=0; } t.temp[0][0]=36; t.temp[1][0]=11; t.temp[2][0]=5; t.temp[3][0]=1; while(~scanf("%I64d",&n)) { init(); if(n<=4) { printf("%I64d\n",t.temp[4-n][0]); continue; } fun(a,n-4); a=mul(a,t); ll ans=a.temp[0][0]%mod; printf("%I64d\n",ans); } return 0; }
