文档章节

poj3070Fibonacci 矩阵快速幂

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:34
字数 197
阅读 7
收藏 0

题目链接:http://poj.org/problem?id=3070

code:

//矩阵快速幂
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Mod 10000
using namespace std;
typedef struct juzhen{
    int a11,a12,a21,a22;
}JZ;
JZ quickpow(JZ s,int n)
{
    JZ base = s;
    // printf("%d %d\n%d %d\n",base.a11,base.a12,base.a21,base.a22);
    int ta11,ta12,ta21,ta22;
    s.a11 = s.a22 = 1;
    s.a12 = s.a21 = 0;
    while(n)
    {
        if((n & 1))
        {
            ta11 = s.a11*base.a11 + s.a12*base.a21;
            ta12 = s.a11*base.a12 + s.a12*base.a22;
            ta21 = s.a21*base.a11 + s.a22*base.a21;
            ta22 = s.a21*base.a12 + s.a22*base.a22;
            s.a11 = ta11 % Mod;
            s.a12 = ta12 % Mod;
            s.a21 = ta21 % Mod;
            s.a22 = ta22 % Mod;
        }
        ta11 = base.a11*base.a11 + base.a12*base.a21;
        ta12 = base.a11*base.a12 + base.a12*base.a22;
        ta21 = base.a21*base.a11 + base.a22*base.a21;
        ta22 = base.a21*base.a12 + base.a22*base.a22;
        base.a11 = ta11 % Mod;
        base.a12 = ta12 % Mod;
        base.a21 = ta21 % Mod;
        base.a22 = ta22 % Mod;
        n >>= 1;
    }
   // printf("%d %d\n%d %d\n",s.a11,s.a12,s.a21,s.a22);
    return s;
}
int main()
{
    int n;
    JZ s,e;
    s.a11 = s.a12 = s.a21 =  1;
    s.a22 = 0;
    while(cin >> n && n!=-1)
    {
        e = quickpow(s,n);
        //printf("%d %d\n%d %d\n",e.a11,e.a12,e.a21,e.a22);
        cout << e.a12 << endl;
    }
    return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5499379.html

YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
hdu2243考研路茫茫——单词情结 【AC自动机+动态规划+矩阵快速幂】

这道题就是bzoj1030的翻版,那道题题解见这里。还是用总方案数减去一个单词都不包含的方案数,只不过节点很少,不到30个,就可以用矩阵快速幂优化。 不过注意要求的是长度小于L的,所以矩阵多...

cdsszjj
2018/01/25
0
0
HDU5950 矩阵快速幂(巧妙的递推)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5950 题意:f[n] = 2*f[n-2] + f[n-1] + n^4 思路:对于递推题而言,如果递推n次很大,则考虑矩阵快速幂的方式推出递推式,计算出累乘...

乌克兰大野猪
11/06
0
0
矩阵快速幂之矩阵构造思想(转)

原文链接 博主写的很好 (转给师弟师妹们看~) 快速幂的思想: 假设我们要求a^b,最朴素的方法就是不断地乘a,乘b次,复杂度O(b)。 如果b很大,10^9,就需要用快速幂的思想。 例:a=3,b=100...

akatsuki__itachi
2018/05/24
0
0
BJ模拟 装饰地板【状压dp+特征多项式优化矩阵快速幂】

题目大意: 给一个 解题思路: 看到 那如何求一个矩阵的特征多项式呢? 如果这是一个常系数线性递推矩阵,那么有结论: 如果有大佬精通多项式算法,可以把多项式直接带进矩阵高斯消元算,应该...

cdsszjj
2018/03/15
0
0
2018 Multi-University Training Contest 7

1001:Age of Moyu 1002:AraBellaC 枚举循环周期,对每个循环周期内的mxa,mnb,mxb,mnc二分寻找,要保证(mxa-1)%len<(mnb-1)%len和(mxb-1)%len<(mnc-1)%len。 000000"> 000000"> 000000">......

Hetui
2018/08/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

利用CSS禁止手机长按出现气泡: 复制、选择等功能

可以用 * ,也可作用于一个div div{  -webkit-touch-callout:none;  /*系统默认菜单被禁用*/  -webkit-user-select:none; /*webkit浏览器*/  -khtml-user-select:none; /*早期浏览...

蓝小驴
53分钟前
9
0
前端的一些雕虫小技,从100%和滚动条说起

1、100%和滚动条 当我们在css中把html和body同时设为100%时,会出现滚动条 html, body { width: 100%; height: 100%; } 原因是html和b...

wphmoon
今天
8
0
电力区块链应用案例【2019】

随着区块链技术的日益普及,出现了大量创业企业尝试使用区块链技术来解决能源与电力行业中存在的问题。在本文中,我们将介绍其中的三个能源区块链项目。 能源行业以价格不透明著称:消费者很...

汇智网教程
今天
12
0
聊聊rocketmq的adjustThreadPoolNumsThreshold

序 本文主要研究一下rocketmq的adjustThreadPoolNumsThreshold DefaultMQPushConsumer rocketmq-client-4.5.2-sources.jar!/org/apache/rocketmq/client/consumer/DefaultMQPushConsumer.ja......

go4it
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部