Comptant permutacions (2) P72123


Statement
 

pdf   zip

html

Considereu totes les permutacions de {1, …, n} ordenades lexicogràficament. És a dir, en ordre alfabètic, si imaginem que un 1 és una a, un 2 és una b, etc. Per exemple, les 3! = 6 permutacions per a n=3 són, en ordre, 123, 132, 213, 231, 312 i 321.

Donades dues permutacions p1 i p2, amb p1 ≤ p2, digueu quantes permutacions p hi ha tals que p1 ≤ p ≤ p2.

Entrada

L’entrada conté diversos casos, cadascun amb una línia amb una n entre 1 i 105, seguida d’una línia amb p1, seguida d’una línia amb p2. Tant p1 com p2 són permutacions de {1, …, n}, i es compleix p1 ≤ p2.

Sortida

Per a cada cas, escriviu el nombre de permutacions entre p1 i p2 mòdul 109 + 7.

Observació

Us recomanem resoldre aquest problema en C++.

Puntuació

  • Cas A:   Casos on n ≤ 18, com l’exemple d’entrada 1.  30% Punts 
  • Cas B:   Resta de casos.  70% Punts 
Public test cases

  • Input

    3
1 3 2
3 1 2
2
2 1
2 1
5
2 5 3 1 4
4 1 5 3 2
18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

    Output

    4
1
34
660911389

  • Input

    20
6 1 7 11 20 16 18 12 14 3 9 5 8 15 13 17 10 19 2 4
10 18 3 16 19 15 20 12 13 11 9 8 6 14 17 1 7 2 5 4
28
17 10 20 6 16 12 7 13 24 23 14 18 21 26 25 19 5 11 27 8 22 3 1 15 9 2 28 4
20 8 9 18 12 5 21 13 22 25 7 6 1 26 24 2 11 19 4 16 14 15 10 3 27 28 17 23

    Output

    446619217
860073471
    • Information
    Author
    Xavier Povill
    Language
    Catalan
    Official solutions
    C++
    User solutions