Una serie Matrix se define de la siguiente manera:
METRO , METRO , METRO ( METRO ) , METRO ( METRO ) 2 , METRO 2 ( METRO ) 3 , METRO 3 ( METRO ) 5 , METRO 5 ( METRO ) 8 . . . . . . . . , donde M es una array cuadrada binaria de tamaño K x K (la Array Binaria es un tipo especial de Array donde cada elemento de la array es 0 o 1) y M T representa la transpuesta de la Array M.
Dados N y K , encuentre el término N de la serie. Requisitos previos: Ejemplos de exponenciación modular :
Input : N = 2, K = 4
M = {
{1, 1},
{0, 1}
}
Output : [ 3 1]
[ 2 1]
Explanation:
The 4th term of the series is M2(MT)3 and the value of M2(MT)3
is {{3, 1}, {2, 1}}.
Input : N = 2, K = 5
M = {
{1, 1},
{0, 1}
}
Output : [7 2]
[3 1]
Explanation:
The 4th term of the series is M3(MT)5 and the value of M3(MT)5
is {{7, 2}, {3, 1}}.
Planteamiento: Se puede observar que las potencias de M T son 0, 1, 1, 2, 3, 5, 8….. para el 1 ° , 2 ° , 3 ° ….. términos respectivamente. Este patrón para las potencias de M T no es más que la serie de Fibonacci. Excepto por el primer término, se puede ver que las potencias de M también tienen el mismo patrón pero, aquí la potencia de M es igual a la potencia de M T para el término anterior. Dado que en K th término M T tiene una potencia de fib K , M tiene la potencia de fib K – 1 . Donde fib i representa el i thnúmero de fibonacci Así, para el K -ésimo término (para K ≠ 1) de la serie se puede calcular como:
Sk = Mfib(k - 1)(MT) fib(K)
Como los valores de Fibonacci aumentan bastante rápido, el número 45 de Fibonacci está cerca de 10 10 . Entonces, la K -ésima potencia no se puede calcular multiplicando repetidamente las arrays K veces. Para hacer esto, podemos calcular eficientemente la K -ésima potencia de la array usando una idea similar a la Exponenciación Modular. Como en Modular Exponentiation, la potencia se divide por 2 en cada paso, aquí también seguimos la misma estrategia de divide y vencerás excepto por el hecho de que aquí no multiplicamos números, sino que aquí se requiere la multiplicación de arrays que se puede hacer en O(N 3 ), donde N es el tamaño de la array cuadrada. El siguiente programa ilustra el enfoque anterior:
CPP
// CPP code to find Kth term of the Matrix Series
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
// This function multiplies two matrices A and B, under modulo mod
// and returns the resultant matrix after multiplication
vector<vector<int> > multiply(vector<vector<int> > A,
vector<vector<int> > B)
{
// n is the size of the matrix
int n = A.size();
// Resultant matrix formded after multiplying matrix A and B
vector<vector<int> > result(n, vector<int>(n, 0));
// Matrix Multiplication
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
result[i][j] = (result[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
}
}
}
return result;
}
// Function to find the Kth power of matrix A of size nXn in O(logK)
// similar to Modular Exponentiation
vector<vector<int> > fastpower(vector<vector<int> > A, int n, ll K)
{
// Base Case
if (K == 1)
return A;
// Recursive Case1: If power is Odd
if (K & 1) {
// power(A, K) = power(A, K/2) * power(A, K/2) * A
// when K is odd, Note than in this implementation
// multiply (power(A, K - 1) * A) as in the case
// the power becomes even in the next recursive call
return multiply(A, fastpower(A, n, K - 1));
}
// power(A, K) = power(A, K/2) * power(A, K/2) if K is even
vector<vector<int> > result = fastpower(A, n, K / 2);
return multiply(result, result);
}
// Returns the transpose of the matrix A
vector<vector<int> > transpose(vector<vector<int> > A)
{
int N = A.size();
vector<vector<int> > transposeMatrix(N, vector<int>(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transposeMatrix[i][j] = A[j][i];
}
}
return transposeMatrix;
}
// Prints the matrix A
void printMatrix(vector<vector<int> > A)
{
int n = A.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << A[i][j] << " ";
}
cout << endl;
}
}
// Return the Kth term of the series where matrix M
// is a boolean matrix of size n X n
void getKthTerm(vector<vector<int> > M, int n, int K)
{
// precompue fibonacci till the Kth term
ll fibonacci[K + 1];
// ith fibonacci number denotes the power of M' in
// the ith term, M' represents the transpose of M
// 1st term has power of M' as 0 thus fib[0] = 1
fibonacci[1] = 0ll;
fibonacci[2] = 1ll;
for (int i = 3; i <= K; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
// stores the transpose of Matrix M
vector<vector<int> > transposeM = transpose(M);
// K = 1 and K = 2, is handled separately
if (K == 1) {
printMatrix(M);
}
else if (K == 2) {
printMatrix(transposeM);
}
else {
vector<vector<int> > MpowerFibKminusOne;
MpowerFibKminusOne = fastpower(M, n, fibonacci[K - 1]);
vector<vector<int> > MTransposePowerFibK;
MTransposePowerFibK = fastpower(transposeM, n, fibonacci[K]);
// kthTerm = (M^fib[K - 1]) * (transposeM ^ fib[K])
vector<vector<int> > kthTerm = multiply(MpowerFibKminusOne,
MTransposePowerFibK);
// Print the Resultant Matrix
printMatrix(kthTerm);
}
}
// Driver Code
int main()
{
int n, K;
n = 2;
K = 4;
vector<vector<int> > M{ { 1, 1 }, { 0, 1 } };
getKthTerm(M, n, K);
// prints the 5th term
K = 5;
getKthTerm(M, n, K);
return 0;
}
Javascript
// JavaScript code to find Kth term of the Matrix Series
let mod = 1000000007;
// This function multiplies two matrices A and B, under modulo mod
// and returns the resultant matrix after multiplication
function multiply(A, B)
{
// n is the size of the matrix
let n = A.length;
// Resultant matrix formded after multiplying matrix A and B
let result = new Array(n);
for(let i = 0; i < n; i++){
result[i] = new Array(n).fill(0);
}
// Matrix Multiplication
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
result[i][j] = (result[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
}
}
}
return result;
}
// Function to find the Kth power of matrix A of size nXn in O(logK)
// similar to Modular Exponentiation
function fastpower(A, n, K)
{
// Base Case
if (K == 1)
return A;
// Recursive Case1: If power is Odd
if (K & 1 != 0) {
// power(A, K) = power(A, K/2) * power(A, K/2) * A
// when K is odd, Note than in this implementation
// multiply (power(A, K - 1) * A) as in the case
// the power becomes even in the next recursive call
return multiply(A, fastpower(A, n, K - 1));
}
// power(A, K) = power(A, K/2) * power(A, K/2) if K is even
let result = fastpower(A, n, Math.floor(K / 2));
return multiply(result, result);
}
// Returns the transpose of the matrix A
function transpose(A)
{
let N = A.length;
let transposeMatrix = new Array(N);
for(let i = 0; i < N; i++){
transposeMatrix[i] = new Array(N).fill(0);
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
transposeMatrix[i][j] = A[j][i];
}
}
return transposeMatrix;
}
// Prints the matrix A
function printMatrix(A)
{
let n = A.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
document.write(A[i][j] + " ");
}
document.write("\n");
}
}
// Return the Kth term of the series where matrix M
// is a boolean matrix of size n X n
function getKthTerm(M, n, K)
{
// precompue fibonacci till the Kth term
let fibonacci = new Array(K+1).fill(0);
// ith fibonacci number denotes the power of M' in
// the ith term, M' represents the transpose of M
// 1st term has power of M' as 0 thus fib[0] = 1
fibonacci[1] = 0;
fibonacci[2] = 1;
for (let i = 3; i <= K; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
// stores the transpose of Matrix M
let transposeM = transpose(M);
// K = 1 and K = 2, is handled separately
if (K == 1) {
printMatrix(M);
}
else if (K == 2) {
printMatrix(transposeM);
}
else {
let MpowerFibKminusOne;
MpowerFibKminusOne = fastpower(M, n, fibonacci[K - 1]);
let MTransposePowerFibK;
MTransposePowerFibK = fastpower(transposeM, n, fibonacci[K]);
// kthTerm = (M^fib[K - 1]) * (transposeM ^ fib[K])
let kthTerm = multiply(MpowerFibKminusOne, MTransposePowerFibK);
// Print the Resultant Matrix
printMatrix(kthTerm);
}
}
// Driver Code
let n, K;
n = 2;
K = 4;
let M = [[1, 1 ], [0, 1]];
getKthTerm(M, n, K);
// prints the 5th term
K = 5;
getKthTerm(M, n, K);
// The code is contributed by Gautam goel (gautamgoel962)
Producción :
3 1 2 1 7 2 3 1
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA