Intercalant paraules P34319


Statement
 

pdf   zip

thehtml

Donades dues paraules s i t, de quantes maneres es poden intercalar tots els seus caràcters respectant l’ordre relatiu dins de cada paraula, i de manera que al resultat final no hi hagi dos caràcters consecutius iguals?

Per exemple, s= “a” i t= “bc” es poden intercalar de tres maneres: “abc”, “bac” i “bca”. Com un altre exemple, s= “ab” i t= “ab” només poden produir “abab”, però de dues maneres diferents (posant abans s, o posant abans t), així que aquí el resultat és 2.

Entrada

L’entrada consisteix en diversos casos, cadascun amb s i t. Podeu suposar que les longituds d’ambdues paraules estan entre 1 i 500. També podeu suposar que les paraules només estan formades per lletres minúscules, encara que la solució esperada, que té cost Θ(| s | · | t |), no ‍fa servir aquest fet.

Sortida

Per a cada cas, escriviu el nombre d’intercalacions possibles. Com que el resultat pot ser molt gran, feu els càlculs mòdul 108 + 7.

Public test cases
  • Input

    a bc
    ab ab
    abc defg
    aaaa bbb
    aaaa bbbb
    aaa b
    qwertyuiopzxcvbnm asdfghjklzxcvbnm
    

    Output

    3
    2
    35
    1
    2
    0
    47646019
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++