Punti fissi

 

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. 1,2,3 (3);
  2. 1,3,2 (1);
  3. 2,1,3 (1);
  4. 2,3,1 (0);
  5. 3,1,2 (0);
  6. 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.

Notice: This work is licensed under a BY-NC-SA. Permalink: Punti fissi

Comments are closed.