Pagini recente » Diferente pentru utilizator/scapry intre reviziile 2 si 1 | Diferente pentru problema/plus2 intre reviziile 10 si 4 | Atasamentele paginii Profil _Andrei__ | Atasamentele paginii Tort | PWCA

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-06-02 18:52:20.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	pwca.in, pwca.out	Sursă	Junior Challenge 2021
Autor	Alexandru Luchianov, Mihai-Cristian Popescu	Adăugată de	Comisia •jc2021
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

PWCA

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.

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₁ aripioare necondimentate, a doua secvenţă să conţină V₂ aripioare condimentate, a treia secvenţă să conţină v₃ aripioare necondimentate etc."

Patronul firmei, renumitul bucătar Gordon Ramsay 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.

Date de intrare

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₁, V₂, ..., V_N reprezentând comanda de aripioare a Doctorului Doofenshmirtz.

Date de ieşire

În fişierul de ieşire pwca.out se va afişa numărul de configuraţii iniţiale căutat, modulo 998244353.

Restricţii

$1 \leq N \leq 10^5$
$1 \leq v_{i} \leq 200$

`Subtask 1 (10 puncte)`

$\sum_{i = 1}^{n} v_i \leq 15$

`Subtask 2 (20 puncte)`

$v_i \leq 15$

`Subtask 3 (30 de puncte)`

$N = 1$

`Subtask 4 (40 de puncte)`

Fără restricţii suplimentare.

Exemplu

pwca.in	pwca.out
1 3	5
3 2 3 1	4

Explicaţie

Exemplul 1

Configuraţia din exemplu o reprezintă şirul de biti 000. Acesta poate fi obţinut din următoarele configuraţii:

000
111 → 000
100 → 000
010 → 000
001 → 000

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta