Les chemins d'Hnitbjorg – Épreuve régionale 2024

Niveau 4 ⋅ Validation weight: 50%

Énoncé

Odin et Baugi veulent prendre d'assaut la montagne Hnitbjorg afin d'obtenir le précieux hydromel placé par le géant Suttungr. Pour cela, ils ont besoin de connaître tous les chemins possibles pour arriver au sommet de la montagne.

La montagne est représentée sous la forme d'un graphe non orienté. Deux sommets seront donnés représentant le pied et le sommet de la montagne. Chaque sommet possède une valeur, sa hauteur dans la montagne.

Le but est de compter le nombre de chemins possibles entre le pied et le sommet de la montagne. Les sommets du chemin doivent contenir des hauteurs strictement croissantes. En effet, ils ne veulent pas faire de détour, et donc ne veulent jamais perdre de la hauteur pour aller au sommet.

Comme il peut y avoir beaucoup de chemins, la valeur à afficher est le nombre de chemins modulo $10^9 + 7$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : nombre sommets, le nombre de sommets du graphe.
  • Sur la ligne suivante, une liste de nombre sommets entiers séparés par des espaces : hauteurs, la hauteur de tous les sommets du graphe.
  • Sur la ligne suivante, un entier : nombre aretes, le nombre d'arêtes du graphe.
  • Sur les lignes suivantes, une liste de nombre aretes éléments : aretes, les arêtes du graphe.
    • Une ligne par élément de la liste : séparés par des espaces, un entier sommet a (le premier sommet de l'arête), et un entier sommet b (le second sommet de l'arête).
  • Sur la ligne suivante, un entier : pied, le pied de la montagne.
  • Sur la ligne suivante, un entier : sommet, le sommet de la montagne.

Sortie

Afficher le nombre de chemins de hauteur strictement croissante, allant du pied au sommet de la montagne, modulo 1,000,000,007

Contraintes

  • $1 \le \text{nombre sommets} \le 1\,000$
  • $1 \le \text{nombre aretes} \le 1\,000$
  • $1 \le \text{hauteurs[i]} \le 1\,000\,000$
  • $1 \le \text{pied}, \text{sommet}, \text{sommet a}, \text{sommet b} \le \text{nombre sommets}$

Contraintes de performance

  • $1 \le \text{nombre sommets} \le 100\,000$
  • $1 \le \text{nombre aretes} \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
10 15 20 12 16 18
7
1 2
1 4
2 3
2 5
3 6
4 5
5 6
1
3
Exemple de sortie
3
Commentaire

Voici le graphe représentant la montagne :

20 - 18
 |   |
15 - 16
 |   |
10 - 12

Voici les trois chemins possibles allant du noeud 10 au noeud 20 :

  • 10 - 15 - 20
  • 10 - 12 - 16 - 18 - 20
  • 10 - 15 - 16 - 18 - 20

La réponse est donc "3".

Exemple d'entrée
3
1 2 3
2
1 2
2 3
1
3
Exemple de sortie
1
Exemple d'entrée
4
1 2 3 4
5
1 2
2 3
3 4
2 4
1 4
1
4
Exemple de sortie
3