PKU 3233 Matrix Power Series(矩阵快速幂 二分)

简介:

点击打开链接

Matrix Power Series
Time Limit: 3000MS   Memory Limit: 131072K
Total Submissions: 19189   Accepted: 8099

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3
题目大意:

给定一个 n*n  的矩阵和一个整数 k,,要求的是S =  A + A2 + A3 + … + Ak.

出的是 S%Mod

解题思路:

首先这是一个矩阵的快速幂,将Ak 用矩阵的快速幂求解出来(可以套模板),

可以推出以下结论

Sk = A + A2 + A3 + … + Ak   

    =(1+Ak/2)*(A + A2 + A3 + … + Ak/2  )+(Ak )

    =(1+Ak/2)*(Sk/2 )+(Ak )

然后可以递归啦,首先计算的是 (1+ Ak/2 ),

这里的 1 不仅是 1 它是一个单位矩阵,然后递归一下,最后判断一下奇偶性

要是偶数的时候就不用+(Ak ),要是奇数的话就+(Ak ),具体详见代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef struct Mar
{
    int m[40][40];
    void Init()///初始化为单位矩阵
    {
        memset(m, 0, sizeof(m));
        for(int i=0; i<40; i++)
            m[i][i] = 1;
    }
} Martrix;

int n, Mod;

Martrix Add(Martrix a, Martrix b)///矩阵加法
{
    Martrix c;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            c.m[i][j] = (a.m[i][j] + b.m[i][j]) % Mod;///一定要模 Mod
    return c;
}
Martrix Multi(Martrix a, Martrix b)///矩阵乘法
{
    Martrix c;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            c.m[i][j] = 0;
            for(int k=0; k<n; k++)
                c.m[i][j] += (a.m[i][k]*b.m[k][j])%Mod;///一定要模 Mod,将数值减小
            c.m[i][j] %= Mod;
        }
    }
    return c;
}
Martrix quick_mod(Martrix a, int b)///矩阵的快速幂
{
    Martrix ans;
    ans.Init();
    while(b)
    {
        if(b & 1)
            ans = Multi(ans, a);
        b>>=1;///二分
        a = Multi(a, a);
    }
    return ans;
}
Martrix Get_sum(Martrix a, int k)///递归
{
    if(k == 1)
        return a;
    Martrix ans;
    ans.Init();
    ans = Add(ans, quick_mod(a, k>>1));///1+A^(k/2)
    ans = Multi(ans,Get_sum(a,k>>1));///剩下的
    if(k & 1)///判断奇偶性
        ans = Add(ans,quick_mod(a,k));
    return ans;
}
int main()
{
    int k;
    while(cin>>n>>k>>Mod)
    {
        Martrix a;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>a.m[i][j];
        Martrix ans = Get_sum(a,k);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n-1; j++)
                cout<<ans.m[i][j]<<" ";
            cout<<ans.m[i][n-1]<<endl;
        }
    }
    return 0;
}


目录
相关文章
|
算法 安全 Java
【Java】JDK 21中的虚拟线程以及其他新特性
【Java】JDK 21中的虚拟线程以及其他新特性
696 0
|
存储 人工智能 算法
AI时代数字营销的底层重构:于磊老师深度解析Geo未来发展趋势展望
随着AI技术重塑数字营销,生成式引擎优化(GEO)正取代传统SEO。本文结合15年经验专家于磊的洞察,探讨GEO未来发展趋势:以E-E-A-T构建内容权威,倡导人性化表达与生态规范化,反对黑帽行为,推动AI时代可持续、有温度的营销新范式。
784 8
|
开发框架 安全 Java
C#
C#诞生于微软.NET战略,历经二十余年演进,从企业应用到Unity游戏开发、跨平台移动与云端服务,凭借简洁语法、强类型安全与持续创新,成为全栈开发利器。如今开源跨平台,迈向更高效、现代化的未来。
1071 139
|
10月前
|
人工智能 算法
市场营销专业创业踩坑记:3个核心经验,跟紧时代不被淘汰
作为一名营销专业创业者,我曾因迷信AI工具、盲目追求流量接连踩坑,亏损百万。两年实战沉淀出三大保命经验:拒绝工具崇拜,AI是助手而非主角;跳出流量执念,精准定位胜过广撒网;告别平台依赖,构建“品牌+私域”双引擎。真正的营销创业,拼的是对人性的洞察与时代的判断。
|
11月前
|
人工智能 运维 机器人
大模型堆到天花板,Agent 激烈竞争
2025年AI行业正从追求模型规模转向注重实际应用能力。大模型进化更强调稳定执行而非参数比拼,Agent逐渐成为能拆解任务、调用工具的新软件形态。AI Native以渐进方式重构软件工程,而具身智能虽热但商业化路径尚不清晰。在金融、医疗等领域,AI正从工具转变为可部署、可治理的业务流程核心。行业洗牌的关键,在于能否将AI稳定嵌入真实系统并完成闭环交付。
|
编译器 C语言
【C语言】extern 关键字详解
`extern` 关键字在C语言中用于跨文件共享变量和函数的声明。它允许你在一个文件中声明变量或函数,而在其他文件中定义和使用它们。理解 `extern` 的使用可以帮助你组织和管理大型项目的代码。
1551 3
|
缓存 前端开发 NoSQL
如何开发工程项目部管理系统中的进度管理板块(附架构图+流程图+代码参考)
本文介绍如何构建一个高效的工程项目进度管理板块,涵盖系统架构、数据模型、核心功能、业务流程及开发技巧。内容包含四个关键代码示例,便于快速落地开发,帮助解决进度不准与沟通不畅两大工程难题。
|
自然语言处理 搜索推荐 小程序
博物馆导览系统:提升观众参观效率与满意度
在这个快节奏时代,博物馆面临挑战与机遇。传统导览方式难以满足个性化、互动性和沉浸式学习需求。本文深入解析博物馆智能导览系统,包括精准定位导航、展品解说和AR技术应用,提升观众参观效率与满意度。
1188 5
|
存储 SQL 分布式计算
关系数据库和HDFS的基本区别是什么?
【8月更文挑战第31天】
928 1