La multiplication matricielle est une technique puissante pour optimiser les récurrences linéaires en programmation dynamique. Cet article explore plusieurs applications, allant des suites classiques aux problèmes de graphes, en mettant l'accent sur l'exponentiation rapide et les adaptations nécessaires.

Suite de Fibonacci avec des Grandes Valeurs

Pour la suite définie par F(n) = F(n-1) + F(n-2) avec des conditions initiales, calculer F(n) mod 1e9+7 pour n ≤ 2^63. L'approche naïve en O(n) est inefficace ; on utilise la multiplication matricielle pour une complexité en O(log n).

La matrice d'état est définie comme un vecteur ligne : S(n) = [F(n), F(n-1)]. La matrice de transition T est telle que S(n+1) = S(n) × T. En résolvant les équations, on obtient :

T = [[1, 1],
     [1, 0]]

La puissance matricielle calcule S(n) = S(2) × T^(n-2). En modifiant les noms de variables et la structure du code :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

struct Matrice {
    ll data[5][5];
    Matrice() { memset(data, 0, sizeof(data)); }
    Matrice operator*(const Matrice& other) const {
        Matrice res;
        for (int i = 1; i <= 2; ++i)
            for (int j = 1; j <= 2; ++j)
                for (int k = 1; k <= 2; ++k)
                    res.data[i][j] = (res.data[i][j] + data[i][k] * other.data[k][j] % MOD) % MOD;
        return res;
    }
};

Matrice puissanceMatricielle(Matrice base, ll exposant) {
    Matrice resultat = base;
    Matrice actuelle = base;
    for (exposant--; exposant; exposant >>= 1, actuelle = actuelle * actuelle)
        if (exposant & 1) resultat = resultat * actuelle;
    return resultat;
}

int main() {
    ll n;
    scanf("%lld", &n);
    if (n <= 2) { printf("1\n"); return 0; }
    Matrice initiale, transition;
    initiale.data[1][1] = 1; initiale.data[1][2] = 1;
    transition.data[1][1] = 1; transition.data[1][2] = 1;
    transition.data[2][1] = 1; transition.data[2][2] = 0;
    Matrice res = puissanceMatricielle(transition, n - 2);
    ll resultat = (initiale.data[1][1] * res.data[1][1] + initiale.data[1][2] * res.data[2][1]) % MOD;
    printf("%lld\n", resultat);
}

Récurrence avec Terme Supplémentaire

Pour une récurrence de la forme a(n) = a(n-1) + a(n-3), on étend la matrice d'état à trois dimensions : S(n) = [a(n), a(n-1), a(n-2)]. La matrice de transition devient :

T = [[1, 1, 0],
     [0, 0, 1],
     [1, 0, 0]]

Le code suit une structure similaire, avec des boucles adaptées pour des matrices 3×3.

Gestion des Termes Constants et des Sommes

Pour les récurrences incluant des constantes, on ajoute une dimension supplémentaire à la matrice d'état. Par exemple, pour f(n) = f(n-1) + f(n-2) + C, on utilise S(n) = [f(n), f(n-1), C]. Pour calculer des sommes cumulatives, on ajoute une composante pour la somme partielle.

Dans un problème où on doit maximiser la somme d'un multiset après des opérations, on applique une stratégie gloutonne et modélise la croissance avec une matrice incluant la somme totale.

Exponentiation Rapide de Matrices par Diviser pour Régner

Pour calculer A + A^2 + ... + A^k, on utilise une approche récursive basée sur la parité de k :

• Si k est pair, S(k) = (I + S(k/2)) × S(k/2)
• Si k est impair, S(k) = A × S(k-1)

Cela réduit la complexité à O(n^3 log k). Le code implémente la multiplication matricielle avec des fonctions surchargées pour l'addition et la multiplication.

Comptage de Chemins dans les Graphes

Pour compter le nombre de chemins de longueur exacte k entre deux nœuds dans un graphe dirigé, on représente le graphe comme une matrice d'adjacence M. La puissance M^k donne le nombre de chemins de longueur k : (M^k)[i][j] est le nombre de chemins de i à j. L'exponentiation rapide de matrices permet de calculer cela efficacement.

Plus Courts Chemins avec Multiplication Matricielle

Pour trouver le plus court chemin passant par exactement k arêtes, on adapte la multiplication matricielle en remplaçant l'addition par la minimisation et la multiplication par l'addition. La matrice d'initialisation est remplie d'une valeur infinie, et on applique l'exponentiation rapide. La discrétisation des nœuds peut être nécessaire pour gérer les indices.

Problèmes Avancés avec Contraintes Temporelles

Dans des problèmes comme la propagation de valeurs dans un graphe avec des contraintes de temps, on combine l'exponentiation rapide avec la décomposition en bits pour gérer des plages de temps importantes. On pré-calcule les matrices pour des puissances de deux, puis on combine les résultats pour chaque requête.

Pour des problèmes avec des événements ponctuels, on segmente le temps entre événements et applique la multiplication matricielle à chaque segment, en ajustant les matrices pour les points d'événement.

Considérations Pratiques

• L'initialisation des matrices doit être adaptée au contexte : pour les plus courts chemins, utiliser une valeur grande ; pour les comptages, utiliser zéro ou l'identité selon le cas.
• Lors de l'exponentiation rapide, la matrice résultat initiale doit être la matrice identité pour la multiplication standard, ou la matrice d'état initiale pour les récurrences.
• La multiplication matricielle diffère de l'algorithme de Floyd-Warshall : dans Floyd, l'ordre des boucles est crucial pour la correction, tandis que la multiplication matricielle est associative et peut être appliquée directement.