网站建设服务商 需要什么主机,视频运营管理平台,上海突发新闻,北京专业做网站A为一个方阵#xff0c;则Tr A表示A的迹#xff08;就是主对角线上各项的和#xff09;#xff0c;现要求Tr(A^k)%9973。 Input 数据的第一行是一个T#xff0c;表示有T组数据。 每组数据的第一行有n(2 n 10)和k(2 k 10^9)两个数据。接下来有n行则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 代码 #includecstdio
#includeiostream
#includecstring
#includealgorithm
#includequeue
#includestack
#includeset
#includemap
#includevector
#includecmathconst int maxn 1e55;
const int mod 9973;
typedef long long ll;
using namespace std;
struct mat
{int a[15][15];
};
int n;
mat Mul(mat a,mat b)
{mat ans;memset(ans.a,0,sizeof(ans.a));for(int t0;tn;t){for(int j0;jn;j){for(int k0;kn;k){ans.a[t][j](ans.a[t][j]a.a[t][k]*b.a[k][j])%mod;}}}return ans;
}
mat ans;
ll quickPow(ll x)
{mat res;memset(res.a,0,sizeof(res));for(int t0;tn;t){res.a[t][t]1;}while(x){if(x1){resMul(ans,res);}ansMul(ans,ans);x1;}ll ss0;for(int t0;tn;t){ss(ssres.a[t][t])%mod;}return ss;
}int main()
{int T;cinT;int k;while(T--){cinnk;for(int t0;tn;t){for(int j0;jn;j){scanf(%d,ans.a[t][j]);}}ll squickPow(k);coutsendl;}return 0;
}转载于:https://www.cnblogs.com/Staceyacm/p/10781745.html
