hipersimetrie

Hipersimetrie

== include(page="template/taskheader" task_id="hipersimetrie") ==

Poveste şi cerinţă...

O *matrice hipersimetrică* este o matrice pătratică definită recursiv astfel:
 
# Matricele de dimensiune $1 x 1$ sunt hipersimetrice.
# O matrice de dimensiune $N x N (N > 1)$ este hipersimetrică, dacă împlineşte simultan următoarele două condiţii:
## Este simetrică vertical, orizontal, faţă de diagonala principală şi faţă de diagonala secundară.
## Submatricele de dimensiuni $N / 2 x N / 2$ (cu $N / 2$ rotunjit în jos) situate în cele patru colţuri ale matricei sunt la rândul lor hipersimetrice.
 
O *matrice binară* este o matrice ale cărei elemente sunt $0$ sau $1$. *Valoarea* unei matrice binare hipersimetrice este numărul în baza 2 cu $N^2^$ biţi obţinut prin concatenarea elementelor din matrice citite pe linii de la stânga la dreapta, de sus în jos.
 
h2. Cerinţă
 
Cunoscând $N$ şi $K$, să se calculeze a $K$-a valoare în ordine crescătoare dintre toate valorile matricelor binare hipersimetrice de dimensiune $N x N$.

h2. Date de intrare

Fişierul de intrare $hipersimetrie.in$ ...

Fişierul de intrare $hipersimetrie.in$ conţine pe prima linie numărul $N$. A doua linie conţine un şir de caractere $0$ sau $1$ reprezentând valoarea lui $K$ în baza 2 (se garantează că primul caracter al şirului este $1$).

h2. Date de ieşire

În fişierul de ieşire $hipersimetrie.out$ ...

În fişierul de ieşire $hipersimetrie.out$ afişaţi a $K$-a valoare în ordine crescătoare dintre toate valorile matricelor binare hipersimetrice de dimensiune $N x N$. Deoarece această valoare poate fi foarte mare, se cere să afişaţi doar restul *modulo $1.000.000.007$* al acesteia.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000.000.000;$
* $1 ≤ K ≤ 2^1.000.000^;$
* Se garantează că pentru valoarea $N$ dată există cel puţin $K$ matrice binare hipersimetrice;
* Pentru teste în valoare de $27$ de puncte se garantează că $N ≤ 1.500$
* Pentru alte teste în valoare de $62$ de puncte se garantează că $N ≤ 1.000.000$
* Pentru alte teste în valoare de $11$ de puncte se garantează că $N ≤ 1.000.000.000$

h2. Exemplu

table(example). |_. hipersimetrie.in |_. hipersimetrie.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. hipersimetrie.in |_. hipersimetrie.out |_. Explicaţii |
| 3
100
| 186
| K = 100{~2~} = 4.
A $4$-a matrice în ordinea crescătoare a valorii este
$0 1 0$
$1 1 1$
$0 1 0$
Valoarea sa este $010111010$ în baza $2$, adică $186$ în baza $10$.
|

== include(page="template/taskfooter" task_id="hipersimetrie") ==