| Fişierul intrare/ieşire: | permheap.in, permheap.out | Sursă | PreOJI 2017 |
| Autor | Marius Nicoli | Adăugată de |  Marius Nicoli •mariusn01 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Permheap
Numim heap un arbore binar în care fiecare nod are informaţia asociată mai mare decât informaţiile asociate fiecăruia dintre fii săi. Astfel, putem reprezenta un heap printr-un vector în care elementele sunt memorate începând cu poziţia 1 iar fiii nodului de pe poziţia i sunt nodurile de pe poziţiile 2*i şi 2*i+1 (nodurile de pe acelaşi nivel ni le imaginăm aşezate de la stânga la dreapta, în ordine crescătoare a poziţiilor lor). Toate nivelurile arborelui sunt complete (fiecare nod are exact 2 fii), eventual cu excepţia ultimului nivel, care este însă completat din stânga (adică întâi frunzele de pe poziţii mai mici).
Să se determine câte permutări ale mulţimii {1, 2, ... n} au structură de heap.
Date de intrare
Fişierul permheap.in conţine pe prima linie numărul natural n.
Date de ieşire
Fişierul permheap.out conţine pe primul rând un număr natural reprezentând valoarea cerută, modulo 666013.
Restricţii
- 1 ≤ n ≤ 200000
Exemplu
| permheap.in | permheap.out |
|---|---|
| 4 | 3 |
Explicaţie
4 2 3 1, 4 3 1 2, 4 3 2 1
