Fişierul intrare/ieşire:pwca.in, pwca.outSursăJunior Challenge 2021
AutorAlexandru Luchianov, Mihai-Cristian PopescuAdăugată dejc2021Comisia •jc2021
Timp execuţie pe test0.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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ă V1 aripioare necondimentate, a doua secvenţă să conţină V2 aripioare condimentate, a treia secvenţă să conţină v3 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 V1, V2, ..., VN 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.inpwca.out
1
3
5
3
2 3 1
4
1
15
30626

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
  • 100 → 000
  • 010 → 000
  • 001 → 000
  • 101 → 100 → 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?