== include(page="template/taskheader" task_id="bob") ==
Poveste şi cerinţă...
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:
# Care este numărul maxim de pachete ce pot fi formate?
# 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)?
h2. Date de intrare
Fişierul de intrare $bob.in$ ...
Î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.
h2. Date de ieşire
În fişierul de ieşire $bob.out$ ...
Î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:
# Daca $P = 1$, atunci se va afisa pe o singura linie numărul maxim de pachete valide ce pot fi formate.
# 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$*.
h2. 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.
h2. 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$
h2. Exemplu
h2. Exemple
table(example). |_. bob.in |_. bob.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
| 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
|
h2. 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]$}).
== include(page="template/taskfooter" task_id="bob") ==
