描述

骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：

提示：骨牌覆盖

提示：如何快速计算结果

输入

第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行：1个整数，表示覆盖方案数 MOD 19999997

 #include <iostream>

 #include <vector>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const ll MOD = ;

 struct matrix {

     ll a, b, c, d;

     matrix() : a(), b(), c(), d() {}

     matrix operator * (const matrix &m) const {

         matrix tmp;

         tmp.a = (a * m.a + b * m.c) % MOD;

         tmp.b = (a * m.b + b * m.d) % MOD;

         tmp.c = (c * m.a + d * m.c) % MOD;

         tmp.d = (c * m.b + d * m.d) % MOD;

         return tmp;

     }

 };

 matrix pow(const matrix &a, int n) {

     matrix tmp;

     if (n ==  || n == ) return tmp;

     tmp = pow(a, n / );

     if (n & ) {

         tmp = tmp * tmp * a;

     } else {

         tmp = tmp * tmp;

     }

     return tmp;

 }

 int main() {

     ll n;

     matrix a, b;

     while (cin >> n) {

         b = pow(a, n);

         cout << b.d << endl;

     }

     return ;

 }