首页 > 其他 > 详细

矩阵快速幂HDU2065

时间:2019-09-17 23:21:18      阅读:63      评论:0      收藏:0      [点我收藏+]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;//矩阵快速幂的应用
const int maxn = 4;
const int MOD = 100;
struct Matrix
{
    int m[maxn][maxn];
};//矩阵
const Matrix E =
{
    1,0,0,0,
    0,1,0,0,
    0,0,1,0,
    0,0,0,1
};//单位矩阵
const Matrix P
{
    2,1,1,0,
    1,2,0,1,
    1,0,2,1,
    0,1,1,2
};//基矩阵
//矩阵相乘函数
Matrix mult(const Matrix& a,const Matrix& b)
{
    Matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i=0;i!=maxn;++i)//对于每一行
    {
        for(int k=0;k!=maxn;++k)//对于每一行每一个数
        {
            for(int j=0;j!=maxn;++j)//对于每一列
            {
                c.m[i][j] += a.m[i][k]*b.m[k][j];
                c.m[i][j] %= 100; 
            }
        }
    }
    return c;
}
//矩阵的快速幂
Matrix quickPow(long long num)
{
    Matrix res = E,a = P;
    while(num)
    {
        if(num&1)
        {
            res = mult(res,a);
        }//如果为奇数的话
        a = mult(a,a);
        num >>= 1;//num 除等于 2
    }
    return res;
}
int main()
{
    int t,index = 0;
    while(cin>>t&&t)
    {
        int kase = 0;
        long long n;//计算矩阵的n次幂
        for(int i=0;i!=t;++i)
        {
            cin>>n;
            cout<<"Case "<<++kase<<": "<<quickPow(n).m[0][0]<<endl;
        }
        cout<<endl;
    }
}

  //学习了。ORZ

矩阵快速幂HDU2065

原文:https://www.cnblogs.com/newstartCY/p/11537688.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!