CSES - Datatähti 2023 loppu - Merkkijonot
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Sinulle on annettu merkkijonoja, joista jokainen koostuu merkeistä a ja b. Monellako tavalla merkkijonot voidaan jakaa kahteen joukkoon XX ja YY niin, että molemmissa joukoissa on yhtä paljon kumpaakin merkkiä?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: merkkijonojen lukumäärä.

Tämän jälkeen tulee nn riviä, joista jokaisella on yksi merkkijono.

Tuloste

Tulosta yksi kokonaisluku: kelvollisten tapojen lukumäärä modulo 109+710^9+7.

Esimerkki 1

Syöte:

5
aba
ba
aab
bba
abbab

Tuloste:

4

Selitys: Mahdolliset jakotavat ovat:

  • X={aba, ba, bba},Y={aab, abbab}X=\{\textrm{aba, ba, bba}\}, Y=\{\textrm{aab, abbab}\}
  • X={aab, abbab},Y={aba, ba, bba}X=\{\textrm{aab, abbab}\}, Y=\{\textrm{aba, ba, bba}\}
  • X={aba, abbab},Y={aab, ba, bba}X=\{\textrm{aba, abbab}\}, Y=\{\textrm{aab, ba, bba}\}
  • X={aab, ba, bba},Y={aba, abbab}X=\{\textrm{aab, ba, bba}\}, Y=\{\textrm{aba, abbab}\}

Esimerkki 2

Syöte:

4
a
a
a
a

Tuloste:

6

Selitys: Jakotapa on aina muotoa X={a, a},Y={a, a}X=\{\textrm{a, a}\}, Y=\{\textrm{a, a}\}. Voidaan valita 66 tavalla, mitkä merkkijonot ovat joukossa XX.

Osatehtävä 1 (15 pistettä)

  • Merkkijonoissa on yhteensä korkeintaan 1616 merkkiä

Osatehtävä 2 (55 pistettä)

  • Merkkijonoissa on yhteensä korkeintaan 100100 merkkiä

Osatehtävä 3 (30 pistettä)

  • Merkkijonoissa on yhteensä korkeintaan 500500 merkkiä