#1151 : 骨牌覆盖问题·二

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

上一周我们研究了2xN的骨牌问题，这一周我们不妨加大一下难度，研究一下3xN的骨牌问题？
所以我们的题目是：对于3xN的棋盘，使用1x2的骨牌去覆盖一共有多少种不同的覆盖方法呢？
首先我们可以肯定，奇数长度一定是没有办法覆盖的；对于偶数长度，比如2，4，我们有下面几种覆盖方式：

提示：3xN骨牌覆盖

输入

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

输出

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

样例输入
62247088
样例输出
4037

思路：

当N为基数的时候，肯定覆盖不了。

当N为偶数的时候，对N做除2操作，找出递推公式。

a[0] = 1;
a[1] = 3;
a[2] = 11;

递推公式为：

f(n)=3(f(n-1)+f(n-2))-f(n-3);

AC代码：

 #include <iostream>

 #include <algorithm>

 #define mod 12357

 using namespace std;

 //

 int solve(long long n)

 {

     n = n / ;

     int a[],t=;

     a[] = ;

     a[] = ;

     a[] = ;

     if (n < )

         return a[n];

     for (int i = ; i <= n; i++)

     {

         t = (*a[] + *a[]-a[]+mod)%mod;

         a[] = a[];

         a[] = a[];

         a[] = t;

     }

     return t;

 }

 int main()

 {

     long long n;

     while (cin >> n) {

         if (n & )

             cout <<  << endl;

         else

             cout << solve(n) << endl;

     }

     system("pause");

     return ;

 }

需要注意的是，有一个取余操作。

t = (3*a[2] + 3*a[1]-a[0]+mod)%mod;   括号内的数需要加上一个Mod，不然可能为负。

最新文章

  1. ReactNative入门 —— 动画篇（上）
  2. mysql支持跨表delete删除多表记录
  3. Leetcode: Largest BST Subtree
  4. android和ios，音频互通方案
  5. 通过FTP连接Azure上的网站
  6. java &lt;? super Fruit&gt;与&lt;? extends Fruit&gt;
  7. hdu 1023 Train Problem II
  8. 可变长参数列表误区与陷阱——va_arg不可接受的类型
  9. jquery 源码分析
  10. __declspec(dllimport)的作用
  11. Android 模块化编程之引用本地的aar
  12. svnkit添加节点
  13. RobotFramework自动化测试框架-移动手机自动化测试AppiumLibrary库其它的常见自动化关键字
  14. 函数PYXX_READ_PAYROLL_RESULT的dump问题
  15. MySQL 参数- Innodb_File_Per_Table（独立表空间）
  16. JeeSite中Excel导入导出
  17. JPA（Hibernate）
  18. [Synthetic-data-with-text-and-image]
  19. Vue+element组合el-table-column表头宽度自定义
  20. HSSF与XSSF导出excel文档

热门文章

  1. 访问cv::Mat中的数据时遇到的指针类型问题
  2. ES6标准
  3. 安装php时的配置选项
  4. Sublime Text 3065
  5. [ngRepeat:dupes] Duplicates in a repeater are not allowed. Use &#39;track by&#39; expression to specify uniq
  6. 平均值mean，众数mode，中值median 和 标准差stddev
  7. mysql中Can&#39;t connect to MySQL server on &#39;localhost&#39; (10061)
  8. maven可选依赖（Optional Dependencies）和依赖排除（Dependency Exclusions）
  9. C-函数与内存剖析
  10. CF449C Jzzhu and Apples （筛素数 数论？