Permutacions i cicles P99557


Statement
 

pdf   zip

thehtml

Donats dos naturals n i k, sigui f(n, k) el nombre de permutacions amb n elements, i les quals contenen exactament k ‍cicles, tots ells de longitud 2 o més. Implementeu una programació dinàmica que calculi f(n, k).

Entrada

L’entrada consisteix en diversos casos, cadascun amb dos naturals n i k. Podeu suposar 2 ≤ n ≤ 1000 i 1 ≤ k ≤ ⌊ n/2 ⌋.

Sortida

Per a cada cas, escriviu f(n, k). Com que aquest nombre pot ser molt gran, useu long long’s i feu els càlculs mòdul 109 + 7.

Pista

Es pot calcular f(n, k) com la suma de només dues “crides recursives”.

Public test cases
  • Input

    2 1
    3 1
    4 1
    4 2
    5 1
    5 2
    20 5
    100 10
    1000 1
    1000 2
    1000 500
    

    Output

    1
    2
    6
    3
    24
    20
    796437723
    673801497
    756641425
    592422688
    164644882
    
  • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++