`
Simone_chou
  • 浏览: 196975 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Tr A(矩阵快速幂)

    博客分类:
  • HDOJ
 
阅读更多

Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2650    Accepted Submission(s): 1972


Problem Description
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
 

 

Input
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
 

 

Output
对应每组数据,输出Tr(A^k)%9973。
 

 

Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
 

 

Sample Output
2
2686
 

 

Author

 

xhd

      思路:

      矩阵快速幂。按要求求出结果即可。

 

      AC:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;

const int MOD = 9973;

mat mul (mat a, mat b) {
    mat c(a.size(), vec(b[0].size()));

    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < b[0].size(); ++j) {
            for (int k = 0; k < b.size(); ++k) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }

    return c;
}

mat pow (mat a, int n) {
    mat b(a.size(), vec(a[0].size()));
    for (int i = 0; i < a.size(); ++i) {
        b[i][i] = 1;
    }

    while (n > 0) {
        if (n & 1) b = mul(b, a);
        a = mul(a, a);
        n >>= 1;
    }

    return b;
}

int main() {

    int t;
    scanf("%d", &t);

    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);

        mat a(n, vec(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%d", &a[i][j]);
            }
        }

        a = pow(a, k);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum = (sum + a[i][i]) % MOD;
        }

        printf("%d\n", sum);
    }

    return 0;
}

 

分享到:
评论

相关推荐

    19-20复旦大学《数学分析AI》期中考试试卷.pdf

    4. **矩阵方程与特征值**:第四题涉及到矩阵方程和特征值,要求找到满足A^2 - AB = I3的矩阵B,同时计算迹(tr)(BA - A^2)。这需要用到特征值和特征向量的概念,以及矩阵的幂运算和乘法。 5. **反对称矩阵**:第五...

    C++使用string的大数快速模幂运算(6)

    本次项目目标:使用C++完成对于大数的相关...模幂快速算法 a,m为正整数,将m表示为二进制形式 则 可得 举个例子 代码中有之前的减法 乘法 取模 除法运算  可得以下快速指数算法以及运行截图 #include #include #i

    求逆矩阵的并行CH法数值不稳定性 (1992年)

    这是一个纯CH法求逆的过程,其中涉及到矩阵幂次的计算可以通过快速算法进行优化。 #### 三、并行计算中的CH法 从并行计算的角度看,CH法只涉及简单的矩阵加法和乘法操作,这使得其并行化成为可能。例如,可以使用...

    《基于YOLOv8的增强现实识别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    Android毕设实战项目Android系统NFC手机读身份证(二代证).zip

    【项目资源】: 适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    基于开源数据集与YOLO11x训练的安全帽识别模型权重文件

    模型权重文件介绍 1. 基于开源数据集训练,训练集包含15000+图片,训练100 epochs 2. 基于YOLO11x模型进行的训练 3. 模型识别类别有2类:helmet、no-helmet

    ARM仿真器快速使用资料+绿色版软件 附视频-20210701.zip

    ARM仿真器快速使用资料+绿色版软件 附视频-20210701.zip

    毕业设计汽车式起重机液压系统的设计(论文设计说明书18000字,CAD图纸13张)

    内容概要:本文详细介绍了QY20B型汽车起重机液压系统的设计过程,涵盖其背景、发展史、主要运动机构及其液压回路设计。文章首先概述了汽车起重机的分类和发展历程,强调了液压技术在现代起重机中的重要性。接着,文章深入分析了QY20B型汽车起重机的五大主要运动机构(支腿、回转、伸缩、变幅、起升)的工作原理及相应的液压回路设计。每个回路的设计均考虑了性能要求、功能实现及工作原理,确保系统稳定可靠。此外,文章还详细计算了支腿油缸的受力、液压元件的选择及液压系统的性能验算,确保设计的可行性和安全性。 适合人群:从事工程机械设计、液压系统设计及相关领域的工程师和技术人员,以及对起重机技术感兴趣的高等院校学生和研究人员。 使用场景及目标:①为从事汽车起重机液压系统设计的工程师提供详细的参考案例;②帮助技术人员理解和掌握液压系统设计的关键技术和计算方法;③为高等院校学生提供学习和研究起重机液压系统设计的实用资料。 其他说明:本文不仅提供了详细的液压系统设计过程,还结合了实际工程应用,确保设计的实用性和可靠性。文中引用了大量参考文献,确保设计依据的科学性和权威性。阅读本文有助于读者深入了解汽车起重机液压系统的设计原理和实现方法,为实际工程应用提供有力支持。

    Unity Beautify 3 - Advanced Post Processing 23.0版本

    Unity Beautify 3 - Advanced Post Processing 23.0版本

    基于数据包络分析的中国旅游业发展效率特征

    基于数据包络分析的中国旅游业发展效率特征

    毕业设计物联网实战项目基于物联网技术的智能拐杖及与服务平台.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    (源码)基于蓝牙技术的多通道键盘.zip

    # 基于蓝牙技术的多通道键盘 ## 项目简介 在多设备工作环境中,用户常常需要在家庭电脑、工作笔记本或平板电脑之间频繁切换键盘输入,这不仅占用了大量桌面空间,而且操作不便。本项目旨在通过蓝牙技术,设计一款能够同时连接多个设备并实现一键切换的多通道键盘,从而简化用户的操作流程,提高工作效率。 ## 项目的主要特性和功能 1. 多设备连接键盘可以同时连接多达三个不同的设备。 2. 一键切换通过按键即可快速切换输入目标设备。 3. 高性能微控制器采用ATMega32u4微控制器,提供足够的GPIO引脚,支持Arduino编程环境,便于固件开发和升级。 4. 蓝牙模块使用RN42蓝牙模块,确保稳定的设备连接和数据传输。 5. 电压调节器使用MIC4680电压调节器,确保系统稳定供电。 ## 安装使用步骤 1. 硬件准备 获取ATMega32u4微控制器、RN42蓝牙模块、MIC4680电压调节器等硬件组件。 2. 电路设计

    毕设单片机实战项目基于 ESP8266 的智能家居解决方案.zip

    【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    基于Vue.js和SpringBoot的研究生调研管理系统.zip

    基于Vue.js和SpringBoot的研究生调研管理系统.zip

    地理信息文件,许昌市各县区政区图,shp格式,可编辑

    地理信息文件,许昌市各县区政区图,shp格式,可编辑

    《基于YOLOv8的运动协会监测系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    Scratch放飞气球 2024年9月电子学会scratch三级考试真题源代码

    Scratch放飞气球 2024年9月电子学会scratch三级考试真题源代码 综合考查角色添加、背景添加、初始位置、移动步数、方向旋转、造型切换、左右翻转、碰到边缘反弹、无限循环、条件判断、鼠标控制、碰撞检测等积木的使用;难点在于: 如何实现蝙蝠不断移动 如何实现蝙蝠边移动边挥翅膀 如何实现Ripley跟随鼠标移动 如何实现蝙蝠碰到Ripley移到随机位置 充分掌握重复执行和碰撞检测积木的使用 详细解题思路和步骤可以查看博客: https://scratch.blog.csdn.net/article/details/142934767 小兔子编程给小朋友们分享各种少儿编程(Scratch编程、python编程、C++编程等)学习、考级和比赛相关资料;更多少儿编程相关的学习资料,可以访问博主博客 https://blog.csdn.net/frank2102 期待小朋友们相互交流学习,有什么问题,建议或者意见可以直接给博主留言,或者私下,博主看到后会第一时间给到您相应的回复

    毕业设计物联网实战项目基于STM32L0低功耗微控制器的物联网智能垃圾桶(HAL).zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    前端分析-2023071100789s102102

    前端分析-2023071100789s102102

    毕业设计物联网实战项目基于VUE+element开发的物联网后台管理系统,金大万翔特供.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

Global site tag (gtag.js) - Google Analytics