| Fişierul intrare/ieşire: | hipersimetrie.in, hipersimetrie.out | Sursă | ONI 2019, clasele 11-12, ziua 2 |
| Autor | Adrian Budau, Adrian Panaete | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 2 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hipersimetrie
O matrice hipersimetrică este o matrice pătratică definită recursiv astfel:
- Matricele de dimensiune 1 × 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 N2 biţi obţinut prin concatenarea elementelor din matrice citite pe linii de la stânga la dreapta, de sus în jos.
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.
Date de intrare
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).
Date de ieşire
Î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.
Restricţii
- 1 ≤ N ≤ 1.000.000.000;
- 1 ≤ K ≤ 21.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
Exemplu
| hipersimetrie.in | hipersimetrie.out | Explicaţii |
|---|---|---|
| 3 100 | 186 | K = 1002 = 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. |
