L'analyse du problème P7118 nous plonge dans un univers où les "Galgame" (représentés par des arbres binaires) sont classés selon leur "attractivité". L'objectif est de déterminer, pour un Galgame donné, combien d'autres Galgame "essentiellement différents" sont considérés comme moins attractifs.

1. Compréhension du Concept d'Attractivité

L'attractivité d'un Galgame est définie par le nombre de Galgame qui le précèdent dans un ordre spécifique. La règle de comparaison entre deux Galgame, G1 et G2, ressemble fortement à une comparaison lexicographique sur leurs structures d'arbres binaires :

1. Comparaison par taille globale : Si le nombre total de scènes (nœuds de l'arbre) diffère, le Galgame avec plus de scènes est jugé plus attractif.
2. Comparaison de la scène A (sous-arbre gauche) : Si les nombres de scènes sont identiques, on compare récursivement leurs scènes A. Le Galgame dont la scène A est plus attractive l'emporte.
3. Comparaison de la scène B (sous-arbre droit) : Si les nombres de scènes sont identiques et que les scènes A sont "essentiellement identiques" (même structure et même attractivité), on compare récursievment leurs scènes B. Le Galgame dont la scène B est plus attractive l'emporte.

Notre tâche est de compter les Galgame G' qui sont "moins attractifs" que notre Galgame cible G. Ces Galgame G' se répartissent en deux catégories principales :

• Catégorie 1 : Les Galgame G' qui possèdent un nombre de scènes inférieur à celui de G.
• Catégorie 2 : Les Galgame G' qui ont le même nombre de scènes que G, mais qui sont jugés moins attractifs selon les règles 2 ou 3.

La solution consiste à calculer la somme des Galgame de ces deux catégories.

2. Catégorie 1 : Comptage des Galgame avec moins de nœuds

Cette partie du problème relève de la combinatoire pure. Un Galgame avec i scènes est un arbre binaire enraciné avec i nœuds. Le nombre d'arbres binaires enracinés "essentiellement différents" (c'est-à-dire de formes distinctes) avec i nœuds est donné par le i-ème nombre de Catalan, noté \(C_i\).

Les Nombres de Catalan

Les nombres de Catalan sont omniprésents en combinatoire et apparaissent dans de nombreux problèmes (séquences de parenthèses bien formées, chemins de Dyck, triangulations de polygones, etc.). Leur formule générale est \(C_n = \frac{1}{n+1}\binom{2n}{n}\), et ils peuvent être calculés récursivement par \(C_0=1, C_{n+1} = \sum_{i=0}^{n}C_i C_{n-i}\). En pratique, pour la programmation, on précalcule souvent les factorielles et leurs inverses modulaires pour calculer les coefficients binomiaux.

Si notre Galgame G possède n scènes, le nombre de Galgame de la première catégorie est la somme des nombres de Catalan pour tous les nombres de nœuds inférieurs à n :

\[ \text{Nombre de Galgame de Catégorie 1} = \sum_{i=0}^{n-1} C_i \] Il est important de noter que le cas de 0 nœuds (l'arbre vide) est inclus, correspondant à \(C_0=1\).

Nous pouvons précalculer tous les nombres de Catalan nécessaires jusqu'à n-1 et en déduire cette somme en temps \(O(n)\).

3. Catégorie 2 : Comptage des Galgame avec un nombre de nœuds identique

C'est la partie la plus complexe du problème. Nous devons trouver combien de Galgame G' ont n nœuds (comme G) mais sont moins attractifs. Nous utilisons une fonction récursive, que nous nommerons compterMoinsAttractifs(noeud_courant, multiplicateur), pour effectuer ce calcul.

Cette fonction calcule le nombre de Galgame qui ont la même taille que le sous-arbre enraciné en noeud_courant, mais qui sont moins attractifs que ce sous-arbre. Le paramètre multiplicateur représente le nombre de façons dont ce sous-problème a pu être atteint depuis la racine de G.

Logique de compterMoinsAttractifs(noeud_o, facteur_contexte) :

Supposons que le sous-arbre en noeud_o ait une taille totale S. Ses enfants gauche (scène A) et droit (scène B) sont enfant_gauche[noeud_o] et enfant_droit[noeud_o], avec des tailles respectives S_A et S_B. Il est évident que \(S = 1 + S_A + S_B\).

1. **Cas 1 : La scène A de G' est plus petite que celle de G.**Nous cherchons un Galgame G' de taille S dont le sous-arbre gauche (G'_A) a i nœuds, où \(0 \le i < S_A\).

   • Pour chaque i, il existe \(C_i\) formes possibles pour G'_A.
   • Le sous-arbre droit (G'_B) doit alors avoir \(S - 1 - i\) nœuds. Il existe \(C_{S-1-i}\) formes possibles pour G'_B.
   • Le nombre de Galgame G' pour un i donné est donc \(C_i \times C_{S-1-i}\).

   Nous sommons ces contributions pour toutes les valeurs de i :

   // Contribution du cas 1 : le sous-arbre gauche de G' est plus petit que celui de G
   long long total_inf = 0;
   for (int i = 0; i < taille_sous_arbre[enfant_gauche[noeud_o]]; ++i) {
       total_inf = (total_inf + catalan[i] * catalan[taille_sous_arbre[noeud_o] - 1 - i]) % MODULO;
   }
   resultat_global = (resultat_global + facteur_contexte * total_inf) % MODULO;
   
   

2. **Cas 2 : La scène A de G' a la même taille que celle de G, mais est intrinsèquement moins attractive.**Ici, G'_A a \(S_A\) nœuds, et G'_B a \(S_B\) nœuds. G'_A est moins attractif que G_A. Le nombre de telles G'_A est exactement ce que compterMoinsAttractifs(enfant_gauche[noeud_o], ...) calcule. Pour chaque tel G'_A, le sous-arbre droit G'_B peut être n'importe quelle des \(C_{S_B}\) formes possibles d'un arbre à \(S_B\) nœuds.

   // Contribution du cas 2 : G'_A a même taille, mais est moins attractif
   if (enfant_gauche[noeud_o] != 0) { // S'il existe un enfant gauche
       long long nouveau_facteur = (facteur_contexte * catalan[taille_sous_arbre[enfant_droit[noeud_o]]]) % MODULO;
       compterMoinsAttractifs(enfant_gauche[noeud_o], nouveau_facteur);
   }
   
   

3. **Cas 3 : La scène A de G' est essentiellement identique à celle de G, mais la scène B de G' est moins attractive.**Dans ce cas, G'_A est identique à G_A (1 seule possibilité). Nous devons alors comparer G'_B et G_B. Le nombre de G'_B moins attractifs que G_B est calculé par compterMoinsAttractifs(enfant_droit[noeud_o], ...).

   // Contribution du cas 3 : G'_A est identique, G'_B est moins attractif
   if (enfant_droit[noeud_o] != 0) { // S'il existe un enfant droit
       compterMoinsAttractifs(enfant_droit[noeud_o], facteur_contexte); // Le facteur_contexte reste inchangé
   }
   
   

4. Optimisation \(O(N^2)\) vers \(O(N \log N)\) : La Fusion Heuristique

L'algorithme de compterMoinsAttractifs décrit ci-dessus peut avoir une complexité en \(O(N^2)\) dans le pire des cas (par exemple, un arbre dégénéré en liste) à cause de la boucle du Cas 1. Cette boucle itère \(S_A\) fois.

L'optimisation réside dans l'utilisation d'une identité des nombres de Catalan :

\[ \sum_{i=0}^{K} C_i \cdot C_{K-i} = C_{K+1} \] Dans notre Cas 1, la somme est \(\sum_{i=0}^{S_A-1} C_i \cdot C_{S-1-i}\). Posons \(K = S-1\). Nous savons que \(\sum_{i=0}^{S-1} C_i \cdot C_{S-1-i} = C_S\). Nous pouvons donc réécrire notre somme comme suit :

\[ \sum_{i=0}^{S_A-1} C_i \cdot C_{S-1-i} = C_S - \sum_{i=S_A}^{S-1} C_i \cdot C_{S-1-i} \] La nouvelle somme \(\sum_{i=S_A}^{S-1} C_i \cdot C_{S-1-i}\) itère \( (S-1) - S_A + 1 = S_B + 1 \) fois.

Nous avons donc deux manières de calculer la somme du Cas 1 :

1. Directement, en itérant \(S_A\) fois.
2. Indirectement, en soustrayant une somme qui itère \(S_B + 1\) fois de \(C_S\).

L'idée de la fusion heuristique est de toujours choisir la méthode qui implique le moins d'itérations. Autrement dit :

• Si \(S_A \le S_B + 1\), on utilise la première méthode (boucle sur \(S_A\)).
• Si \(S_A > S_B + 1\), on utilise la deuxième méthode (boucle sur \(S_B + 1\)).

En choisissant toujours de parcourir le sous-arbre de plus petite taille (ou l'un des deux côtés si la différence est faible), la profondeur effective des appels récursifs pour un nœud donné est bornée par \(O(\log N)\). Cela réduit la complexité totale de l'algorithme à \(O(N \log N)\).

5. Étapes de Résolution Complètes

1. Précalculs : Calculer les factorielles, inverses modulaires, et enfin tous les nombres de Catalan \(C_0, \dots, C_n\) modulo \(998244353\).
2. Calcul de la taille des sous-arbres : Effectuer un parcours en profondeur (DFS) initial pour déterminer la taille de chaque sous-arbre taille_sous_arbre[i].
3. Calcul des Galgame de Catégorie 1 : Sommer les nombres de Catalan de \(C_0\) à \(C_{n-1}\).
4. Calcul des Galgame de Catégorie 2 : Appeler la fonction récursive optimisée compterMoinsAttractifs(racine_de_G, 1).
5. Résultat Final : Additionner les résultats des étapes 3 et 4, en s'assurant que toutes les opérations respectent l'arithmétique modulaire.