fft2d

Time limit: 1.25s
Memory limit: 256MB
Input: fft2d.in
Output: fft2d.out

Un graf FFT de ordin FF este un graf orientat cu FF niveluri, numerotate de la 00 la F1F - 1. Fiecare nivel este compus din 2F12^{F - 1} noduri, numerotate cu numere de la 00 la 2F112^{F - 1} - 1. Vom folosi notația (h,x)(h, x) pentru a ne referi la nodul cu indicele xx de pe nivelul hh.

Muchiile grafului FFT sunt următoarele:

  1. Toate muchiile orientate de la (h,x)(h, x) la (h+1,x)(h + 1, x);
  2. Toate muchiile orientate de la (h,x)(h, x) la (h+1,x2Fh2)(h + 1, x \oplus 2^{F - h - 2}).

Inițial toate nodurile grafului au fost colorate de Stiuboss cu alb. De supărare, Nustiuboss a selectat TT noduri pe care le-a colorat cu negru. (Vedeți figura)

Intrigat de modificările făcute, Nusdeaici s-a decis să calculeze numărul de perechi (a,b)(a, b) cu proprietatea că există măcar un drum orientat de la nodul (0,a)(0, a) la nodul (F1,b)(F - 1, b) care nu trece prin niciun nod negru.

Date de intrare

Fișierul de intrare fft2d.in va conține pe prima linie două numere naturale FF și TT. Următoarele TT linii vor conține câte o pereche (h,x)(h, x), reprezentând faptul că nodul de pe nivelul hh cu indicele xx este colorat cu negru.

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)(a, b) cu proprietatea că există măcar un drum orientat de la nodul (0,a)(0, a) la nodul (F1,b)(F - 1, b) care nu trece prin niciun nod negru.

Restricții

  • 1F301 ≤ F ≤ 30
  • 1T100 0001 ≤ T ≤ 100 \ 000
  • ABA \oplus B reprezintă operația de sau exclusiv pe biți (xor).
  • ATENȚIE! Muchiile sunt orientate (deși în figură nu sunt reprezentate astfel).
  • “Apam, cum să numim personajul principal?” Răspuns: “Nustiuboss”.
  • Pentru teste în valoare de 1010 puncte, F10F ≤ 10
  • Pentru alte teste în valoare de 1010 puncte, F16F ≤ 16
  • Pentru alte teste în valoare de 3030 puncte, T2 000T ≤ 2 \ 000

Exemplul 1

fft2d.in

3 3
0 2
1 1
2 3

fft2d.out

5

Explicație

Există 55 perechi (a,b)(a, b) cu proprietatea din enunț. Mai exact, acestea sunt: (0,0)(0, 0), (0,1)(0, 1), (0,2)(0, 2), (1,2)(1, 2), (3,2)(3, 2).

Exemplul 2

fft2d.in

4 3
0 1
1 1
2 4

fft2d.out

44 

Explicație

Există 4444 de perechi (a,b)(a, b) cu proprietatea din enunț. Figura de mai sus corespunde acestui exemplu.

Exemplul 3

fft2d.in

15 10
3 12914
8 10479
12 1039
8 13597
11 2633
12 10668
12 6769
11 4443
7 15697
12 13418

fft2d.out

268271648

Explicație

Va trebui să ne credeți pe cuvânt.

Problem info

ID: 272

Editor: liviu

Author:

Source: ONI 2018 Baraj Seniori: Problema 2

Tags:

ONI 2018 Baraj Seniori

Log in or sign up to be able to send submissions!