!{margin: 10px}>problema/pwca?HotWings.png!
_Agent P., plictisit de algoritmi de cuplaj in O(N) cu rucsac random si de interactive de geometrie, a demisionat de la Organizatia Fara Acronim Cool si s-a apucat de compus Probleme Cu Acronim Cool._
_Agent P., plictisit de interactive de geometrie şi de algoritmi de cuplaj în $O(N)$ cu rucsac random, a demisionat de la Organizaţia Fără Acronim Cool şi s-a apucat de compus Probleme Cu Acronim Cool._
Poveste şi cerinţă...
Doctorul Heinz Doofenshmirtz lucra la un nou inator, când i s-a făcut foame şi s-a gândit să comande prin _FoodPlatypus_ nişte aripioare picante de pui. Aripioarele de pui pot fi de $2$ tipuri: $condimentate$ (codificate prin $1$) sau $necondimentate$ (codificate prin $0$). Comanda sa prin _FoodPlatypus_ are următoarele instrucţiuni:
_"Vreau să primesc un şir de aripioare, împărţit în $N$ secvenţe alternante. Astfel, prima secvenţă să conţină $V{~1~}$ aripioare $necondimentate$, a doua secvenţă să conţină $V{~2~}$ aripioare $condimentate$, a treia secvenţă să conţină $v{~3~}$ aripioare $necondimentate$ etc."_
Patronul firmei, renumitul bucătar 'Gordon Ramsay':problema/gordonramsay are acum un şir de aripioare de pui în faţa lui, unele $condimentate$, altele nu. El defineşte o $subsecvenţă picantă maximală$ ca fiind o subsecvenţă formată din aripioare de acelaşi tip care nu se poate extinde la stânga sau la dreapta. La un pas, el poate schimba tipul unei $subsecvenţe picante maximale$ dacă şi numai dacă aceasta are lângă ea o altă $subsecvenţă picantă maximală$ de lungime mai mare sau egală ca ea. Fiind în secret pasionat de probleme de algoritmică, el se întreabă care este numărul total de configuraţii iniţiale de aripioare pe care le poate avea astfel încât, aplicând operaţia de mai sus de oricâte ori vrea, să poată obţine comanda finală a Doctorului Doofenshmirtz. Fiind însă prea ocupat cu prepararea comenzii şi insultarea angajaţilor, vă întreabă pe voi care este acest număr, *modulo 998244353*.
h2. Date de intrare
Fişierul de intrare $pwca.in$ ...
Fişierul de intrare $pwca.in$ va conţine pe prima linie numărul natural $N$ reprezentând numărul de secvenţe. Următoarea linie va conţine $N$ numere $V{~1~}, V{~2~}, ..., V{~N~}$ reprezentând comanda de aripioare a Doctorului Doofenshmirtz.
h2. Date de ieşire
În fişierul de ieşire $pwca.out$ ...
În fişierul de ieşire $pwca.out$ se va afişa numărul de configuraţii iniţiale căutat, *modulo 998244353*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* <tex>1 \leq N \leq 10^5</tex>
* <tex>1 \leq v_{i} \leq 200</tex>
h2. Exemplu
h3. $Subtask 1 (10 puncte)$
table(example). |_. pwca.in |_. pwca.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* <tex>\sum_{i = 1}^{n} v_i \leq 15 </tex>
h3. $Subtask 2 (20 puncte)$
* <tex>v_i \leq 15 </tex>
h3. $Subtask 3 (30 de puncte)$
h3. Explicaţie
* <tex> N = 1 </tex>
...
h3. $Subtask 4 (40 de puncte)$
* $Fără restricţii suplimentare.$
h2. Exemplu
table(example). |_. pwca.in |_. pwca.out |
| 1
3
| 5 |
| 3
2 3 1
| 4
|
| 1
15
| 30626
|
h2. Explicaţie
h3. Exemplul 1
Configuraţia din exemplu o reprezintă şirul de biti $000$. Acesta poate fi obţinut din următoarele configuraţii:
* $000$
* $100$ → $000$
* $010$ → $000$
* $001$ → $000$
* $101$ → $100$ → $000$
h3. Exemplul 2
Configuraţia din exemplu o reprezintă şirul de biti $001110$. Acesta poate fi obţinut din următoarele configuraţii:
* $001110$
* $101110$ → $001110$
* $001010$ → $001110$
* $101010$ → $001010$ → $001110$
== include(page="template/taskfooter" task_id="pwca") ==
