热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

POJ3420QuadTiling【矩阵快速幂】

QuadTilingTimeLimit:1000MSMemoryLimit:65536KTotalSubmissions:5008Accepted:2269DescriptionT

Quad Tiling

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 5008 Accepted: 2269

Description

Tired of the Tri Tiling game finally, Michael turns to a more challengeable game, Quad Tiling:

In how many ways can you tile a 4 × N (1 ≤ N ≤ 109) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0

Input

Input consists of several test cases followed by a line containing double 0. Each test case consists of two integers, N and M, respectively.

Output

For each test case, output the answer modules M.

Sample Input

1 10000

3 10000

5 10000

0 0

Sample Output

1

11

95

Source

POJ Monthly--2007.10.06, Dagger

问题链接:POJ3420 Quad Tiling

问题简述:(略)

问题分析

    递推式如下:

a[0]=1,a[1]=1,a[2]=5,a[3]=11,

a[n]=a[n-1]+5a[n-2]+a[n-3]-an-4

    采用矩阵快速模幂计算,模板题。关键是找到那个递推式。

程序说明:(略)

参考链接:(略)

题记:(略)

AC的C++语言程序如下:

/* POJ3420 Quad Tiling */
#include
#include
using namespace std;
const int N = 10;
const int M = 10;
int r, mod;
struct Matrix
{
int n,m;
int a[N][M];
void clear()
{
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator +(const Matrix &b) const
{
Matrix c;
c.n = n;
c.m = m;
for(int i = 0; i for(int j = 0; j c.a[i][j] = a[i][j] + b.a[i][j];
return c;
}
Matrix operator -(const Matrix &b) const
{
Matrix c;
c.n = n;
c.m = m;
for(int i = 0; i for(int j = 0; j c.a[i][j] = a[i][j] - b.a[i][j];
return c;
}
Matrix operator *(const Matrix &b) const
{
Matrix c;
c.clear();
c.n = n;
c.m = b.m;
for(int i = 0; i for(int j = 0; j for(int k = 0; k {
c.a[i][j] += a[i][k] * b.a[k][j];
c.a[i][j] %= mod;
}
return c;
}
Matrix powermod(int x)
{
Matrix c;
c.clear();
c.n = c.m = n;
for(int i = 0; i c.a[i][i] = 1;
if(x == 0)
return c;
else if(x == 1)
return *this;
Matrix d = powermod(x / 2);
d = d * d;
if(x % 2 )
d = d * (*this);
return d;
}
};
int main()
{
while(scanf("%d%d", &r, &mod) == 2 && (r || mod)) {
int a[] = {1, 1, 5, 11};
if(r <= 3) {
printf("%d\n", a[r] % mod);
continue;
}
Matrix b;
b.clear();
b.n = b.m = 4;
b.a[0][1] = b.a[1][2] = b.a[2][3] = 1;
b.a[3][0] = -1;
b.a[3][1] = 1;
b.a[3][2] = 5;
b.a[3][3] = 1;
b = b.powermod(r - 3);
Matrix x;
x.clear();
x.n = 4;
x.m = 1;
x.a[0][0] = 1;
x.a[1][0] = 1;
x.a[2][0] = 5;
x.a[3][0] = 11;
x = b * x;
printf("%d\n",(x.a[3][0] + mod) % mod);
}
return 0;
}


推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 使用GDI的一些AIP函数我们可以轻易的绘制出简 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 本文详细介绍了Java中的访问器(getter)和修改器(setter),探讨了它们在保护数据完整性、增强代码可维护性方面的重要作用。通过具体示例,展示了如何正确使用这些方法来控制类属性的访问和更新。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • 解决JAX-WS动态客户端工厂弃用问题并迁移到XFire
    在处理Java项目中的JAR包冲突时,我们遇到了JaxWsDynamicClientFactory被弃用的问题,并成功将其迁移到org.codehaus.xfire.client。本文详细介绍了这一过程及解决方案。 ... [详细]
author-avatar
用户3w7mnpewca
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有