文章

2

粉丝

60

获赞

0

访问

1.4k

头像
矩阵幂 题解:重载*运算符,模板题(快速幂)
P1384 北京邮电大学
发布于2024年3月15日 17:25
阅读数 564

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> operator*(const vector<vector<int>> &a,const vector<vector<int>> &b) {
	int n = a.size();
	vector<vector<int>> tmp(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				tmp[i][j] += a[i][k] * b[k][j];
			}
		}
	}
	return tmp;
}
	
	
int main () {
	int n,k;
	while (cin>>n>>k) {	
		vector<vector<int>> P(n, vector<int>(n, 0));
		vector<vector<int>> Q(n,vector<int>(n, 0));
		for (int i = 0; i < n; i++) {
			Q[i][i] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin>>P[i][j];
			}
		}
		while (k>0) {
			if (k % 2 == 1) {
				Q = Q * P;
			}
			P = P * P;
			k /= 2;
		}
		for (int i = 0; i < n; i++) {
			 cout<<Q[i][0];
			 for (int j = ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发