Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Sinulle annetaan kokonaisluvut $H, W, A, B, C, D$.

On annettu ruudukko, jossa on $H$ riviä ja $W$ saraketta. Ylhäältä lukien $i$-nnen rivin ja vasemmalta lukien $j$-nnen sarakkeen ruutua kutsutaan ruuduksi $(i, j)$.

Jokainen ruutu on väritetty joko valkoiseksi tai mustaksi. Ruutu $(i, j)$ on musta jos ja vain jos $A \le i \le B$ ja $C \le j \le D$; muussa tapauksessa se on valkoinen.

Asetat lamppuja joihinkin tämän ruudukon valkoisista ruuduista. Valkoiseen ruutuun $(i, j)$ asetettu lamppu valaisee kaikki valkoiset ruudut, jotka täyttävät molemmat seuraavista ehdoista:

  • Ne ovat samalla rivillä tai samassa sarakkeessa kuin ruutu $(i, j)$.
  • Ruudun $(i, j)$ ja kyseisen ruudun välissä ei ole yhtään mustaa ruutua.

Lamppujen sijoittelua sanotaan kelvolliseksi, jos se täyttää seuraavat kaksi ehtoa:

  • Jokainen valkoinen ruutu on vähintään yhden lampun valaisema.
  • Mikään ruutu, jossa on lamppu, ei ole minkään toisen lampun valaisema.

Etsi kelvollisten lamppujen sijoittelujen lukumäärä modulo $998244353$.

Syöte

Syöte annetaan seuraavassa muodossa:

H W A B C D
  • Kaikki syötteen arvot ovat kokonaislukuja.
  • $1 \le A \le B \le H \le 5 \times 10^5$
  • $1 \le C \le D \le W \le 5 \times 10^5$
  • $(A, B) \ne (1, H)$
  • $(C, D) \ne (1, W)$

Tuloste

Tulosta vastaus.

Esimerkit

Syöte 1

3 3 2 2 2 2

Tuloste 1

7

Syöte 2

2 3 1 1 1 2

Tuloste 2

3

Syöte 3

500000 500000 100000 200000 100000 250000

Tuloste 3

360665510

Huomautus

Ensimmäisessä esimerkissä on täsmälleen $7$ kelvollista lamppujen sijoittelua. Ruudut, joissa on lamppu, sekä lamppujen valaisemat valkoiset ruudut on esitetty kuvissa vihreällä.

problem_16233_1.png

Jotkin sijoittelut eivät täytä ehtoja: vasemmanpuoleisessa tapauksessa on olemassa vähintään yksi valkoinen ruutu, jota mikään lamppu ei valaise; oikeanpuoleisessa tapauksessa on valkoinen ruutu, jossa on lamppu ja jota valaisee toinen lamppu. Molemmat tapaukset ovat epäkelpoja.

problem_16233_2.png

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.