제목 대의: n 단계 방진 A, 계산 S = A ^ 1 + A ^ 2 +.... + A ^ k
(mod m) (k <= 10^9) 우 리 는 행렬 의 빠 른 속도 에 따라 O (n ^ 3 log (k) 의 시간 에 A ^ k 를 계산 할 수 있 지만, 우 리 는 하나하나 계산 해서 더 할 수 는 없다. 그러면 시간 을 초과 할 것 이다.
① 2 분 이라는 방법 은
진 구 소 알고리즘 은 여러 가지 식 으로 계산 하 는 사고 가 비슷 합 니 다. 모두 중복 요 소 를 찾 아 여러 가지 식 으로 계산 하 는 횟수 를 줄 이 는 것 입 니 다. 물론 우 리 는 이 여러 가지 식 이 특수 하기 때문에 진 구 소 알고리즘 보다 더 좋 은 생각 이 있 습 니 다. k 가 짝수 일 때: S (k) = A ^ 1 + A ^ 2 + A ^ 3 + A ^ (k / 2 + 1) + A ^ (k / 2 + k / 2) +... + A ^ (k / 2 + k / 2) + E) = (A ^ (k / 2) + E) (A ^ 1 + A ^ 2 + A ^ 2 + A ^ 3.... + A ^ (k / 2) = (A ^ (k / 2) + E) S (k / 2) k 가 홀수 일 때: S (k) = S (k - 1) * A ^ k 이런 방법 은 너무 깊 은 문제 가 발생 할 수 있 으 므 로 공간 을 차지 하고 스 택 이 넘 치지 않도록 조심해 야 하 며 속도 도 느 린 편 이다.
11217405
AbandonZHANG
3233
Accepted
3532K
704MS
G++
2444B
2013-01-28 20:53:36
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)>>1) #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef long long LL; const int MAX = 30; struct Mat{ int row, col; LL mat[MAX][MAX]; }; //initialize square matrix to unit matrix Mat unit(int n){ Mat A; A.row = A.col = n; memset(A.mat, 0, sizeof(A.mat)); for (int i = 0; i < n; i ++) A.mat[i][i] = 1; return A; } //return T(A) Mat transpose(Mat A){ Mat T; T.row = A.col; T.col = A.row; for (int i = 0; i < A.col; i ++) for (int j = 0; j < A.row; j ++) T.mat[i][j] = A.mat[j][i]; return T; } //return (A+B)%mod Mat add(Mat A, Mat B, int mod){ Mat C = A; for (int i = 0; i < C.row; i ++) for (int j = 0; j < C.col; j ++) C.mat[i][j] = (A.mat[i][j] + B.mat[i][j]) % mod; return C; } //return A*B%mod Mat mul(Mat A, Mat B, int mod){ Mat C; C.row = A.row; C.col = B.col; for (int i = 0; i < A.row; i ++){ for (int j = 0; j < B.col; j ++){ C.mat[i][j] = 0; for (int k = 0; k < A.col; k ++) // ， C.mat[i][j] += A.mat[i][k] * B.mat[k][j]; C.mat[i][j] %= mod; } } return C; }; //return A^n%mod Mat exp_mod(Mat A, int n, int mod){ Mat res = unit(A.row); while(n){ if (n & 1){ res = mul(res, A, mod); } A = mul(A, A, mod); n >>= 1; } return res; } Mat A; int n, k, mod; Mat S(int k){ if (k == 1){ return A; } if (k % 2 == 0){ return mul(add(exp_mod(A, k/2, mod), unit(n), mod), S(k/2), mod); } else{ return add(S(k-1), exp_mod(A, k, mod), mod); } } int main(){ cin >> n >> k >> mod; A.row = A.col = n; for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) cin >> A.mat[i][j]; Mat ans = S(k); for (int i = 0; i < ans.row; i ++){ for (int j = 0; j < ans.col - 1; j ++) cout << ans.mat[i][j] << " "; cout << ans.mat[i][ans.col-1] << endl; } return 0; }
② 선형 변환 (좋 은 방법 이 네요 ~! 상승 자세 ~) 우 리 는 전달, 즉 s (k - 1) 에서 s (k) 로 의 선형 변환 을 고려 합 니 다.우선 1 차원 선형 변환 은 분명히 나 올 수 없습니다. A ^ 1 + A ^ 2 + A ^ 3 +... + A ^ k = d * (A ^ 1 + A ^ 2 + A ^ 3 +... + A ^ (k - 1) ) 분명히 안 돼............................................................................................ ) + A^k A^(k+1) = 0 * ( A^1+A^2+A^3+……+A^(k-1) ) + A * A^k. //이 줄 의 변 화 는 보조 로 서 2 차원 의 선형 변 화 를 보완 하 는 것 이다. 그러면 선형 변환 행렬 B 는 분명히 1, 10, 1 일반 화 는 s (k) 가 있다. 1 1 s(k-1) A^k+1 = 0 1 * A ^ k 즉 P (k) = B ^ (n - 1) * P (1) 이렇게 하면 ① 보다 훨씬 좋아 지고 공간 도 절약 하 며 시간 도 절약 할 수 있다.
11217490
AbandonZHANG
3233
Accepted
1016K
282MS
G++
2962B
2013-01-28 21:25:37
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)>>1) #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef long long LL; const int MAX = 60; struct Mat{ int row, col; LL mat[MAX][MAX]; }; //initialize square matrix to unit matrix Mat unit(int n){ Mat A; A.row = A.col = n; memset(A.mat, 0, sizeof(A.mat)); for (int i = 0; i < n; i ++) A.mat[i][i] = 1; return A; } //return T(A) Mat transpose(Mat A){ Mat T; T.row = A.col; T.col = A.row; for (int i = 0; i < A.col; i ++) for (int j = 0; j < A.row; j ++) T.mat[i][j] = A.mat[j][i]; return T; } //return (A+B)%mod Mat add(Mat A, Mat B, int mod){ Mat C = A; for (int i = 0; i < C.row; i ++) for (int j = 0; j < C.col; j ++) C.mat[i][j] = (A.mat[i][j] + B.mat[i][j]) % mod; return C; } //return A*B%mod Mat mul(Mat A, Mat B, int mod){ Mat C; C.row = A.row; C.col = B.col; for (int i = 0; i < A.row; i ++){ for (int j = 0; j < B.col; j ++){ C.mat[i][j] = 0; for (int k = 0; k < A.col; k ++) // ， C.mat[i][j] += A.mat[i][k] * B.mat[k][j]; C.mat[i][j] %= mod; } } return C; }; //return A^n%mod Mat exp_mod(Mat A, int n, int mod){ Mat res = unit(A.row); while(n){ if (n & 1){ res = mul(res, A, mod); } A = mul(A, A, mod); n >>= 1; } return res; } Mat A; int n, k, mod; int main(){ cin >> n >> k >> mod; A.row = A.col = n; for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) cin >> A.mat[i][j]; Mat res; res.row = 2 * n; res.col = n; for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) res.mat[i][j] = A.mat[i][j]; for (int i = n; i < 2 * n; i ++) for (int j = 0; j < n; j ++) res.mat[i][j] = A.mat[i-n][j]; Mat E = unit(n); Mat B; memset(B.mat, 0, sizeof(B.mat)); B.row = B.col = 2 * n; for (int i = 0; i < n; i ++){ for (int j = 0; j < n; j ++) B.mat[i][j] = E.mat[i][j]; for (int j = n; j < 2 * n; j ++) B.mat[i][j] = A.mat[i][j-n]; } for (int i = n; i < 2 * n; i ++){ for (int j = n; j < 2 * n; j ++) B.mat[i][j] = A.mat[i-n][j-n]; } B = exp_mod(B, k-1, mod); res = mul(B, res, mod); for (int i = 0; i < n; i ++){ for (int j = 0; j < n - 1; j ++) cout << res.mat[i][j] << " "; cout << res.mat[i][n-1] << endl; } return 0; }
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Matrix RGB LED Funduino를 Colorduino에서 사용
Matrix LED가 장착된 ATmega328P 보드 Funduino를 사용해 봅시다.
Funduino는 Colorduino, RGB LED 8x8 Matrix Board with Driver Shield for A...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
