热门标签 | 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函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • 使用Vultr云服务器和Namesilo域名搭建个人网站
    本文详细介绍了如何通过Vultr云服务器和Namesilo域名搭建一个功能齐全的个人网站,包括购买、配置服务器以及绑定域名的具体步骤。文章还提供了详细的命令行操作指南,帮助读者顺利完成建站过程。 ... [详细]
  • 本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本,并进行数据处理和保存。 ... [详细]
  • 本文介绍了如何利用JavaScript或jQuery来判断网页中的文本框是否处于焦点状态,以及如何检测鼠标是否悬停在指定的HTML元素上。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先,通过change事件监听用户选择的省份,并动态加载对应的城市列表。其次,详细讲解了使用Validation插件进行表单验证的方法,包括内置规则、自定义规则及实时验证功能。 ... [详细]
  • Android 渐变圆环加载控件实现
    本文介绍了如何在 Android 中创建一个自定义的渐变圆环加载控件,该控件已在多个知名应用中使用。我们将详细探讨其工作原理和实现方法。 ... [详细]
  • Python自动化处理:从Word文档提取内容并生成带水印的PDF
    本文介绍如何利用Python实现从特定网站下载Word文档,去除水印并添加自定义水印,最终将文档转换为PDF格式。该方法适用于批量处理和自动化需求。 ... [详细]
  • 探索弱监督开放域问答中的潜在检索机制
    本文探讨了在弱监督环境下,开放域问答系统中潜在检索技术的应用。通过引入反隐式任务预训练方法,研究展示了如何仅依赖问题答案对进行端到端的联合学习,而无需传统的信息检索系统。实验结果表明,在某些数据集上,这种新方法显著优于传统方法。 ... [详细]
  • 本文详细介绍了Java中org.w3c.dom.Text类的splitText()方法,通过多个代码示例展示了其实际应用。该方法用于将文本节点在指定位置拆分为两个节点,并保持在文档树中。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本文详细介绍如何在VSCode中配置自定义代码片段,使其具备与IDEA相似的代码生成快捷键功能。通过具体的Java和HTML代码片段示例,展示配置步骤及效果。 ... [详细]
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社区 版权所有