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++