poj 3233 매트릭스 곱셈 (블록 매트릭스)

POJ 3233
문제 해결: Sn이 원하는 행렬인 경우
이렇게 해서 이 문제는 매트릭스 멱과 매트릭스 곱셈을 구하고 블록 매트릭스 곱셈은 일반 매트릭스와 같다.
code:

/*
adrui's submission
Language : C++
Result : Accepted
Love : ll
Favorite : Dragon Balls

Standing in the Hall of Fame
*/


#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define M(a, b) memset(a, b, sizeof(a))
#define mid ((l + r) >> 1)
#define ls rt << 1, l, mid
#define rs rt << 1|1, mid + 1, r
#define lowbit(x) (x & (-x))
#define LL long long
#define REP(n) for(int i = 0; i < n; i++)
#define debug 0
#define mod 1000

int n, k, m;

struct Matrix {
	int mat[65][65];														//      ， size  2 
	void init() {															//    
		M(mat, 0);
		for (int i = 0; i < 65; i++)
			mat[i][i] = 1;
	}
	void output(int c) {
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < c; j++)
			{
				printf("%d%s", mat[i][j] % m, j != c - 1 ? " " : "
"); 
			}
		}
	}
};

Matrix operator * (Matrix a, Matrix b) {									//    
	Matrix c;	
	M(c.mat, 0);
		for (int i = 0; i < 2 * n; i++) {
			for (int j = 0; j < 2 * n; j++)
			{
				for (int k = 0; k < 2 * n; k++)
					c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % m;
				c.mat[i][j] %= m;
			}
		}

	return c;
}

Matrix operator + (const Matrix &a, const Matrix &b) {						//    
	Matrix c;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
			{
				c.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % m;
			}
		}
		//c.output();
	return c;
}

Matrix Matrix_fast_mod(Matrix tmp, int b) {									//     
	Matrix res;
	res.init();																//    
	while (b) {
		if (b & 1) res = tmp * res;
		tmp = tmp * tmp;
		b >>= 1;
	}
	return res;
}

int main() {
#if debug
	freopen("in.txt", "r", stdin);
#endif //debug
	
	while (~scanf("%d%d%d", &n, &k, &m)) {
		Matrix ans, b;
		M(b.mat, 0);
		Matrix res;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &res.mat[i][j]);
				res.mat[i][j] %= m;
				b.mat[i][j] = res.mat[i][j];								//b      
				res.mat[i][n + j] = res.mat[i][j];							//ret   Sn     
			}
			b.mat[n + i][i] = b.mat[n + i][n + i] = 1;
		}
		//b.output(2 * n);
		b = Matrix_fast_mod(b, k - 1);										//   
		//b.output(2*n);
		//res.output(2 * n);
		ans = res * b;


		ans.output(n);										//  
	}
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 3233 문제 해결: Sn이 원하는 행렬인 경우 이렇게 해서 이 문제는 매트릭스 멱과 매트릭스 곱셈을 구하고 블록 매트릭스 곱셈은 일반 매트릭스와 같다. code:...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj 3233 매트릭스 곱셈 (블록 매트릭스)

좋은 웹페이지 즐겨찾기