Рубрики

Судо Размещение 2 | Матричная серия

Матричный ряд определяется следующим образом:

M, MT, M(MT), M(MT)2, M2(MT)3, M3(MT)5, M5(MT)8 . . . . . . . .,

where M is a binary square matrix of size K x K (Binary Matrix is a special type of Matrix where each element of the matrix is either 0 or 1) and MTrepresents the transpose of Matrix M.

Учитывая N и K , найдите N- й член ряда.

Пререквизиты: Модульное экспонирование

Примеры:

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}}.

Подходить :
Можно заметить, что степени M T равны 0, 1, 1, 2, 3, 5, 8… .. для 1- го , 2- го , 3- го … .. членов соответственно. Этот паттерн для степеней M T есть не что иное, как ряд Фибоначчи.

За исключением первого слагаемого, можно видеть, что степени M также имеют одинаковую структуру, но здесь мощность M равна мощности M T для предыдущего слагаемого.
Так как в K- ом члене M T имеет степень fib K , M имеет степень fib K — 1 .
Где fib i представляет i- е число Фибоначчи.

Таким образом, для K- го члена (для K ≠ 1) ряда можно рассчитать как:

Sk = Mfib(k - 1)(MT) fib(K) 

Поскольку значения Фибоначчи увеличиваются довольно быстро, 45- е число Фибоначчи близко к 10 10 . Таким образом, K- ю степень нельзя рассчитать путем многократного умножения матриц K раз. Чтобы сделать это, мы можем эффективно рассчитать K- ую степень матрицы, используя идею, аналогичную модульному экспоненцированию.

Как и в модульном экспонировании, мощность делится на 2 на каждом шаге, здесь мы также следуем той же стратегии «Разделяй и властвуй», за исключением того факта, что здесь мы не умножаем числа, вместо этого здесь требуется умножение матриц, что можно сделать в O (N 3 ), где N — размер квадратной матрицы.

Ниже программа иллюстрирует вышеприведенный подход:

// код CPP для поиска K-го члена ряда матриц
#include <bits/stdc++.h>

  
#define ll long long
#define mod 1000000007

  

using namespace std;

  
// Эта функция умножает две матрицы A и B по модулю mod
// и возвращает результирующую матрицу после умножения

vector<vector<int> > multiply(vector<vector<int> > A,

                              vector<vector<int> > B)

{

  

    // n - размер матрицы

    int n = A.size();

  

    // Результирующая матрица формируется после умножения матриц A и B

    vector<vector<int> > result(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++) {

                result[i][j] = (result[i][j] + (A[i][k] * B[k][j]) % mod) % mod;

            }

        }

    }

  

    return result;

}

  
// Функция для нахождения K-й степени матрицы A размера nXn в O (logK)
// аналогично модульному экспонированию

vector<vector<int> > fastpower(vector<vector<int> > A, int n, ll K)

{

    // Базовый вариант

    if (K == 1)

        return A;

  

    // Рекурсивный случай1: если мощность нечетна

    if (K & 1) {

        // мощность (A, K) = мощность (A, K / 2) * мощность (A, K / 2) * A

        // когда K нечетно, обратите внимание, чем в этой реализации

        // умножаем (мощность (A, K - 1) * A) как в случае

        // сила становится даже при следующем рекурсивном вызове

        return multiply(A, fastpower(A, n, K - 1));

    }

  

    // мощность (A, K) = мощность (A, K / 2) * мощность (A, K / 2), если K четное

    vector<vector<int> > result = fastpower(A, n, K / 2);

    return multiply(result, result);

}

  
// Возвращает транспонирование матрицы 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;

}

  
// Печатает матрицу 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;

    }

}

  
// Возвращаем K-й член ряда, где матрица M
// является булевой матрицей размера n X n

void getKthTerm(vector<vector<int> > M, int n, int K)

{

  

    // предварительное вычисление фибоначчи до K-го срока

    ll fibonacci[K + 1];

  

    // i-е число Фибоначчи обозначает степень М 'в

    // i-й член M 'представляет транспонирование M

    // 1-й член имеет степень M ', равную 0, поэтому fib [0] = 1

    fibonacci[1] = 0ll;

    fibonacci[2] = 1ll;

    for (int i = 3; i <= K; i++) {

        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];

    }

  

    // сохраняет транспонирование Matrix M

    vector<vector<int> > transposeM = transpose(M);

  

    // K = 1 и K = 2, обрабатывается отдельно

    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]) * (транспонировать M ^ fib [K])

        vector<vector<int> > kthTerm = multiply(MpowerFibKminusOne,

                                                MTransposePowerFibK);

  

        // Распечатать матрицу результатов

        printMatrix(kthTerm);

    }

}

  
// Код драйвера

int main()

{

  

    int n, K;

    n = 2;

    K = 4;

    vector<vector<int> > M{ { 1, 1 }, { 0, 1 } };

    getKthTerm(M, n, K);

  

    // печатает 5-й член

    K = 5;

    getKthTerm(M, n, K);

  

    return 0;

}
 

Выход :

3 1 
2 1 
7 2 
3 1 

Рекомендуемые посты:

Судо Размещение 2 | Матричная серия

0.00 (0%) 0 votes