Fişierul intrare/ieşire:	bob.in, bob.out	Sursă	OJSEPI 2021, clasele 11-12
Autor	Costin Oncescu	Adăugată de	Matteo Verzotti •Matteoalexandru
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bob

Dezamăgiţi de lipsa fotbalului din ultima perioadă, Ştefan şi Georgian şi-au deschis (în secret) o afacere cu boabe de cafea, comercializând K tipuri diferite de cafea. Astfel, timp de N zile ei produc cafea, urmând să formeze din boabele obţinute în zile consecutive pachete ce conţin toate tipurile de cafea.

Concret, cei doi ştiu pentru fiecare zi ce tipuri de cafea produc în acea zi (posibil niciun tip, caz în care afacerea ia o pauză), după care ei împart zilele în secvenţe continue astfel încât, pentru fiecare tip de cafea, fiecare secvenţă de zile să conţină cel puţin o zi în care să fie produs acel tip de cafea.

Înainte de a se apuca de împachetat boabele, Ştefan şi Georgian îşi pun două întrebări:

1. Care este numărul maxim de pachete ce pot fi formate?
2. Care este numărul de moduri de a împărţi zilele astfel încât să se formeze număr maxim de pachete valide (ce conţin toate tipurile de cafea)?

Date de intrare

În fişierul de intrare bob.in, pe prima linie se găseşte un număr întreg P, reprezentând numărul cerinţei de rezolvat.

Pe cea de-a doua linie se găseşte un număr întreg T, reprezentând numărul de scenarii pentru care va trebui să rezolvaţi problema.

Urmează cele T instanţe ale problemei, fiecare fiind compusă din N + 1 linii: pe prima linie se vor afla două numere întregi N şi K, reprezentând numărul de zile, respectiv numărul de tipuri diferite de cafea; pe următoarele N linii câte K cifre binare, cea de-a j-a cifră de pe linia i fiind 0 dacă în ziua i tipul j de cafea nu este produs, sau fiind 1 dacă în ziua i tipul j de cafea este produs.

Date de ieşire

În fişierul de ieşire bob.out, pentru fiecare dintre cele T instanţe se va afişa răspunsul, începând de la o linie noua, după cum urmeaza:

1. Daca P = 1, atunci se va afisa pe o singura linie numărul maxim de pachete valide ce pot fi formate.
2. Daca P = 2, atunci se va afisa pe o singura linie numărul de moduri de a împărţi zilele în secvenţe continue astfel încât să se formeze număr maxim de pachete. Răspunsul va fi afişat modulo 1 000 000 007.

Restricţii

• 1 ≤ P ≤ 2
• 1 ≤ T ≤ 3
• 1 ≤ N ≤ 200 000
• 1 ≤ K ≤ 20
• Se garantează că fiecare tip de cafea apare în cel puţin una dintre cele N zile.

Punctare

• Pentru 6 puncte: P = 1, N ≤ 15
• Pentru alte 6 puncte: P = 1, N ≤ 100
• Pentru alte 9 puncte: P = 1, N ≤ 2 000
• Pentru alte 10 puncte: P = 1, N ≤ 200 000
• Pentru alte 10 puncte: P = 2, K = 1, N ≤ 200 000
• Pentru alte 4 puncte: P = 2, N ≤ 15
• Pentru alte 4 puncte: P = 2, N ≤ 20
• Pentru alte 9 puncte: P = 2, N ≤ 100
• Pentru alte 8 puncte: P = 2, N ≤ 700
• Pentru alte 8 puncte: P = 2, N ≤ 2 000
• Pentru alte 8 puncte: P = 2, N ≤ 10 000
• Pentru alte 9 puncte: P = 2, N ≤ 70 000
• Pentru alte 9 puncte: P = 2, N ≤ 200 000

Exemple

bob.in	bob.out
1 3 3 3 010 101 111 6 2 10 01 00 10 11 01 5 4 0100 1010 0000 1110 0001	2 2 1
2 3 3 3 010 101 111 6 2 10 01 00 10 11 01 5 4 0100 1010 0000 1110 0001	1 3 1

Explicaţii

În primul exemplu, tipurile de cafea produse în fiecare zi sunt:

• În prima zi se va produce doar tipul 2 de cafea
• În cea de-a doua zi se vor produce tipurile 1 şi 3 de cafea
• În ultima zi se vor produce toate cele 3 tipuri de cafea

Numărul maxim de pachete este 2, şi este obţinut în mod unic, grupând zilele în următorul fel: [1, 2], [3].

În cel de-al doilea exemplu, numărul maxim de pachete este 2, fiind obţinut în urmatoarele 3 moduri:

• [1, 2], [3, 4, 5, 6]
• [1, 2, 3], [4, 5, 6]
• [1, 2, 3, 4], [5, 6]

În cel de-al treilea exemplu, numărul maxim de pachete este 1, fiind obţinut prin gruparea tuturor zilelor într-o singură secvenţă ([1, 2, 3, 4, 5]).

Cum se trimit solutii?