[POJ3420]QuadTiling

作者:网络    软件教程库   2020-05-13

quad tiling

time limit:1000ms memory limit:65536k
total submissions:3495 accepted:1539

description

tired of thetri tilinggame finally, michael turns to a more challengeable game, quad tiling:

in how many ways can you tile a 4 times;n(1 le;nle; 109) rectangle with 2 times; 1 dominoes for the answer would be very big, output the answer modulom(0 mle; 105).

input

input consists of several test cases followed by a line containing double 0. each test case consists of two integers,nandm, respectively.

output

for each test case, output the answer modulesm.

sample input

1 10000
3 10000
5 10000
0 0

sample output

1
11
95

source

poj monthly--2007.10.06, dagger

川大校赛的原题出处,,,醉了,,比赛的时候一直没推出公式,唉,弱得不行

重点在求递推公式,再矩阵快速幂即可。

scu 4430 把输入改一下就可以了

#include iostream
#include cstdio
#include cstring
using namespace std;
#define ll long long
#define n 10

int mod;
struct matric
{
    int size;
    int a[n][n];
    matric(int s=0)
    {
        size=s;
        memset(a,0,sizeof(a));
    }
    matric operator * (const matric t)
    {
        matric res=matric(size);
        for(int i=0;isize;i++)
        {
            for(int k=0;ksize;k++)
            {
                if((*this).a[i][k])
                    for(int j=0;jsize;j++)
                    {
                        res.a[i][j]+=(ll)(*this).a[i][k]*t.a[k][j]%mod;
                                    res.a[i][j]=(res.a[i][j]+mod)%mod;
                    }
            }
        }
        return res;
    }
    matric operator ^ (int n)
    {
        matric ans=matric(size);
        for(int i=0;isize;i++) ans.a[i][i]=1;
        while(n)
        {
            if(n1) ans=ans*(*this);
            (*this)=(*this)*(*this);
            n=1;
        }
        return ans;
    }
    void debug()
    {
        for(int i=0;isize;i++)
        {
            for(int j=0;jsize;j++)
            {
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
    }
};
int main()
{
    int n;
    while(scanf("%d%d",n,mod),n||mod)
    {
        matric a=matric(4);
        matric b=matric(4);
        a.a[0][0]=1;
        a.a[0][1]=1;
        a.a[0][2]=5;
        a.a[0][3]=11;

        b.a[0][3]=-1;
        b.a[2][3]=5;
        b.a[1][0]=b.a[2][1]=b.a[3][2]=b.a[1][3]=b.a[3][3]=1;

        b=b^n;
        a=a*b;
        printf("%d\n",(a.a[0][0]+mod)%mod);
    }
    return 0;
}

[poj 3420] quad tiling

原文地址:http://www.cnblogs.com/hate13/p/4471465.html

软件教程库 该篇文章地址:https://www.itjcku.com/9999/1091369.html

阅读全部内容


Tags:

返回首页



推荐内容

C-关键字,标识符,注释

一.关键字:c语言中提供了有特殊含义的符号,也叫做保留字。 c语言中一个32个关键字,这些关键字都被赋予了 ...

C-基本概念

一.程序结构 1.c 程序结构:任何一个c程序都是由一个或小个程序代码块组成,每个小程序都有自己的功能,一般称这些小 ...

应该具备的能力

1. 学习能力(learning ability)   有些东西不懂很正常,从不懂到懂,从懂到精通,自己想想,原来不会的 ...

Apache-rhel5.8环境下编译安装

apache安装过程 step 1:安装包gcc或gcc-c++# yum install gcc#yum insta ...

OpenWrt学习目标

最近在研究openwrt,总感觉这一看一点那也了解一点,没有目的,也没有重心。 这里,给自己拟定一个目标,就朝着这个目标 ...

HelloKiki(hdu3579+不互质的中国剩余定理)

hello kiki time limit:1000msmemory limit:32768kb64bit io ...

android环境下摄像头数据采集及显示

以前项目涉及些摄像头预览及数据处理操作,当时的需求是除了做摄像头预览外,还要显示文字、个性图像等,当初在查找资料实 ...

uva10003CuttingSticks简单区间dp

// uva 10003 cutting sticks 区间dp // 经典的区间dp // dp(i,j)表示切割小木 ...

Go的语言特性总结

写在前面: 近来关于对golang的讨论有很多,七牛的几个大牛们也断定go语言在未来将会快速发展,并且很可能会取代ja ...

golang控制channel的出入口

golang控制channel的出入口 我们常常使用channel来在多个goroutine之间做数据通讯,但是cha ...

UVA10479TheHendrieSequence规律

题目大意:一个序列,刚开始由0变到了1,接着往后一个个变化下去 变化的规则是,如果当前数是k,就在这个序列的最后面加上 ...

在不是Activity类中调用Toast和Dialog

有时候我们需要在非activity类中处理一些逻辑,显示toast对话框或者是弹出一个dialog,但是在非activi ...

查询Oraclesql语句中绑定变量值的方法

alter session set nls_date_format = #39;yyyy-mm-dd,hh24:mi:s ...

Hdoj1588GaussFibonacci【矩阵快速幂】

gauss fibonacci time limit: 1000/1000 ms (java/others) m ...

Hdoj5195DZYLovesTopologicalSorting【拓扑】+【线段树】

dzy loves topological sorting time limit: 4000/2000 ms (jav ...

【转自mos文章】使用单条sql来查询出awr中的syatemstatistics

使用单条sql来查询出awr中的syatem statistics 参考自: how to monitor system ...

I.MX6Q(TQIMX6Q/TQE9)学习笔记——新版BSP之u-boot移植

前段时间就开始学习i.mx6q了,但是最近工作实在是忙,间断了一些时间了。为了提高移植效率,还是考虑移植freescal ...

eclipse应用技巧

最近发现eclipse作为ide还是有很多值得探索的使用技巧的,转载一下他人整理好的资源以做分享。 快捷键的使用,加速 ...

Mysql创建数据库的排序规则中文选择哪种编码

mysql中文编码 mysql创建数据库的排序规则 中文 选择哪种编码原文地址:http://blog. ...

线性表简述

一、简单实现增,删,改、查 package datatructs; /** * 表接口 */ public int ...

android测试本地服务调试流程

我今天调试的整个过程 1,安卓发现连不上本地的tomcat 2,使用浏览器直接尝试,发现可以连上 3,怀疑是安卓app和 ...

设计模式1

静态工厂模式,工厂方法模式,抽象工厂模式 工厂方法改进了添加新产品时,静态工厂不满足的开-闭原则;而抽象工厂满足了当产品 ...

c语言文件操作总结

#includelt;stdio.hgt; /********************************** ...

(c#)如果添加的字段中已经有了身份证号码,则年龄和性别和出生年月可得

//把界面文本框里面的身份证号进行提取,以二代身份证为例 model.ecardid = txt_cardno. ...

Scrum时间估算

在新公司里,不懂软件工程的产品经理经常逼迫研发人员作出很不靠谱的时间估算。常见场景有下面这些: 需求未细化的情况下要求给 ...

C++11中uniforminitialization和initializer_list

c++11中出现了uniform initialization的概念: int a1 = {1};//ok int a ...

关于Scrum

最近某些产品经理发出下两周的工作计划的时候,喜欢带上sprint这个字眼,看上去貌似是要走敏捷开发这一套,只可惜,我觉得 ...

输入输出简单解释

;汇编指令,表示程序将被汇编成能在intel386系列及以上的计算机上运行.386;model flat 表明程序使用保 ...

2015第18周五问题即机会

问题即机会,当一切问题都不存在的时候,请问你的机会在哪里? 你能达到怎样的境界,取决于你怎样认识这个世界。对于问题,有人 ...

solr配置方案

http://www.sjsjw.com/kf_cloud/article/44_5945_1823.asp cento ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com