编程之美 --1 : 骨牌覆盖问题·一

题目1 : 骨牌覆盖问题·一

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

输入

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

输出

第1行:1个整数,表示覆盖方案数 MOD 19999997

样例输入

62247088

17748018

分析:
     f(1)=1,f(0)=1,f(2)=2,f(3)=3;
----    f(n)=  f(n-1)+ f(n-2)
----  显然这样处理的时间复杂度为O(n),n=10^8大于1000ms  故而可以这样构造函数:
     由齐次方程可以得:
        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 }

截图:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】1447: [蓝桥杯][历届试题]格子刷油漆

好消息,网站又新增新功能,赶紧去看看吧! 题目描述 X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如下图所示),现需要把这些格子刷上保护漆。 ...

30290
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

27560
来自专栏量子位

谷歌云TPU上可以用Julia啦!0.23秒跑100张图片,Jeff Dean点赞推荐

不久前,Julia Computing官方放出了一篇论文,展示将Julia代码和机器学习模型编译到谷歌云TPU的方法,可以实现在0.23秒内完成100张图片VG...

13430
来自专栏申龙斌的程序人生

零基础学编程042:画函数图像

孩子马上就要参加高考了,我以前还能帮着辅导一下数学功课,现在就不行了,一来她很忙,晚上很晚才到家,二来高中的数学题太变态,琢磨一个小时可能也解不出一道。 前几天...

39790
来自专栏ascii0x03的安全笔记

使用sklearn构建含有标量属性的决策树

网络上使用sklearn生成决策树的资料很多,这里主要说明遇见标量数据的处理。 经查验参考资料,sklearn并非使用了课上以及书上讲的ID3算法,而是选择了C...

42560
来自专栏数据结构与算法

扩展中国剩余定理详解

前言 阅读本文前,推荐先学一下中国剩余定理。其实不学也无所谓,毕竟两者没啥关系 扩展CRT 我们知道,中国剩余定理是用来解同余方程组 但是有一个非常令...

34190
来自专栏塔奇克马敲代码

RTKLIB源码解析(一)——单点定位(pntpos.c)

2.1K40
来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

74960
来自专栏Python数据科学

5种方法教你用Python玩转histogram直方图

直方图是一个可以快速展示数据概率分布的工具,直观易于理解,并深受数据爱好者的喜爱。大家平时可能见到最多就是 matplotlib,seaborn 等高级封装的库...

53210
来自专栏机器之心

教程 | 如何使用TensorFlow中的高级API:Estimator、Experiment和Dataset

选自Medium 作者:Peter Roelants 机器之心编译 参与:李泽南、黄小天 近日,背景调查公司 Onfido 研究主管 Peter Roelant...

79470

扫码关注云+社区

领取腾讯云代金券