首页 > ACM题库 > HDU-杭电 > HDU 1575 Tr A-数论应用-[解题报告] C++
2013
12-12

HDU 1575 Tr A-数论应用-[解题报告] C++

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

题目链接:点击打开链接

配合上一篇博客:矩阵乘法介绍的模板题。要求求解Tr(a^k)%9937,注意不要到最后才余,在每处理完一次的时候就余一下(矩阵性质:矩阵中的每个数同时除以/乘以相同整数,矩阵的性质均不变(包括矩阵的迹、矩阵的秩、矩阵的最简阶梯行列式等等)否则数字过大会溢出。

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

class Mat
{
public:
    int mat[15][15];
};

int n;     //维度,即矩阵A的行数
int MOD=9973;//好多问题要求给出取余之后的数字
Mat E;

void initE()
{
	for(int i=0;i<15;i++)
		E.mat[i][i]=1;
}

Mat operator*(Mat a,Mat b)
{
    int i,j,k;
    Mat c;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
       		c.mat[i][j] = 0;
       		for (k=0;k<n;k++)
       		{
                	c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]);
       		}
       		c.mat[i][j]%=MOD;
        }
    }
    return c;
}

Mat operator+(Mat a,Mat b)
{
    Mat c;
    int i,j;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
            c.mat[i][j] = a.mat[i][j]+b.mat[i][j];
        c.mat[i][j]%=9973;
    }
    return c;
}

Mat operator^(Mat a,int x)  
{  
     Mat p = E,q = a;  
     while (x>=1)  
     {  
         if(x%2==1)  
             p = p*q;  
         x/=2;  
         q = q*q;  
     }  
     return p;  
}

Mat solve(Mat a,int p)  
{  
     if(p==1)  
         return a;
     else if(p&1)  
         return (a^p)+solve(a,p-1);  
     else  
         return ((a^(p>>1))+E)*solve(a,p>>1);  
}  


int main()
{
	int testcase;
	cin>>testcase;
	Mat at,bt;
	int res;
	int kp;
	while(testcase--)
	{	
		res=0;
		initE();
		memset(at.mat,0,sizeof(at.mat));
		memset(bt.mat,0,sizeof(bt.mat));
		cin>>n>>kp;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>at.mat[i][j];
			}
		}
		
		bt=at^kp;
		
		for(int i=0;i<n;i++)
		{
			res+=bt.mat[i][i];
		}
		cout<<res%9973<<endl;
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/mig_davidli/article/details/8601453


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。