4. Opačné čítanie vzorové riešenie

1
AbbA

6

2
DaL00LaD
bysAsyb

210
98

Pomalé riešenie

Najjednoduchšie riešenie tejto úlohy je vyrobiť si všetky možnosti premazaných substringov, ktoré zodpovedajú zadaniu. Akonáhle máme tieto substringy, tak cez každý prejdeme for cyklom, ktorý sa pozerá na znaky z obidvoch koncov substringu. Ak sa znaky spredu aj zozadu zhodujú, tak substring preskočíme. Ak sa nejaký/é znak/y nezhodoval/i, tak si započítame \(+1\) do možností. Takto prejdeme cez všetky možné substringy a zistíme koľko z nich sa nečíta rovnako spredu aj zozadu.

Rýchle riešenie

Lepší prístup k tejto úlohe je zistiť si celkový možný počet substringov a od neho odčítať počet tých substringov, ktoré sa čítajú rovnako spredu aj zozadu. Celkový počet substringov je \(2^k\), pretože máme dokopy k znakov v stringu a každý z nich bude alebo nebude v substringu. Teraz ešte treba zistiť, čo od toho odčítať.

Existujú dva druhy stringov, ktoré nám vedia prísť na vstupe – párnej a nepárnej dĺžky. Najskôr sa budeme venovať stringom párnej dĺžky. Tie pozostávajú z dvojíc rovnakých znakov na opačných stranách stringu. Keď vymažeme nejaké znaky zo stringu, tiež máme dve možnosti novovzniknutého substringu – bude párnej alebo nepárnej dĺžky. Pozrime sa na všetky substringy párnej dĺžky. Predstavme si, že v strede stringu je zrkadlo. Keďže string sa dá čítať rovnako spredu aj zozadu, tak ľavá a pravá polovica vyzerajú rovnako, len zrkadlovo – DaL0|0LaD. Ak vymažeme znaky tak, že nám stále ostane párny počet znakov v substringu, tak vieme jednoducho zistiť, koľko je takých, ktoré sa čítajú rovnako spredu aj zozadu. Ak vymažeme znak na nultom indexe, tak musíme vymazať aj na poslednom – aL00La; ak na prvom, tak aj predposlednom – DL00LD; … . Takto sa dostaneme ku vzorcu \(2^{k/2}\). Pretože ak vymažeme ktorýkoľvek znak z prvej polovice stringu, tak vymažeme aj jeho dvojicu v druhej polovici. Keďže mažeme dvojice, tak máme “polovičnú” dĺžku stringu – \({k/2}\); a každá dvojica bude alebo nebude v substringu. Berieme do úvahy aj to, že nevymažeme ani jeden znak alebo vymažeme všetky.

Ešte potrebujeme odčítať počet substringov nepárnej dĺžky, ktoré sa čítajú rovnako spredu aj zozadu. Je to jednoduchšie ako sa na prvý pohľad zdá. Majme všetky substringy párnej dĺžky z minulého odseku. Z dvojice znakov, ktorá je v strede vymažeme jeden znak a máme substring nepárnej dĺžky, ktorý sa číta rovnako spredu aj zozadu – napr. aL0La. Na čo však nesmieme zabudnúť je to, že môžeme vymazať pravý alebo ľavý znak, čo sa počíta ako dva rôzne substringy. Takže dokopy máme \(2 \cdot 2^{k/2}\) možnoných substringov nepárnej dĺžky, ktoré sa čítajú rovnako spredu aj zozadu. Čo však nie je úplne pravda. Ako bolo aj predtým povedané, v \({k/2}\) sa ráta za možnosť aj prázdny string. Z prázdneho stringu však nevieme nič odčítať, takže vzorec bude vyzerať takto: \(2 \cdot (2^{k/2} - 1)\). Celkový vzorec na vypočítanie všetkých možných párnych stringov, ktoré sa nedajú prečítať rovnako spredu aj zozadu je \(2^k - 2^{k/2} - 2 \cdot (2^{k/2} -1)\).

Pri stringu nepárnej dĺžky sa správame podobne ako pri párnej dĺžky. Tie tiež pozostávajú z dvojíc rovnakých znakov na opačných stranách stringu, ale majú jeden znak v strede navyše – bysAsyb. Predstavme si, že ten znak v strede navyše tam nie je – byssyb. V takom prípade sme opäť naspäť pri stringu párnej dĺžky a vieme použiť vzorec \(2^k - 2^{k/2} - 2 \cdot (2^{k/2} -1)\). Avšak, od celkového počtu ešte potrebujeme odčítať možnosti, kedy sme znak v strede nevymazali. To je v podstate to isté ako keď vymazávame znaky tak, aby sme mali substringy párnej dĺžky. Budeme vymazávať dvojice rovnakých znakov a vždy necháme stredný znak – ysAsy, bsAsb, bAb, … . Takže od celého vzorca ešte odčítame \(2^{k/2}\), a teda výsledný vzorec pre string nepárnej dĺžky bude vyzerať takto: \(2^k - 2^{k/2} - 2 \cdot (2^{k/2} -1) - 2^{k/2}\).

Samozrejme, nakoniec nesmieme zabudnúť na modulo \(10^9 + 7\) a implementovať to cez rýchle modulovanie.

Časová zložitosť je \(O(n \cdot \log k)\), pretože počet možností vypočítame v čase \(\log k\) a vypočítame ich \(n\)-krát, lebo máme \(n\) otázok. Pamäťová zložitosť je \(O(k)\).

MOD = 1000000007

def moznosti(k):
    if k % 2 == 0:
        return (pow(2, k, MOD) - pow(2, (k//2), MOD) - 2*(pow(2, (k//2), MOD) -1)) % MOD
    else:
        return (pow(2, k, MOD) - pow(2, (k//2), MOD) - 2*(pow(2, (k//2), MOD) -1) - pow(2, (k//2), MOD)) % MOD

n = int(input())
for _ in range(n):
    slovo = input()
    k = len(slovo)
    print(moznosti(k))