No ABBA P89531


Statement
 

pdf   zip

Considereu una paraula composta només amb ‘A’ i ‘B’. Algunes posicions tenen el contingut fixat, mentre que d’altres podeu escollir si tenen una ‘A’ o una ‘B’. De quantes maneres podeu triar el contingut de les posicions lliures de forma que la subparaula “ABBA” no hi aparegui?

Entrada

L’entrada consisteix en diverses paraules amb entre 1 i 10510^5 caràcters. Les lletres fixades es marquen amb ‘A’ i ‘B’, mentre que les lletres per triar es marquen amb punts.

Sortida

Per a cada paraula, escriviu el nombre de maneres de completar-la sense que hi aparegui la subparaula “ABBA”. Com que el resultat pot ser molt gros, feu els càlculs mòdul 108+710^8 + 7.

Pista

La solució esperada és una programació dinàmica amb 4n4n estats, on nn és la mida de la paraula donada. Potser aquest autòmat us resultarà útil:

(42,9) (1,5)1.2a(1,5)λ\lambda (11,5)1.2b(11,5)A (21,5)1.5c(21,5)AB (31,5)2.0d(31,5)ABB (41,5)1.2e(41,5)X

Public test cases

  • Input

    .
A..
....
B...
ABBA
A..B.A
A..B.B
.......................
..............................
..B....A....AB....BA.....B..A.

    Output

    2
4
15
8
0
5
7
2109583
66654350
513920
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++