== include(page="template/taskheader" task_id="fft2d") ==
Un graf *FFT* de ordin *F* este un *graf* orientat cu *F* niveluri, numerotate de la *0* la *F - 1*. Fiecare nivel este compus din *2 ^F - 1^* noduri, numerotate cu numere de la *0* la *2 ^ F - 1 ^ - 1*. Vom folosi notaţia *(h, x)* pentru a ne referi la nodul cu indicele *x* de pe nivelul *h*.
Muchiile grafului *FFT* sunt următoarele:
1. Toate muchiile *orientate* de la *(h, x)* la *(h + 1, x)*;
2. Toate muchiile *orientate* de la *(h, x)* la *(h + 1, x xor (2 ^ F - h - 2^))*.
Un graf $FFT$ de ordin $F$ este un $graf$ orientat cu $F$ niveluri, numerotate de la $0$ la $F - 1$. Fiecare nivel este compus din $2^F - 1^$ noduri, numerotate cu numere de la $0$ la $2^F - 1^ - 1$. Vom folosi notaţia $(h, x)$ pentru a ne referi la nodul cu indicele $x$ de pe nivelul $h$.
Muchiile grafului $FFT$ sunt următoarele:
# Toate muchiile $orientate$ de la $(h, x)$ la $(h + 1, x)$;
# Toate muchiile $orientate$ de la $(h, x)$ la $(h + 1, x ^ 2^F - h - 2^)$.
Iniţial toate nodurile grafului au fost colorate de Stiuboss cu alb. De supărare, Nustiuboss a selectat T noduri pe care le-a colorat cu negru. (Vedeţi figura)
!problema/fft2d?pic_fft2d.png!
Intrigat de modificările făcute, Nusdeaici s-a decis să calculeze numărul de perechi *(a, b)* cu proprietatea că există măcar un drum orientat de la nodul *(0, a)* la nodul *(F - 1, b)* care nu trece prin niciun nod negru.
Intrigat de modificările făcute, Nusdeaici s-a decis să calculeze numărul de perechi $(a, b)$ cu proprietatea că există măcar un drum orientat de la nodul $(0, a)$ la nodul $(F - 1, b)$ care nu trece prin niciun nod negru.
h2. Date de intrare
Fişierul de intrare $fft2d.in$ va conţine pe prima linie două numere naturale *F* şi *T*. Următoarele *T* linii vor conţine câte o pereche *(h, x)*, reprezentând faptul că nodul de pe nivelul *h* cu indicele *x* este colorat cu negru.
Fişierul de intrare $fft2d.in$ va conţine pe prima linie două numere naturale $F$ şi $T$. Următoarele $T$ linii vor conţine câte o pereche $(h, x)$, reprezentând faptul că nodul de pe nivelul $h$ cu indicele $x$ este colorat cu negru.
h2. Date de ieşire
Fişierul de ieşire $fft2d.out$ va conţine un singur număr natural reprezentând numărul de perechi *(a, b)* cu proprietatea că există măcar un drum orientat de la nodul *(0, a)* la nodul *(F - 1, b)* care nu trece prin niciun nod negru.
Fişierul de ieşire $fft2d.out$ va conţine un singur număr natural reprezentând numărul de perechi $(a, b)$ cu proprietatea că există măcar un drum orientat de la nodul $(0, a)$ la nodul $(F - 1, b)$ care nu trece prin niciun nod negru.
h2. Restricţii
● *1 ≤ F ≤ 30*
● *1 ≤ T ≤ 100 000*
● ATENŢIE! Muchiile sunt orientate (deşi în figură nu sunt reprezentate
astfel).*
● Pentru teste în valoare de 10 puncte, N ≤ 10
● Pentru alte teste în valoare de 10 puncte, N ≤ 16
● Pentru alte teste în valoare de 30 puncte, K ≤ 2000
● “Apam, cum să numim personajul principal?” Răspuns: “Nustiuboss”.
* $1 ≤ F ≤ 30$
* $1 ≤ T ≤ 100 000$
* *ATENŢIE!* Muchiile sunt orientate (deşi în figură nu sunt reprezentate astfel)
* Pentru teste în valoare de $10$ puncte, $F ≤ 10$
* Pentru alte teste în valoare de $10$ puncte, $F ≤ 16$
* Pentru alte teste în valoare de $30$ puncte, $T ≤ 2 000$
* “Apam, cum să numim personajul principal?” Răspuns: “Nustiuboss”.
h2. Exemplu
1 1
2 3
| 5
| Există 5 perechi (a, b) cu proprietatea din enunţ. Mai
exact, acestea sunt: (0, 0), (0, 1), (0, 2), (1, 2), (3, 2).
| Există $5$ perechi $(a, b)$ cu proprietatea din enunţ. Mai
exact, acestea sunt: $(0, 0)$, $(0, 1)$, $(0, 2)$, $(1, 2)$, $(3, 2)$.
|
| 4 3
0 1
1 1
2 4
| 44
| Există 44 de perechi (a, b) cu proprietatea din enunţ.
Figura de pe prima pagină corespunde acestui exemplu.
| Există $44$ de perechi $(a, b)$ cu proprietatea din enunţ.
Figura din enunt corespunde acestui exemplu.
|
| 15 10
3 12914
