Introduction au plus court chemin par congruence

Le plus court chemin par congruence est une technique algorithmique basée sur la théorie des nombres, utilisée pour modéliser des états via des classes de congruence. Elle transforme des problèmes de combinaison linéaire en graphes où les nœuds représentent des restes modulo un entier donné, et les arêtes représentent des opérations d'ajout. Cette méthode est particulièrement efficace pour résoudre des problèmes tels que :

• Compter le nombre d'entiers pouvant être formés comme combinaison linéaire d'un ensemble de nombres, avec un nombre illimité de termes.
• Trouver la plus grande ou la plus petite valeur ne pouvant pas être obtenue par de telles combinaisons.
• Déterminer le nombre minimal d'opérations pour obtenir un entier congru à une valeur donnée modulo k.

L'idée centrale est de construire un graphe où chaque nœud i (0 ≤ i < m) représente la classe de congruence modulo m. Les transitions s'effectuent en ajoutant les valeurs données, avec un coût correspondant à la valeur ajoutée, et la distance calculée représente la plus petite valeur atteignable pour chaque reste. Cela s'apparente à un algorithme de plus court chemin source unique, typiquement Dijkstra.

Exemple 1 : Problème P3403 (Saut d'étages)

Soit un bâtiment avec des marches de tailles x, y et z. On souhaite compter le nombre d'étages atteignables sans dépasser une hauteur maximale h, en utilisant une combinaison arbitraire de y et z, suivie d'ajouts multiples de x.

Pour tout entier k exprimable comme ay + bz (a, b ≥ 0), sa valeur modulo x est invariante. On peut donc se concentrer sur les plus petites valeurs pour chaque reste modulo x. On construit un graphe avec des nœuds de 0 à x-1, où chaque nœud i a des arêtes vers (i+y) % x avec poids y, et vers (i+z) % x avec poids z. En appliquant Dijkstra depuis le nœud 1 % x (en supposant que l'étage initial est 1), on obtient d[i], la plus petite valeur congrue à i modulo x.

Le nombre total d'étages atteignables est alors la somme sur tous les restes i de ⌊(h - d[i]) / x⌋ + 1, à condition que d[i] ≤ h. Il faut noter un cas particulier : si x = 1, la congruence est triviale, et tous les étages de 1 à h sont atteignables si au moins un des pas y ou z est défini.

Implémentation en C++ (refactorisée)

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAXN = 2e5+10;
ll hauteur, total;
int modulo, pasA, pasB;
priority_queue<pair> file;
int compteur, vers[MAXN], poids[MAXN], suiv[MAXN], debut[MAXN];
int visite[MAXN];
ll dist[MAXN];

void ajouter_arete(int de, int a, int cout) {
    vers[++compteur] = a;
    poids[compteur] = cout;
    suiv[compteur] = debut[de];
    debut[de] = compteur;
}

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1 % modulo] = 1;
    file.push(make_pair(-1, 1 % modulo));
    while (!file.empty()) {
        int noeud = file.top().second;
        file.pop();
        if (visite[noeud]) continue;
        visite[noeud] = 1;
        for (int i = debut[noeud]; i; i = suiv[i]) {
            if (dist[vers[i]] > dist[noeud] + poids[i]) {
                dist[vers[i]] = dist[noeud] + poids[i];
                file.push(make_pair(-dist[vers[i]], vers[i]));
            }
        }
    }
}

int main() {
    scanf("%lld%d%d%d", &hauteur, &modulo, &pasA, &pasB);
    for (int i = 0; i < modulo; i++) {
        ajouter_arete(i, (i + pasA) % modulo, pasA);
        ajouter_arete(i, (i + pasB) % modulo, pasB);
    }
    dijkstra();
    for (int i = 0; i < modulo; i++) {
        if (hauteur >= dist[i] && dist[i] != INF) total += ((hauteur - dist[i]) / modulo + 1);
    }
    printf("%lld", total);
    return 0;
}</pair>

Exemple 2 : Problème P2371 (Équations de Mo Mo)

Considérons un problème similaire où, donnés n entiers positifs, on suohaite compter combien d'entiers dans l'intervalle [l, r] peuvent être exprimés comme une combinaison linéaire non négative de ces entiers. L'approche utilise un des entiers comme base pour la congruence, disons x. On construit un graphe analogue avec des nœuds modulo x, et on applique Dijkstra pour obtenir d[i], la plus petite valeur congrue à i modulo x.

Pour un intervalle [l, r], le nombre de valeurs atteignables est la différence entre les comptes cumulés à r et à l-1. Concrètement, pour chaque reste i, si d[i] ≤ r, on ajoute ⌊(r - d[i]) / x⌋ + 1, et si d[i] ≤ l-1, on soustrait ⌊(l-1 - d[i]) / x⌋ + 1.

Implémentation en C++ (refactorisée)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e6+10;
ll gauche, droite, reponse;
ll dist[MAXN];
int nbEntiers;
int visite[MAXN];
int compteur, vers[MAXN], poids[MAXN], suiv[MAXN], debut[MAXN];
priority_queue<pair> file;

void ajouter_arete(int de, int a, int cout) {
    vers[++compteur] = a;
    poids[compteur] = cout;
    suiv[compteur] = debut[de];
    debut[de] = compteur;
}

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    file.push(make_pair(0, 0));
    while (!file.empty()) {
        int noeud = file.top().second;
        file.pop();
        if (visite[noeud]) continue;
        visite[noeud] = 1;
        for (int i = debut[noeud]; i; i = suiv[i]) {
            if (dist[vers[i]] > dist[noeud] + poids[i]) {
                dist[vers[i]] = dist[noeud] + poids[i];
                file.push(make_pair(-dist[vers[i]], vers[i]));
            }
        }
    }
}

int main() {
    int base, val;
    scanf("%d%lld%lld%d", &nbEntiers, &gauche, &droite, &base);
    for (int j = 1; j < nbEntiers; j++) {
        scanf("%d", &val);
        for (int i = 0; i < base; i++) ajouter_arete(i, (i + val) % base, val);
    }
    dijkstra();
    gauche--;
    for (int i = 0; i < base; i++) {
        if (droite >= dist[i]) reponse += (droite - dist[i]) / base + 1;
        if (gauche >= dist[i]) reponse -= (gauche - dist[i]) / base + 1;
    }
    printf("%lld", reponse);
    return 0;
}</pair>

Attention : dans cet exemple, la taille du tableau pour les distances doit être bien calibrée ; une valeur de 5e6 est souvent adéquate pour éviter les erreurs de mémoire ou de temps.