Hdoj1588GaussFibonacci【矩阵快速幂】

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

gauss fibonacci

time limit: 1000/1000 ms (java/others) memory limit: 32768/32768 k (java/others)
total submission(s): 2584 accepted submission(s): 1078

problem description
without expecting, angel replied quickly.she says: “i’v heard that you’r a very clever boy. so if you wanna me be your gf, you should solve the problem called gf~. ”
how good an opportunity that gardon can not give up! the “problem gf” told by angel is actually “gauss fibonacci”.
as we know ,gauss is the famous mathematician who worked out the sum from 1 to 100 very quickly, and fibonacci is the crazy man who invented some numbers.

arithmetic progression:
g(i)=k*i+b;
we assume k and b are both non-nagetive integers.

fibonacci numbers:
f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2) (n=2)

the gauss fibonacci problem is described as follows:
given k,b,n ,calculate the sum of every f(g(i)) for 0=i

#include cstdio
#include iostream
#include cstring
using namespace std;
#define ll __int64

struct node{
    ll num[3][3];
};
node e, a;
ll n, m, k, b;

node mul(node aa, node bb){
    node c;
    for(int i = 1; i  3; ++i){
        for(int j = 1; j  3; ++j){
            c.num[i][j] = 0;
            for(int k = 1; k  3; ++k){
                c.num[i][j] = (c.num[i][j]+aa.num[i][k]*bb.num[k][j])%m;
            }
        }
    }
    return c;
}

node fa(node a, ll n){
    node b = e;
    while(n){
        if(n1) b = mul(a, b);
        n = 1;
        a = mul(a, a);
    }
    return b;
}

node add(node aa, node bb){
    node c;
    for(int i = 1; i  3; ++i){
        for(int j = 1; j  3; ++j){
            c.num[i][j] = (aa.num[i][j]+bb.num[i][j])%m;
        }
    }
    return c;
}

node dg(node p, ll k){  //这里很巧
    if(k == 1) return p;
    else if(k1) return add(dg(p, k-1), fa(p, k)); //这里就是a^(k-1)+a^k
    else return mul(dg(p, k1), add(fa(p, k1), e));//这里就是 a^k+a^(k1);
}

int main(){
    e.num[1][1] = e.num[2][2] = 1;
    e.num[1][2] = e.num[2][1] = 0;
    a.num[1][1] = a.num[1][2] = a.num[2][1] = 1; a.num[2][2] = 0;
    while(cin  k  b  n  m){
        node ak = fa(a, k);
        node ab = fa(a, b);
        node ans = dg(ak, n-1);
        ans = add(e, ans);
        ans = mul(ab, ans);
        cout  ans.num[1][2] endl;
    }
    return 0;
}

hdoj 1588 gauss fibonacci 【矩阵快速幂】

原文地址:http://blog.csdn.net/shengweisong/article/details/45423839

本文内容由软件教程库(原文链接:https://www.itjcku.com/9999/1091342.html)本站为各位整理

阅读全部内容


Tags:矩阵快速

返回首页



推荐内容

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 ...

什么是二维码?

二维码,业界当然是人人听说,人人用过。 这个话题,我倒是百感交集,我一直认为,我有一种二维码情节。 一方面, 我自认 ...

1475:方格取数

1475: 方格取数 time limit:5 secmemory limit:64 mbsubmit:578solv ...

敏捷开发宣言(一)

原文: inpiduals and interactionsover processes and tools worki ...

(C#)一个项目的配置和增删改查

一、windows窗体项目环境配置步骤 1.文件mdash;gt;新建mdash;gt;项目mdash;gt;windo ...

比例简化

题目描述description 在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示 ...

sockaddr和sockaddr_in的区别

struct sockaddr和struct sockaddr_in这两个结构体用来处理网络通信的地址。 在各种系统调用 ...

基于Html5的智能家居手机客户端设计(一)——找到openhab的rest

今天开始我的毕业设计,基于html5的智能家居手机客户端设计。挑剔了好久,终于找到我可以使用国外开源项目智能家居核心 ...

阅读《大道至简--软件工程实践者的思想》有感(3)

阅读完《大道至简--软件工程实践者的思想》,明白了软件与程序的区别,《战国策-秦策》中的那句话,王不如远交而近攻, ...

10条建议让你创建更好的jQuery插件

前言:在开发过很多 jquery 插件以后,我慢慢的摸索出了一套开发jquery插件比较标准的结构和模式。这样我就可以 ...

nexus7升级失败后手动刷系统

http://bbs.gfan.com/android-6934570-1-1.html 步骤如下: 1. 下载a ...

SWUSTOJ爬不出去的水井(0333)

爬不出去的水井(0333) time limit(ms): 1000memory limit(kb): 6 ...

移动端Web开发注意点

不用考虑浏览器兼容性 移动端开发主要对象是手持设备,其中绝大部分是ios和android系统,so,在开发此类页面时不必 ...

CDN云主机与传统虚拟主机功能对比

cdn云主机与传统虚拟主机功能对比   传统的虚拟主机都是单台服务器,一旦机器硬件损坏、ip被封、机房网络故障等,都将导 ...

找斐波那契数列中的第N个数

题目描述 description 用递归的方法求斐波那契数列中的第n个数 输入输出格式input/output 输入格 ...


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