12-Perm

12perm

==Include(page="template/taskheader" task_id="12perm")==

== include(page="template/taskheader" task_id="12perm") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| 12perm.in | 12perm.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="12perm") ==

==Include(page="template/raw")==
 
12-Perm
 
 
 
Se defineste 12-permutarea A[1],A[2],...,A[N] ca fiind o permutare a numerelor 1,2,...,N astfel incat |A[i]-A[i+1]| pentru i=1,2,..N-1.
 
h2. Cerinta
 
Dandu-se un numar natural N calculati numarul de 12-permutari de lungime N .
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare 12perm.in contine numarul natural N cu semnificatia de mai sus.
 
h2. Date de Iesire
 
In fisierul 12perm.out veti afisa X numarul de 12-permutari de lungime N modulo 1048576
 
h2. Restrictii si precizari
 
. 1 <= N <= 15.000.000
 
. 1048576=2^20
 
. Pentru 70% din teste N <= 5.500.000 .
 
h2. Exemplu
 
 
|12perm.in |12perm.out |
 
|4 |12 |
 
 
 
 
Explicatii
 
Cele 12 12-permutari sunt: 1 2 3 4 , 1 2 4 3 , 1 3 2 4 , 1 3 4 2 , 2 1 3 4 , 2 4 3 1 , 3 1 2 4 , 3 4 2 1 , 4 2 1 3 , 4 2 3 1 , 4 3 1 2 , 4 3 2 1
==Include(page="template/taskfooter" task_id="12perm")==