Problem 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×N (N>1) este hipersimetrică, dacă îndeplineș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×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.

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×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×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 ≤ 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 puncte se garantează că N ≤ 1.500
  • Pentru alte teste în valoare de 62 puncte se garantează că N ≤ 1.000.000
  • Pentru alte teste în valoare de 11 puncte N ≤ 1.000.000.000

Exemplu

hipersimetrie.in

3
100

hipersimetrie.out

186

Explicații

\(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.

General info

ID: 13

Upload: liviu

Input: hipersimetrie.in/hipersimetrie.out

Memory limit: 128MB/8MB

Time limit: 1s

Author: Adrian Panaete, Adrian Budău

Source: ONI 2019 XI-XII: Ziua 2, Problema 2

Submissions

Special Submissions