Fişierul intrare/ieşire:hipersimetrie.in, hipersimetrie.outSursăONI 2019, clasele 11-12, ziua 2
AutorAdrian Budau, Adrian PanaeteAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test4 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Hipersimetrie

O matrice hipersimetrică este o matrice pătratică definită recursiv astfel:

  1. Matricele de dimensiune 1 × 1 sunt hipersimetrice.
  2. O matrice de dimensiune N x N (N > 1) este hipersimetrică, dacă împlineşte simultan următoarele două condiţii:
    1. Este simetrică vertical, orizontal, faţă de diagonala principală şi faţă de diagonala secundară.
    2. 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.inhipersimetrie.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?