Permutacions i cicles (2) P64069


Statement
 

pdf   zip

thehtml

Feu un programa que compti quantes permutacions de {1, …, n} hi ha amb exactament k ‍cicles, on 1 ≤ kn.

Per exemple, de les sis permutacions de {1, 2, 3}, n’hi ha:

  • dues amb un cicle, que són: (2, 3, 1) i (3, 1, 2).
  • tres amb dos cicles, que són: (2, 1, 3), (1, 3, 2) i (3, 2, 1).
  • una amb tres cicles, que és: (1, 2, 3).

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i k, tals que 1 ≤ kn ≤ 1000.

Sortida

Per a cada cas, compteu el nombre de permutacions de {1, …, n} amb k cicles. Com que el resultat pot ser molt gran, feu els càlculs mòdul 108 + 7.

Observació

Sigui c el nombre de casos. La solució esperada té cost total O(10002 + c). Es poden obtenir fins a 80 punts si es passen jocs de proves on n ≤ 100, amb una solució de cost O(1003 + c).

Public test cases
  • Input

    3 1
    3 2
    3 3
    4 1
    4 2
    4 3
    4 4
    10 2
    20 10
    100 50
    

    Output

    2
    3
    1
    6
    11
    6
    1
    1026576
    28767655
    68128793
    
  • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++