Python学习

九度题目1443:Tr A

题目描述:
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
输入:
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
输出:
对应每组数据,输出Tr(A^k)%9973。
样例输入:
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
样例输出:
2
2686

总结:
– 输入没有看清楚,习惯性的自有输入,其实是有数量限制的

– 不要设置很多全局变量,最后会混在一起,可以使用结构体,很好用

– 矩阵乘法不要自己臆想,要背调

代码

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<math.h>
#include<string.h>
#define M 9973
#define H 102
using namespace std;
typedef struct Matrix{
    int v[H][H];
} matrix;
//Matrix E;
//Matrix Ans;
Matrix Mul(Matrix aa,Matrix bb,int n){
//  cout<<"get in now"<<endl;
    Matrix cc;
    memset(cc.v,0,sizeof(cc.v));  //将所有的v置0
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int c=0;c<n;c++){
                cc.v[i][j]+=aa.v[i][c]*bb.v[c][j];
                cc.v[i][j]%=M;
            }
        }
    }
    return cc;
} 
 
Matrix pow(Matrix E,int k,int n){  //求x^y  x可能是longlong  E(n)^k 910^9==10^10 <21亿
    Matrix Ans;
    memset(Ans.v,0,sizeof(Ans.v));
    for(int i=0;i<n;i++){
                Ans.v[i][i]=1;
    }
    while(k!=0){
        if(k%2==1){
            Ans=Mul(E,Ans,n);
        }
        k/=2;
        E=Mul(E,E,n);
    }
    return Ans;
}
 
int main(){
    int t,n;
    int k;
    Matrix E;
    Matrix Ans;
    cin>>t;
        for(int j=0;j<t;j++){
            cin>>n>>k;
                    for(int a=0;a<n;a++){
                        for(int b=0;b<n;b++){
                            cin>>E.v[a][b];
                            E.v[a][b]%=M;
                        }
                    }
                    //矩阵输入完毕;
                     
                    Ans=pow(E,k,n);
                    int count=0;
                    for(int p=0;p<n;p++){
                        count=count + Ans.v[p][p];
                        count%=M;
                    }
                    cout<<count<<endl;
                 
            }
    return 0;
}
/**************************************************************
    Problem: 1443
    User: WZDCJ0206
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:1688 kb
****************************************************************/
Be the First to comment.

Leave a Comment

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据