首页 > 其他分享 >hdu 3117(矩阵快速幂)

hdu 3117(矩阵快速幂)

时间:2023-06-28 23:02:16浏览次数:46  
标签:hdu temp 3117 res 矩阵 long int ori mod


题意:求斐波那契序列的第n个数。如果超过8位,只输出前4位和后4位。
题解:后4位比较好办,直接mod10000就可以了,前4位不知道怎么求,网上看到一个人写的很详细易懂,需要用到斐波那契通项公式,详细见→传送门

#include <stdio.h>
#include <math.h>
#include <string.h>
struct Mat {
    long long g[2][2];
}ori, res;
long long n;

Mat multiply(Mat x, Mat y, int mod) {
    Mat temp;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            temp.g[i][j] = 0;
            for (int k = 0; k < 2; k++)
                temp.g[i][j] = (temp.g[i][j] + x.g[i][k] * y.g[k][j]) % mod;
        }
    return temp;
}

void calc(long long n, int mod) {
    while (n) {
        if (n & 1)
            ori = multiply(ori, res, mod);
        n >>= 1;
        res = multiply(res, res, mod);
    }
}

int main() {
    while (scanf("%lld", &n) == 1) {
        if (n == 0 || n == 1) {
            printf("%lld\n", n);
            continue;
        }
        ori.g[0][0] = 1;
        ori.g[0][1] = ori.g[1][0] = ori.g[1][1] = 0;
        res.g[0][0] = res.g[0][1] = res.g[1][0] = 1;
        res.g[1][1] = 0;
        if (n < 40) {
            calc(n - 1, 1e9);
            printf("%lld\n", ori.g[0][0]);
        }
        else {
            calc(n - 1, 10000);
            double nn = n * log10((1.0 + sqrt(5.0)) / 2.0) - 0.5 * log10(5.0);
            double temp = nn - floor(nn);
            double temp2 = pow(10, temp);
            while (temp2 < 1e3)
                temp2 *= 10;
            printf("%d...%04lld\n", (int)temp2, ori.g[0][0]);
        }
    }
    return 0;
}


标签:hdu,temp,3117,res,矩阵,long,int,ori,mod
From: https://blog.51cto.com/u_10729926/6577233

相关文章

  • uva 12470(矩阵快速幂)
    题意:公式f(n)=f(n-1)+f(n-2)+f(n-3),给出n,f(1)=0,f(2)=1,f(3)=2,要求得出f(n)。题解:普通的矩阵快速幂模板题。#include<stdio.h>#include<string.h>constintMOD=1000000009;structMat{longlongg[3][3];}ori,res;longlongn;Matmultiply(......
  • hdu 5254(暴力)
    题解:暴力所有点,直到不存在可以0变1的点。#include<stdio.h>#include<string.h>constintN=505;intn,m,k,g[N][N],temp[N][N],vis[N][N];booljudge(intx,inty){if(x-1>=0&&y-1>=0){if(temp[x-1][y]&&te......
  • hdu 2855(矩阵快速幂)
    题意:计算公式题解:想推出矩阵相乘的形式,想了很久也想不出,然后看别人的题解有一个高中就学过的式子:(1+x)^n=Cn0x^n+Cn1x^(n-1)+Cn2x^(n-2)+Cn3x^(n-3)+····+Cnn然后想到斐波那契矩阵是{1,1,1,0},1看做一个单位阵{1,0,1,0},就会做了。。。#include<stdio.h>#include......
  • hdu 1241(dfs)
    ProblemDescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangularregionoflandatatime,andcreatesagridthatdividesthelandintonumeroussquareplots.......
  • 2023-06-28《计算方法》- 陈丽娟 - 向量和矩阵基础.md
    2023-06-28《计算方法》-陈丽娟-向量和矩阵基础Matlab计算方法矩阵范数导数条件数本问补充向量和矩阵范数的相关知识,为下一章节的线性方程组的迭代法以及误差分析做准备。除了参考《计算方法》一书,还参考了华东师范大学数学学院的课程材料《迭代方法与预处理》以及陈新宇、伍......
  • 免费修复一加手机高通崩溃qualcomm crashdump mode
    qualcommcrashdumpmodequalcommcrashdumpmodequalcommcrashdumpmode高通崩溃高通崩溃高通崩溃希望崩溃的小朋友们,送修之前能搜到。。线刷下载,挨个刷。。国内找个网站比较恶心,下载要要两块钱。。这个免费。。。https://onepluscommunityserver.com/list/Unbrick_Too......
  • 【雕爷学编程】Arduino动手做(131)---跑马灯矩阵键盘模块
    37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手尝试系列实验,不管成功(程序走通)与否,都会记录下来—小小的进步或是搞......
  • maltab 利用不同方式(自编高斯赛德尔迭代函数,逆矩阵,左除(\)运算)求解线性方程组的速度
    参考:matlabhelp文档:mldivide实际测试比较,这里K_Tem为一个2398*2398的稀疏矩阵,Guass_Seidal是自己写的高斯赛德尔迭代函数 ......
  • 混淆矩阵
    机器学习的结果要用不同于训练数据的测试数据进行评价,否则就没有意义针对训练数据的100%准确率是没有意义的……准确率粗略的评价对象是准确率,旨在评价数据中分类正确的样本数与样本总数之比混淆矩阵首先……简单起见,考虑二分类问题的评价方法。将符合设定的训练数据......
  • matlab判断一行元素是否在其一个矩阵集中
      index=0......