前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >矩阵快速幂

矩阵快速幂

作者头像
AngelNH
发布2020-04-16 15:40:20
3220
发布2020-04-16 15:40:20
举报
文章被收录于专栏:AngelNI

tql,ORZ,catch me off ground。

矩阵快速幂

1.

分解来看,是由矩阵乘法,和快速幂组成

矩阵乘法

代码语言:javascript
复制
for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
 		for(int k=1;k<=n;k++)
 			c[i][j]+=a[i][k]*b[k][j];

快速幂

代码语言:javascript
复制
ll pow_ksm(ll a,ll n)
{
	ll res = 1;
    while(n)
    {
        if(n&1) res = res*a%mod;
        a = a*a%mod;
        n>>=1;
    }
    return res;
}

模板

代码语言:javascript
复制
struct matrix
{
    ll m[101][101];
}
matrix a, b;
matrix mul(matrix x,matrix y)
{
    matrix c;
    for(int i =1;i<=n;++i)
    {
        for(int j =1;j<=n;++j)
        {
            c.m[i][j] = 0;
		}
    }
    for(int i =1;i<=n;++i)
    {
        for(int j =1;j<=n;++j)
        {
            for(int k =1;k<=n;++k)
            {
                c.m[i][j] += x.m[i][k]*y.m[k][j]%mod;
            }
        }
    }
    return c;
}
matrix pow_ksm(matrix x,ll y)
{
    matrix ans;
  	memset(ans.m,0,sizeof ans.m);
	for(int i=1;i<=n;i++)
		ans.m[i][i]=1;
    while(y)
    {
        if(y&1) ans = mul(ans,x);
        x = mul(x,x);
        y>>=1;
    }
    return ans;
}

2.

poj3070

Change many times ,finally pass。

代码语言:javascript
复制
#include<iostream>

#include<cstring>
#include<stdio.h>
using namespace std;

typedef long long ll;
const int mod = 10000;
struct node
{
    ll m[5][5];
};
node mul(node a,node b)
{
    node c;
    memset(c.m,0,sizeof c.m);
    // for(int i =1;i<=5;++i)
    // {
    //     for(int j =1;j<=5;++j)
    //     {
    //         c.m[i][j] = 0;
    //     }
    // }
    for(int i=1;i<=2;++i)
    {
        for(int j =1;j<=2;++j)
        {
            for(int k =1;k<=2;++k)
            {
                c.m[i][j] =(c.m[i][j] + a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return c;
}
node ksm(node x,ll y)
{
    node ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i =1;i<=2;++i)
    {
        //for(int j =1;j<=2;++j)
            ans.m[i][i] = 1;
        
    }
    while(y)
    {
        if(y&1) ans = mul(ans,x);
        y>>=1;
        x = mul(x,x);
    }
    return ans;
}
int main()
{
    ll n;
    while(cin>>n&&n!=-1)
    {
        if(n==0)
            printf("0\n");
        else if(n==1||n==2)
            printf("1\n");
        else
        {
            node a,b;
            a.m[1][1] = 1;
            a.m[1][2] = 1;
            a.m[2][1] = 1;
            a.m[2][2] = 0;
            b.m[1][1] = 1;
            b.m[1][2] = 1;
            b.m[2][1] = 1;
            b.m[2][1] = 0;
            node ans = ksm(a,n-1);
            ans = mul(ans,b);
            printf("%d\n",ans.m[1][1] ) ;
         }
        
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-02-27|,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 矩阵快速幂
    • 1.
      • 矩阵乘法
      • 快速幂
      • 模板
    • 2.
      • poj3070
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档