`
Simone_chou
  • 浏览: 198075 次
  • 性别: 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;
}

 

分享到:
评论

相关推荐

    幂零矩阵的性质及应用参照.pdf

    比如,推论1表明A是幂零矩阵的等价条件是它的迹(即所有对角元素之和)属于整数集合Z,并且0ktr(A),这里的tr(A)表示矩阵A的迹。这个推论提供了判断矩阵是否为幂零的另一种方法。 在实际应用中,幂零矩阵具有重要的...

    TR069 TR098 TR064 TR067 资料 文档 大全

    TR069、TR098、TR064和TR067是四个重要的通信协议,主要用于远程管理和配置家庭网络设备,如宽带调制解调器、路由器、机顶盒等。这些协议由DSL论坛(现为Broadband Forum)制定,旨在提高服务提供商对家庭用户设备的...

    IPD技术评审(TR1-TR6)知识分享

    TR2需要产品设计规格、测试计划、需求跟踪矩阵等。这些输入材料是评审的基础,确保了评审的有效性和准确性。 总之,IPD技术评审(TR1-TR6)是产品开发过程中的关键控制点,通过这些评审,项目团队能够持续优化设计,...

    TR069协议中文版_tr069协议中文_tr069_TR098Amendment2_tr069.zip_

    TR069协议的中文版本对于中国和亚洲地区的用户来说尤其有价值,因为它提供了更易于理解的文档,使得技术人员能够更快速地理解和应用该协议。这份"TR069协议中文版.pdf"文档很可能是TR-069的完整标准翻译,包括所有...

    TR069和TR098协议文档

    TR069(Technical Report 069)和TR098是两种广泛应用于设备管理和服务提供商网络自动化的重要协议。这两种协议由DSL论坛(现为Broadband Forum)制定,旨在提供一种安全、可靠的方式来远程管理和配置家庭及企业网络...

    TR31 TR34标准.rar

    《TR31 TR34标准详解——对称密钥的非对称分发技术》 在信息安全领域,数据加密是保障信息安全的重要手段。对称密钥加密和非对称密钥加密是两种主要的加密方式,各有其优势与应用场景。今天我们将深入探讨TR31和TR...

    TR-111(属于TR069协议族)

    TR-111是TR-069协议族的一个重要组成部分,主要应用于家庭网络设备的远程管理。TR-069(Technical Report 069)是由DSL论坛(现为Broadband Forum)制定的一套标准,旨在提供一种安全、自动化的远程配置和管理家庭...

    TR069标准协议族

    TR111专注于DSL接入设备的诊断,它提供了标准化的诊断方法,使得服务提供商可以快速识别并解决与DSL连接相关的故障。这包括了线缆质量检查、性能测试等功能,有助于提高网络稳定性。 TR143则是针对IP电视(IPTV)...

    TR-104(tr069协议组中的一员)

    TR-104是TR-069协议族中的一个重要组成部分,主要关注家庭网关和其他CPE(Customer Premises Equipment)设备的管理。TR-069,全称为"Technical Recommendation CPE WAN Management Protocol",是由DSL论坛(现为...

    TR098:TR069宽带参数模型

    ### TR098:TR069宽带参数模型解析 #### 概述 TR098,即《Internet Gateway Device Data Model for TR-069》,是针对TR-069标准的一种数据模型规范,旨在为宽带网络中的网关设备提供统一的数据管理和控制接口。该...

    表达谱基因芯片筛选肝癌细胞中ATRA下游基因的应用研究.pdf

    1. 全反式维甲酸(ATRA):ATRA是一种药物,属于维甲酸类化合物,在此研究中被用于处理肝癌细胞系HepG2细胞。维甲酸类化合物具有调节细胞生长和分化的作用,因此在癌症研究中备受关注。 2. 肝癌细胞系HepG2:HepG2...

    TR069交互协议-TR098节点定义规范

    TR098节点定义规范是TR069协议的一个重要组成部分,主要针对家庭网关设备的管理和控制。TR069是一种广泛应用于远程管理和配置家庭网络设备的协议,特别是路由器和网关设备。该协议旨在提供一个标准接口,使得服务...

    tr的详细用法tr的详细用法

    cat a.txt | tr "[a-z]" "[A-Z]" &gt; b.txt ``` 5. **指定字符集删除**: - 删除所有非字母字符,并将所有剩余字符转换为一个换行符: ```bash tr -cs "[a-z][A-Z]" "\n" ``` 6. **字符替换**: - 在处理从 ...

    tr069主要协议规范

    6. "TR-111.pdf":TR-111规范可能涉及到特定设备的诊断和故障恢复过程,帮助运营商快速识别并解决用户端的问题。 7. "TR-110v1.01.pdf":TR-110可能定义了用于管理多服务接入平台(MSAP)的TR069扩展,这些平台支持...

    TR-142(Framework for TR-069 enabled PON devices)

    这对于快速定位问题并采取措施解决非常重要。 - **安全性**:在PON环境下应用TR-069协议时,安全性是一个关键考虑因素。本报告讨论了多种安全措施,如数据加密、访问控制等,以保护网络免受未经授权的访问和攻击。 -...

    TR181英文标准协议PDF

    TR181是宽带论坛(Broadband Forum)发布的一个技术报告,主要针对TR-069设备管理协议的数据模型。这个标准旨在规范和促进宽带网络系统的发展与部署。TR-069,全称为Automated Configuration Server (ACS) and CPE ...

    TR-135协议

    TR-135协议,即《适用于TR-069启用的机顶盒的数据模型》(Data Model for a TR-069 Enabled STB),是针对机顶盒(Set-Top Box,简称STB)这一特定设备类别的扩展与细化。这份由DSL论坛于2007年发布的技术报告,详细...

    TR-181_Issue-2_Amendment-2-Device Data Model For TR069

    1. **远程设备配置**:服务提供商可以利用TR-069协议远程配置用户的路由器、调制解调器等网络设备,以实现快速部署和自动化管理。 2. **故障诊断与维护**:当用户遇到网络问题时,服务提供商可以通过TR-069获取设备...

    TR181 Amendment 8 协议

    TR-181 Amendment 8协议是宽带论坛(Broadband Forum)制定的技术报告,专注于TR-069问题2的设备数据模型。这份文档是在2014年9月发布的,涵盖了TR-069 TR-181问题2的修订8版本。宽带论坛是一个非营利性的组织,旨在...

    tr069参数节点

    随着宽带技术的快速发展与普及,TR-069作为一种重要的远程配置管理协议,在运营商网络设备管理中扮演着至关重要的角色。本文旨在深入探讨《TR-098互联网网关设备数据模型》中的TR069参数节点规范,为读者提供一个...

Global site tag (gtag.js) - Google Analytics