題目1 : 骨牌覆蓋問題·一

時間限制:10000ms 單點時限:1000ms 內(nèi)存限制:256MB

描述

骨牌，一種古老的玩具。今天我們要研究的是骨牌的覆蓋問題：
我們有一個2xN的長條形棋盤，然后用1x2的骨牌去覆蓋整個棋盤。對于這個棋盤，一共有多少種不同的覆蓋方法呢？
舉個例子，對于長度為1到3的棋盤，我們有下面幾種覆蓋方式：

?

輸入

第1行：1個整數(shù)N。表示棋盤長度。1≤N≤100,000,000

輸出

第1行：1個整數(shù)，表示覆蓋方案數(shù) MOD 19999997

樣例輸入

62247088

17748018

　　　

分析：
f(1)=1,f(0)=1,f(2)=2,f(3)=3;
---- f(n)= f（n-1）+ f(n-2)
---- 顯然這樣處理的時間復(fù)雜度為O(n)，n=10^8大于1000ms 故而可以這樣構(gòu)造函數(shù)：
由齊次方程可以得：
　　　　　　　　f(n) = f（n-1）+ f(n-2) （1）
　　　　　　f（n-1） = f(n-2) + f(n-3) (2)
-----> 可以得： 　　　　　　　　　　　　　　　　　　　　
　　　　　　f(n) = 1*f(n-1) + 1* f(n-2) (1)
　　　　　　　f(n-1) = 1*f(n-1) + 0* f(n-2) (2) 　　　　　　　　　　　　

　---> 進一步可以寫成

| f(n) | = |f(n-1)| *| 1 , 1| | f(n-1) | |f(n-2)| | 1 , 0|
化解為：

所以以此得出下面的代碼：

1 /*快速矩陣*/ 2 #include<iostream> 3 #define _int long long 4 const _int mod = 19999997; 5 using namespace std; 6 7 struct GMagin { 8 9 _int Margin [2][2]; 10 11 }Gbase,Gbasa; 12 13 /* 14 |f(n) | = |f(n-1)| * |1,1| 15 |f(n-1)| |f(n-2)| |1,0| 16 */ 17 18 void init(GMagin &Gbas_ , _int a=1, _int b=1, _int c=1, _int d=0) { 19 20 Gbas_.Margin[0][0] = a; 21 Gbas_.Margin[0][1] = b; 22 Gbas_.Margin[1][0] = c; 23 Gbas_.Margin[1][1] = d; 24 } 25 26 /*快速矩陣算法*/ 27 void Marginal(GMagin & a , GMagin &b ) { 28 GMagin res; 29 init(res,0,0,0,0); 30 for (int i = 0; i < 2; i++) { 31 for (int j = 0; j < 2; j++) { 32 for (int k = 0; k < 2; k++) 33 res.Margin[i][j] = (res.Margin[i][j]+a.Margin[i][k] * b.Margin[k][j])%mod; 34 } 35 } 36 init(a ,res.Margin[0][0], res.Margin[0][1], res.Margin[1][0], res.Margin[1][1]); 37 } 38 void matpow(int n) { 39 40 while (n > 0) { 41 if (n & 1) Marginal(Gbase,Gbasa); 42 n>>=1L; 43 if (n == 0) break; 44 Marginal(Gbasa, Gbasa); 45 } 46 } 47 48 int main(int argc ,char * argv []) { 49 50 int n; 51 while (cin>>n) { 52 init(Gbase); 53 init(Gbasa); 54 _int res; 55 if (n > 2) { 56 matpow(n - 2); 57 res = (Gbase.Margin[0][0] + Gbase.Margin[0][1]) % mod; 58 } 59 else { 60 61 if (n == 0 || n == 1)res = 1; 62 else if (n == 2) res = 2; 63 } 64 cout << res << endl; 65 } 66 return 0; 67 }

截圖：

?

轉(zhuǎn)載于:https://www.cnblogs.com/gongxijun/p/4418625.html

總結(jié)

以上是生活随笔為你收集整理的编程之美 --1 : 骨牌覆盖问题·一的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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