Una permutazione P[1..n] di dimensione n è una sequenza nella quale ciascun numero intero da 1 a n compare una e una sola volta.
Esempi di permutazioni sono le due sequenze 1,4,3,5,2 (n=5) e 3,2,1 (n=3) mentre la sequenza 1,2,3,5,1 (n=5) non è una permutazione poiché il numero 1 compare due volte.
L’intero j si definisce punto fisso della permutazione P se vale P[j]=j, dove 1 <= j <= n.
Ad esempio, nella permutazione 1,4,3,5,2 ci sono due punti fissi, 1 e 3, mentre la permutazione 5,4,3,2,1 non ha alcun punto fisso.
È interessante stabilire quante permutazioni di dimensione n hanno esattamente k punti fissi.
Per esempio, dato n=3, abbiamo 6 permutazioni, dove tra parentesi indichiamo il rispettivo numero di punti fissi:
- 1,2,3 (3);
- 1,3,2 (1);
- 2,1,3 (1);
- 2,3,1 (0);
- 3,1,2 (0);
- 3,2,1 (1).
In tale situazione, non ci sono permutazioni con k=2 punti fissi; per k=1, ne abbiamo 3, e così via.
Scrivere un programma che, ricevuti due numeri n e k, trova il numero di permutazioni di dimensione n che hanno esattamente kpunti fissi.
Dati di input
Il file input.txt è composto da un’unica riga contenente i due numeri interi n (1 <= n <= 9) e k (0 <= k <= n) separati da uno spazio.
Dati di output
Il file output.txt è composto da una sola riga contenente un intero non negativo, ossia il numero di permutazioni di dimensione n che hanno esattamente k punti fissi.
Esempi
input.txt | output.txt | |
---|---|---|
1 | 5 2 | 20 |
2 | 9 6 | 168 |
3 | 2 1 | 0 |
4 | 9 0 | 133496 |
Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.