Fişierul intrare/ieşire:substitutii.in, substitutii.outSursăutcn-2021
AutorTudor MuresanAdăugată decypryCiprian Oprisa •cypry
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Substituții circulare cu element maxim

Se consideră elementele 1, 2, \ldots, n şi permutările formate cu ele. Permutarea 1, 2, \ldots, n se numeşte permutare principală. Se numeşte substituţie de grad n operaţia prin care se trece de la permutarea principală la o permutare dată. De exemplu pentru grad 10 avem substituţia:

\left(\begin{matrix} \pmb{1} & 2 & \pmb{3} & \pmb{4} & 5 & \pmb{6} & 7 & 8 & 9 & 10 \\ \pmb{3} & 2 & \pmb{4} & \pmb{6} & 5 & \pmb{1} & 8 & 9 & 10 & 7 \end{matrix}\right) \quad \text{ciclul lui 1} \rightarrow \left(\begin{matrix} \pmb{1} & 3 & 4 & 6 \\ 3 & 4 & \pmb{6} & 1 \end{matrix}\right) \quad \text{6 este maxim}

Notăm cu s(i) elementul permutării care corespunde în permutarea principală elementului i. Pentru exemplul dat s(1)=3, s(2)=2, s(3)=4, etc. Se numeşte substituţie circulară, sau ciclu, o substituţie în care plecând de la elementul i şi aplicând succesiv operaţia s() de p ori se ajunge din nou la elementul i. În exemplul de mai sus elementul 1 are un ciclu de 4 elemente: s(1)=3, s(3)=4, s(4)=6, s(6)=1. La fel elementul 7 are un ciclu de 4 elemente, iar elementele 2 şi 5 au un ciclu de 1 element. În ciclul elementului 1 avem elementul maxim al ciclului egal cu 6. Elementele ciclului 1, 3, 4, 6 din permutarea principală apar în permutarea substituţiei deplasate cu o poziţie la stânga 3, 4, 6, 1. (Pentru substituţia: 1, 6, 3, 4 în permutarea principală ar fi 6, 3, 4, 1 în permutarea substituţiei.)

\text{alt ciclu al lui 1} \rightarrow \left(\begin{matrix} \pmb{1} & 6 & 3 & 4 \ 6 & 3 & 4 & 1 \end{matrix}\right)
sau respectand ordinea in permuarea principala
\left(\begin{matrix} \pmb{1} & 2 & \pmb{3} & \pmb{4} & 5 & \pmb{6} & 7 & 8 & 9 & 10 \ \pmb{6} & 2 & \pmb{4} & \pmb{1} & 5 & \pmb{3} & 8 & 10 & 7 & 9 \end{matrix}\right) \end{matrix}\right)

Scrieţi un program care să calculeze numărul permutărilor distincte într-o substituţie de grad n, pentru care elementul maxim din ciclul elementului 1 este de valoare k, unde 1 \leq k \leq n.

Date de intrare

Fişierul de intrare substitutii.in conţine mai multe exemple de test. Un exemplu are pe o linie doi întregi n şi k separaţi prin spaţiu determinând gradul n al substituţiei şi valoarea k a elementului maxim în ciclul elementului 1. Fişierul se termină cu o linie conţinând un 0.

Date de ieşire

Fişierul de ieşire substitutii.out conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de ':' şi de numărul de permutari distincte, luat modulo 9999991, pentru care valoarea elementului maxim al ciclului lui 1 este cea specificată. 

Restricţii

  • 1 \leq n, k \leq 200

Exemplu

substitutii.insubstitutii.out
2 1
19 16
0
1:1
2:4476041
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?