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的内容。
每组数据的第一行有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; }
相关推荐
TR098节点定义规范旨在提供一套标准化的规范,用于描述和定义TR098节点。TR098是一种用于管理家庭网关设备的协议,它定义了一组数据模型和接口,用于配置、监控和管理这些设备。 该文档主要包含以下内容: 引言:...
IPD技术评审(TR1-TR6)知识分享IPD技术评审(TR1-TR6)知识分享IPD技术评审(TR1-TR6)知识分享IPD技术评审(TR1-TR6)知识分享IPD技术评审(TR1-TR6)知识分享
包含TR069文档协议学习,同时还包含TR098、TR064、TR104相关文档协议的学习。
包含TR069协议在内的标准协议族,TR198,TR104,TR111,TR143等。
索尼sony ccd-tr36_tr73_tr76_tr83_tr93_tr100_tr560_tr600_tr670pk_tr880摄像机维修服务手册
TR104,tr069协议组中的一个,英文
TR-142 Framework for TR-069 enabled PON devices
Applying TR-069 to Remote Management of Home Networking Devices
TR098:<<Internet Gateway Device Data Model for TR-069>>,TR069宽带参数模型,2007年12月版本
TR181英文标准协议
TR069和TR098协议文档
The architecture of TR-069 Amendment 2 [1] and TR-106 Amendment 1 [2] enables device management of CPE devices in the customer’s home, including the home gateway, and devices behind it. This ...
TR181协议详解 。 TR181是基于TR069的数据结构模型。 本文档为英文版本:release-2.15-51。
定义终端的TR-069 参数模型主要参考两个文档TR-106 和TR-135 ,TR-106 定义了基于TR-069管理的设备的通用数据模型,TR-135 定义了STB 的特定数据模型。由于目前针对STB 的数据管理没有提出具体要求,因此暂不...
tr069参数节点规范,里面对于tr069协议需求的节点,都有详细的节点规范需求描述
TR24A TR24B TR24P 无线收发模块 详细编程资料
Interoperable Method for Distribution of Symmetric Keys using Asymmetric
TR-181_Issue-2_Amendment-2-Device Data Model For TR069
该文档详细介绍tr069原理及工作流程,并结合实际例子进行抓包分析 培训内容: 1.TR069是什么 2.TR069有什么作用 3.TR069连接建立 4.TR069交互实例 5.TR069对CPE操作的常用方法
主要介绍TR069协议工作流程,TR069协议工作场景。