Aceasta se datoreaza periodicitatii. In plus, cel de-al doilea termen provine din faptul ca daca am o pereche de chei confundabile in $P$, fiecare dintre ele formeaza o pereche (in plus fata de cea explicata mai sus) - cu corespondentul modulo $K$ al perechii sale initiale - pentru fiecare din cele $T$ aparitii disjuncte ale lui $P$ in $S$. Alte perechi nu mai sunt care sa _merite_ numarate, deci formula e corecta. Ramane de vazut cum o vom folosi.

Merita sa analizam cum depinde $A$ de felul in care arata $P$. Cand vom folosi termenul de _rotatie_ a unui sir, ne vom referi la rotatii circulare, adica aplicarea succesiva a mutarii primului element din sir la capatul sau. Stim ca $P$ e neperiodic (un sir e neperiodic atunci cand perioada sa minima e chiar el insusi) (altfel, am fi gasit o perioada mai scurta, contrazicand minimalitatea lui $P$), deci pentru a avea macar o pereche de chei confundabile, singura varianta e sa putem roti sirul in asa fel incat %{color:red}sa contina un palindrom de marime cel putin $K - 1$%. Orice astfel de sir +se poate roti+ in asa fel incat sa respecte unul din cele 3 cazuri:

Merita sa analizam cum depinde $A$ de felul in care arata $P$. Cand vom folosi termenul de _rotatie_ a unui sir, ne vom referi la rotatii circulare, adica aplicarea succesiva a mutarii primului element din sir la capatul sau. Stim ca $P$ e neperiodic (un sir e neperiodic atunci cand perioada sa minima e chiar el insusi) (altfel, am fi gasit o perioada mai scurta, contrazicand minimalitatea lui $P$), deci pentru a avea macar o pereche de chei confundabile, singura varianta e sa putem roti sirul in asa fel incat %{color:red}sa contina un palindrom de marime cel putin $K - 1$%. Orice astfel de sir +se poate roti+ in asa fel incat sa respecte unul din cele 4 cazuri:

|_. indicele categoriei |_. relatii intre valorile sirului <tex> P_0 \ldots P_{K - 1} </tex> |_. conditii impuse asupra lui <tex> K </tex> |_. valoarea lui $A$ in general |_. exemple de <tex> P </tex> |_. valoarea lui $A$ in exemplu |
| <tex> \Lambda </tex> | <tex> P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \} </tex> | <tex> K </tex> impar | $A =$ <tex> \frac{K - 1}{2} </tex> | %{color:red}x%{%{color:blue}abc%}{%{color:green}cba%}, %{color:red}x%{%{color:blue}aba%}{%{color:green}aba%} | $3$ |

| <tex> \Omega </tex> | <tex> P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \}, P_0 \neq P_{\frac{K}{2}} </tex> | <tex> K </tex> par | $A =$ <tex> \frac{K}{2} - 1 </tex> | %{color:red}b%{%{color:blue}abc%}{%{color:red}a%}{%{color:green}cba%} = %{color:red}a%{%{color:blue}cba%}{%{color:red}b%}{%{color:green}abc%}, %{color:red}x%{%{color:blue}abc%}{%{color:red}y%}{%{color:green}cba%} | $3$ |
| <tex> \Gamma </tex> | <tex> P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \}, P_0 = P_{\frac{K}{2}} </tex> | <tex> K </tex> par | $A =$ <tex> \frac{K}{2} </tex> | %{color:red}x%{%{color:blue}abc%}{%{color:red}x%}{%{color:green}cba%}, %{color:red}x%{%{color:blue}abx%}{%{color:red}x%}{%{color:green}xba%} | $4$ |

| <tex> \Omega </tex> | <tex> P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \} </tex> | <tex> K </tex> par | $A =$ <tex> \frac{K}{2} - 1 </tex> | %{color:red}b%{%{color:blue}abc%}{%{color:red}a%}{%{color:green}cba%} = %{color:red}a%{%{color:blue}cba%}{%{color:red}b%}{%{color:green}abc%}, %{color:red}x%{%{color:blue}abc%}{%{color:red}y%}{%{color:green}cba%}, %{color:red}x%{%{color:blue}abc%}{%{color:red}x%}{%{color:green}cba%}, %{color:red}x%{%{color:blue}abx%}{%{color:red}x%}{%{color:green}xba%} | $3$ |
| <tex> \Gamma </tex> | <tex> P_i = P_{K - i - 1}, \forall i \in \{ 0, 1, \ldots, K - 1 \} </tex> | <tex> K </tex> par | $A =$ <tex> \frac{K}{2} </tex> | %{color:blue}abcd%{%{color:green}dcba%} | $4$ |
| <tex> \Xi </tex> | <tex> non \Lambda, non \Omega, non \Gamma </tex> | - | $0$ | abcdef | $0$ |
 

Sirul *neperiodic* $P$ trebuie doar sa respecte relatiile date, pentru macar o rotatie de-a sa, pentru a se incadra definitiv intr-una din categorii. E clar ca orice sir face parte din cel mult o categorie. Din fericire, periodicitatea si rotirea sunt probleme foarte asemanatoare cand vine vorba de numarare de siruri, dupa cum vom vedea.

O observatie pe care o putem face de pe acum, care ne va ajuta mai incolo, e sa vedem ca de vreme ce $A$ e aproximativ <tex> \frac{K}{2} </tex>, deci din formula care leaga $A, K$ si $T$ de $n$, deducem ca $-T * (K + 1) &le; n - T^2^ * (K + 1) &le; 0$

O observatie pe care o putem face de pe acum, care ne va ajuta mai incolo, e sa vedem ca de vreme ce $A$ e aproximativ <tex> \frac{K}{2} </tex> (cu exceptia ultimei categorii), deci din formula care leaga $A, K$ si $T$ de $n$, deducem ca $-T * (K + 1) &le; n - T^2^ * (K + 1) &le; 0$

_Nota._ Acum deja va puteti raspunde la intrebarea, in caz ca v-a trecut asa ceva prin minte, cum se pot face teste ne-banale la problema chei? Folosindu-ne de aceste observatii, putem sa ne asiguram ca o solutie care ia puncte, le ia pe deplin pe merit: palindroame lungi, scurte, din toate cele 3 categorii (desigur, separat), rotite si concatenate prezinta suficient material pentru un set teste decisiv. Poate nu e asa interesant la prima vedere, dar acest aspect a stat la bazele cercetarilor care au dat nastere acestei probleme.

Sa notam cu <tex> \alpha(k) </tex>, <tex> \beta(k) </tex> si <tex> \gamma(k) </tex> numarul de siruri neperiodice de $k$ caractere dintr-un alfabet de marime <tex> \Sigma </tex>, pentru care (sa existe o rotatie in asa fel incat) sirul sa se incadreze in categoria <tex> \Lambda </tex>, <tex> \Omega </tex>, respectiv <tex> \Gamma </tex>. De exemplu, sirul %{color:blue}bc%{%{color:red}y%}{%{color:green}cba%}{%{color:red}x%}{%{color:blue}a%} este numarat in <tex> \beta(n) </tex>. Pentru simplitatea explicatiei, si pentru a evidentia carcterul general al calculelor, vom nota cu <tex> \Theta, \chi </tex> pentru a ne referi la oricare dintre <tex> \Lambda, \alpha </tex>, <tex> \Omega, \beta </tex>, respectiv <tex> \Gamma, \gamma</tex>. Numim _sir canonic_ orice sir neperiodic care nu are nevoie de nicio rotatie circulara pentru a respecta conditiile din categoria sa. Cu ocazia aceasta, *impunem categoriilor* <tex> \Omega </tex> *si* <tex> \Gamma </tex> *ca sirul canonic corespunzator sa respecte conditia ca* <tex> P_0 \ldots P_{\frac{k}{2} - 1} < P_{\frac{k}{2}} \ldots P_{k - 1} </tex> *, din punct de vedere lexicografic* (Tinem a nota ca cele ce urmeaza vor fi mult mai clare, mai usor de dedus si de inteles pentru cei care vor analiza niste exemple contextual generice de siruri de marimi $20$, respectiv $21$.)
 
Atunci cand ne propunem sa calculam <tex> \chi(k) </tex>, impunem constrangerile impuse de categoria <tex> \Chi </tex> si vedem cum putem numara sirurile respective. Mai intai, sa observam ca orice sir canonic se poate roti circular de $k$ ori, obtinand de fiecare data un alt sir. Intr-adevar, daca ar fi 2 siruri identice printre aceste $k$ rotatii, sirul nu ar avea cum sa fie neperiodic. Dintre acestea $k$, doar el este canonic. Aceasta pentru ca sunt cel mult doua pozitii care sa fie centrul unui palindrom circular de marime cel putin $k - 1$, iar dintre ele deja am ales ca pozitie canonica pe exact una: pentru $k$ impar, singura pozitie candidat e <tex> 0 </tex>; pentru $k$ par, pozitiile <tex> 0 </tex> si <tex> \frac{k}{2} </tex> sunt ambele corecte, doar ca am ales exact una dintre ele prin compararea lexicografica, care nu poate rezulta in egalitate, intrucat sirul este neperiodic.

 Numim _sir canonic_ orice sir neperiodic care nu are nevoie de nicio rotatie circulara pentru a respecta conditiile din categoria sa. Sa notam cu <tex> \alpha(k) </tex>, <tex> \beta(k) </tex>, <tex> \gamma(k) </tex> si <tex> \xi(k) </tex> numarul de siruri canonice, neperiodice de $k$ caractere dintr-un alfabet de marime <tex> \Sigma </tex>, pentru care sirul sa se incadreze in categoria <tex> \Lambda </tex>, <tex> \Omega </tex>, <tex> \Gamma </tex>, respectiv <tex> \Xi </tex>. De exemplu, sirul %{color:blue}bc%{%{color:red}y%}{%{color:green}cba%}{%{color:red}x%}{%{color:blue}a%} este numarat in <tex> \frac{k}{2} \beta(n) </tex> prin faptul ca %{color:red}x%{%{color:blue}abc%}{%{color:red}y%}{%{color:green}cba%} e numarat in <tex> \beta(n) </tex>. Pentru simplitatea explicatiei, si pentru a evidentia carcterul general al calculelor, vom nota cu <tex> \Theta, \chi </tex> pentru a ne referi la oricare dintre <tex> \Lambda, \alpha </tex>, <tex> \Omega, \beta </tex>, <tex> \Gamma, \gamma </tex>, respectiv <tex> \Xi, \xi </tex>. (Tinem a nota ca cele ce urmeaza vor fi mult mai clare, mai usor de dedus si de inteles pentru cei care vor analiza niste exemple contextual generice de siruri de marimi $20$, respectiv $21$.)

Dar toate acestea nu inseamna decat ca e suficient sa gasim numarul de siruri canonice, pe care apoi sa il inmultim cu numarul $k$, pentru a afla <tex> \chi(k) </tex>. Putem pleca de la ideea ca orice sir care respecta conditiile din tabel este canonic, daca in plus respecta si conditia pe care am impus-o pentru $k$ par (care nu face decat sa injumatateasca factorul de $k$, fapt pentru care vom da o demonstratie alternativa), cu exceptia acelor siruri care le respecta pe toate acesea, doar ca sunt periodice. Deci tot ce ne ramane de facut e sa scadem din numarul total atatea siruri care au, pe deasupra, perioada minima de lungime $d$, unde $d$ este un divizor al lui $k$, pentru fiecare astfel de divizor.

Atunci cand ne propunem sa calculam <tex> \chi(k) </tex>, impunem constrangerile impuse de categoria <tex> \Chi </tex> si vedem cum putem numara sirurile respective. Mai intai, sa observam ca orice sir canonic se poate roti circular de <tex> \varkappa = \{ \Labmda : k, \Omega, \Gamma : \frac{k}{2}, \Xi : 1 \} </tex> ori, obtinand de fiecare data un alt sir. Intr-adevar, daca ar fi 2 siruri identice printre aceste rotatii, sirul nu ar avea cum sa fie neperiodic. Dintre acestea, doar el este canonic. Aceasta pentru ca sunt cel mult doua pozitii care sa fie centrul unui palindrom circular de marime cel putin $k - 1$, iar dintre ele deja am ales ca pozitie canonica pe exact una: pentru $k$ impar, singura pozitie candidat e <tex> 0 </tex>; pentru $k$ par, pozitiile <tex> 0 </tex> si <tex> \frac{k}{2} </tex> sunt ambele corecte.

Daca notam cu <tex> \Upsilon_{\Theta}(k) </tex> numarul de siruri periodice si neperiodice de marime $k$ care respecta relatiile din categoria <tex> \Theta </tex>, daca eventual le-am supune unei rotatii, vedem ca:

Dar toate acestea nu inseamna decat ca e suficient sa gasim numarul de siruri canonice, <tex> \chi(k) </tex>, pe care apoi sa il inmultim cu numarul corespunzator <tex> \varkappa </tex>, pentru a afla numarul total de siruri din categoria respectiva. Putem pleca de la ideea ca orice sir care respecta conditiile din tabel este canonic, doar ca trebuie sa fie, in plus, periodic. Deci tot ce ne ramane de facut e sa scadem din numarul total atatea siruri care au, pe deasupra, perioada minima de lungime $d$, unde $d$ este un divizor al lui $k$, pentru fiecare astfel de divizor.

* <tex> \Upsilon_{\Lambda}(k) = k \Sigma^{\frac{k + 1}{2}} </tex>
* <tex> \Upsilon_{\Omega}(k) = \frac{k}{2} \Sigma^{\frac{k}{2}} (\Sigma - 1)</tex>
* <tex> \Upsilon_{\Gamma}(k) = \frac{k}{2} \Sigma^{\frac{k}{2}} </tex>

Daca notam cu <tex> \Upsilon_{\Theta}(k) </tex> numarul de siruri canonice periodice si neperiodice de marime $k$ care respecta relatiile din categoria <tex> \Theta </tex>, daca eventual le-am supune unei rotatii, vedem ca:

Mica, dar folositoare, _digresiune_. O alta modalitate de a intelege de ce impartim la $2$ in cazul in care $k$ e par, e urmatoarea: In loc sa numim sir canonic doar unul din cele 2 posibile, le putem considera pe amandoua. Totul ramane neschimbat, doar ca acum fiecare sir canonic are o gama de <tex> \frac{k}{2} </tex> de rotatii proprii, pentru ca le imparte pe cele $k$ cu perechea sa. In aceasta perspectiva, lucrurile care vor urma s-ar putea sa fie mai clare, pentru ca ar ridica mai putine intrebari. Cu toate acestea, vom reveni si vom folosi denumirea de sir canonic asa cum am stabilit-o mai inainte.

* <tex> \Upsilon_{\Lambda}(k) = \Sigma^{\frac{k + 1}{2}} </tex>
* <tex> \Upsilon_{\Omega}(k) = \Sigma^{\frac{k}{2}} </tex>
* <tex> \Upsilon_{\Gamma}(k) = \Sigma^{\frac{k}{2} + 1} </tex>
* <tex> \Upsilon_{\Xi}(k) = \Sigma^{k} </tex>

Sa investigam ce inseamna ca un sir sa fie periodic, dar, ignorand pentru o clipa restrictia aceasta din definitie, canonic! Pentru $k$ impar, stim ca orice $d$ e, la randul sau, impar. De asemenea, <tex> \frac{k}{d} </tex> e impar. Cu aceste observatii in minte, si suprapunand conditiile ca sirul sa fie atat periodic, cat si de categoria <tex> \Lambda </tex>, putem observa ca e vorba de *exact sirurile numarate* de <tex> \alpha(d) </tex>, concatenate unul dupa altul, pana se obtine marimea $k$! Aceasta inseamna ca e suficient sa scadem <tex> \alpha(d) </tex> din numarul total de solutii, si nu mai trebuie sa ne ingrijoram de sirurile cu perioada $d$!

Pentru $k$ par, povestea se repeta! Atunci cand <tex> \frac{k}{d} </tex> este par, periodicitatea impune ca <tex> P_0 = P_{\frac{K}{2}} </tex>, deci doar <tex> \gamma(k) </tex> e influentata in acest caz, si trebuie sa scadem <tex> \beta(d) + \gamma(d) </tex>, daca $d$ e par, respectiv <tex> \alpha(d) </tex>, daca $d$ e impar. Atunci cand <tex> \frac{k}{d} </tex> e impar: pe de o parte, $d$ e par, iar pe de alta parte, *perioada pastreaza categoria sirului mare*, asa ca e suficient sa scadem <tex> \chi(d) </tex> din <tex> \chi(k) </tex>. In general, observam ca:
 
<tex> \chi(k) = \Upsilon_{\Theta}(k) - \sum_{d = 1, d | k}^{k - 1} \psi(d) </tex>, unde <tex> \psi(d) </tex> e o combinatie de <tex> \chi'(d) </tex>, in functie de <tex> \Theta </tex> si paritatea lui $d$. Daca analizam aceste cazuri, vedem ca se pot scrie mult mai usor, notand cu <tex> \delta(k) </tex> numarul de siruri neperiodice de marime $k$ pentru care una din rotatii face parte din cele 3 categorii:

Pentru $k$ par, povestea se repeta! *Perioada pastreaza categoria sirului mare*, asa ca e suficient sa scadem <tex> \chi(d) </tex> din <tex> \chi(k) </tex>. In general, observam ca:

<tex> \delta(k) = ((\frac{k}{2^{(k + 1) - 2 [\frac{k + 1}{2}]}})) \Sigma^{[\frac{k + 2}{2}]} - \sum_{d = 1, d | k}^{k - 1} \delta(d) </tex>

$(*): $ <tex> \chi(k) = \Upsilon_{\Theta}(k) - \sum_{d = 1, d | k}^{k - 1} \chi(d) </tex>

Pe cat de compact si promitator arata, sa nu uitam de unde am plecat. Noi trebuie sa stim, deoarece valoarea lui $A$ difera in functie de categorii, cate din cele <tex> \delta(k) </tex> siruri, pentru $k$ par, fac parte din <tex> \beta(k) </tex> si cate din <tex> \gamma(k) </tex>. Din fericire, mai avem o supriza, daca ne uitam mai atent la metoda de calcul a primului numar: daca $l$ e puterea (nu exponentul) maxima a lui $2$ care il divide pe $k$, atunci <tex> \beta(k) = \frac{k}{2} \Sigma^{\frac{k}{2}} (\Sigma - 1) - \beta(l)</tex>, unde termenul al doilea este folosit doar daca $l < k$, adica daca $k$ nu e el insusi putere de $2$. Dar <tex> \beta(l) </tex> este putere de $2$, deci atunci cand $k$ nu este putere de $2$, <tex> \beta(k) = (\Sigma - 1)(\frac{k}{2} \Sigma^{\frac{k}{2}} - \frac{l}{2} \Sigma^{\frac{l}{2}}).

Pentru a calcula numarul de siruri din ultima categorie, *de fapt* vom calcula in <tex> \chi(k) </tex> numarul total de siruri neperiodice, iar la final vom scadea cate fac parte din celelalte categorii, si anume: <tex> k \alpha(k) </tex> (daca $k$ e impar) sau <tex> \frac{k}{2} (\beta(k) + \gamma(k)) </tex> (daca $k$ e par)

Pana acum am facut suficiente observatii ca sa putem trece la partea algoritmica a rezolvarii problemei. O prima idee de solutie ar fi sa calculam desigur sirul $s{~i~}$ = restul impartirii lui <tex> \delta(k) </tex> la $MOD$. Acum am putea fixa $K$, si in caz ca e par, am fixa si valoarea lui $A$, am cauta valoarea lui $T$ pentru care ecuatia care il leaga de $n$ sa se respecte si am deduce tot ce avem nevoie din tabelul $s$. In functie de abordarea calculului, solutia va obtine intre $64$ (ar fi un lowerbound pentru orice idee decenta) si $100$ de puncte:

Pana acum am facut suficiente observatii ca sa putem trece la partea algoritmica a rezolvarii problemei. O prima idee de solutie ar fi sa calculam desigur sirul $s{~i~}$ = restul impartirii lui <tex> \delta(k) </tex> la $MOD$. Acum am putea fixa $K$, si in caz ca e par, am fixa si valoarea lui $A$, am cauta valoarea lui $T$ pentru care ecuatia care il leaga de $n$ sa se respecte si am deduce tot ce avem nevoie din tabelul $s$. In functie de abordarea calculului, solutia va obtine intre $20$ (ar fi un lowerbound pentru orice idee decenta) si (aproximativ) $75$ de puncte:

* O metoda bruta ar fi sa calculam sirul $s$ pana la valoarea lui $n$, folosind o metoda patratica de a verifica toti divizorii unui numar. Cautarea lui $T$ se face in cel mai banal fel posibil. Calculul valorilor lui <tex> \Sigma^{h} </tex>, atunci cand sunt cerute, in <tex> O(h) </tex>. _Daca cineva, in timpul unei runde lungi, se incapataneaza sa ajunga cu rationamentul aici si sa nu faca un pas spre a-si optimiza codul, sper ca nu va lua un punctaj mai mare decat il merita..._

* O metoda bruta ar fi sa calculam sirul $s$ pana la valoarea lui $2n + 2$, folosind o metoda patratica de a verifica toti divizorii unui numar. Cautarea lui $T$ se face in cel mai banal fel posibil. Calculul valorilor lui <tex> \Sigma^{h} </tex>, atunci cand sunt cerute, in <tex> O(h) </tex>. _Daca cineva, in timpul unei runde lungi, se incapataneaza sa ajunga cu rationamentul aici si sa nu faca un pas spre a-si optimiza codul, sper ca nu va lua un punctaj mai mare decat il merita..._

* Sunt multe feluri de a imbunatati solutia precedenta: Putem precalcula puterile lui <tex> \Sigma </tex>, il putem cauta pe $T$ in <tex> O(log(n)) </tex> sau in <tex> O(1) </tex>, amortizat sau nu. Putem gasi divizorii unui numar cu un algoritm mai eficient, sau putem chiar folosi ciur pentru a determina valorile din sirul $s$.

* Pasul important catre solutia de $100$ de puncte il constituie observatia ca numarul de numere mai mari ale caror valori in sirul $s$ sunt interesante pentru noi este foarte scazut, si putem folosi memoizare pentru calculul acestora. O observatie care poate fi de folos aici e ca $T$ divide $n$, prin urmare putem incerca divizorii sai, pentru care cautam valori $K, A$ pentru care exista o sansa sa se potriveasca in ecuatie, iar apoi calculam valorile relevante din $s$ pentru a actualiza raspunsul

* Pasul important catre solutia de $100$ de puncte il constituie observatia ca numarul de numere mai mari ale caror valori in sirul $s$ sunt interesante pentru noi este foarte scazut, si putem folosi memoizare pentru calculul acestora. O observatie care poate fi de folos aici e ca $T$ divide $2n$, prin urmare putem incerca divizorii sai, pentru care cautam valori $K, A$ pentru care exista o sansa sa se potriveasca in ecuatie, iar apoi calculam valorile relevante din $s$ pentru a actualiza raspunsul. Pentru un punctaj mai mare, putem calcula prin ciur valorile necesare pana la o anumita valoare, $10.000$ sa zicem, si doar pentru celelalte memoizam.
 
Se cade sa facem un scurt rezumat al aventurii noastre cu aceasta problema. Am facut observatii legate de relatia intre forma sirului de caractere si numarul de perechi de chei care nu pot fi distinse. Am analizat aspecte ale numararii sirurilor neperiodice, sub incidenta proprietatilor care ne intereseaza. Am fost uimiti sa vedem cum toate se leaga, valorile pe care voiam sa le calculam se foloseau, in chip neasteptat, de ele insele, inlesnind drumul de la recurenta la solutie. Mai mult, am fost surprinsi sa vedem cat de mult se simplifica operatiile, ajungand sa retinem intr-un sir de numere tot ce ne-ar putea interesa. Apoi am cautat solutii eficiente de a implementa solutia, folosindu-ne de forma ecuatiei care leaga parametrii de numarul din input. A fost un tur de forta care ne-a trecut prin multe observatii, multe idei ad-hoc, si am ajuns, intr-un final, la un algoritm simplu, eficient, sprijinit pe multimea observatiilor facute, care exploateaza _materie_ relativ redusa si tehnici deloc complicate (valabil si pentru solutia de mai jos).
 
Frumos este ca surprizele pregatite de aceasta problema nu se termina aici. Putem obtine un algoritm si mai eficient, care sa obtina scorul de $100$ de puncte, daca mai facem o observatie. Formula $(*)$ sugereaza ca exista o sansa sa aflam valorea lui <tex> \chi(k) </tex> fara sa fie nevoie sa calculam valorile <tex> \chi(d) </tex>. Sa analizam, mai exact, care este factorul, notat cu $f()$, cu care trebuie adunat <tex> \Upsilon_{\Theta}(d) </tex> la raspuns, pentru fiecare $d$. De exemplu, daca $k = 2 * 3 * 5$ sa zicem, putem vedea ca <tex> f(\Upsilon_{\Theta}(2 * 3 * 5)) = 1 </tex>, <tex> f(\Upsilon_{\Theta}(2 * 3)) = f(\Upsilon_{\Theta}(2 * 5)) = f(\Upsilon_{\Theta}(3 * 5)) = -1 </tex>, <tex> f(\Upsilon_{\Theta}(2)) = f(\Upsilon_{\Theta}(3)) = f(\Upsilon_{\Theta}(5)) = 1 </tex>, respectiv <tex> f(\Upsilon_{\Theta}(1)) = -1 </tex>. Acest fenomen se generalizeaza in felul urmator:
 
* Fie $k = p{~0~}^a{~0~}^ * p{~1~}^a{~1~}^ * ... * p{~r-1~}^a{~r-1~}^$, descompunerea in factori primi a lui $k$
* <tex> f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = (-1)^{\sum a_i - \sum b_i} </tex>, orice $d$ pentru care, oricare ar fi $i$, fie $b{~i~} = a{~i~}$, fie $b{~i~} = a{~i~} - 1$
* <tex> f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = 0 </tex>, orice $d$ pentru care exista $i$ astfel incat $b{~i~} &le; a{~i~} - 2$

Se cade sa facem un scurt rezumat al aventurii noastre cu aceasta problema. Am facut observatii legate de relatia intre forma sirului de caractere si numarul de perechi de chei care nu pot fi distinse. Am analizat aspecte ale numararii sirurilor neperiodice, sub incidenta proprietatilor care ne intereseaza. Am fost uimiti sa vedem cum toate se leaga, valorile pe care voiam sa le calculam se foloseau, in chip neasteptat, de ele insele, inlesnind drumul de la recurenta la solutie. Mai mult, am fost surprinsi sa vedem cat de mult se simplifica operatiile, ajungand sa retinem intr-un sir de numere tot ce ne-ar putea interesa. Apoi am cautat solutii eficiente de a implementa solutia, folosindu-ne de forma ecuatiei care leaga parametrii de numarul din input. A fost un tur de forta care ne-a trecut prin multe observatii, multe idei ad-hoc, si am ajuns, intr-un final, la un algoritm simplu, eficient, sprijinit pe multimea observatiilor facute, care exploateaza _materie_ relativ redusa si tehnici deloc complicate.
 

Aceste observatii contureaza algoritmul pe care il vom implementa. Atunci cand e nevoie sa aflam valoarea lui <tex> \chi(k) </tex>, il descompunem pe $k$ in factori primi si, prin backtracking sau nu, pentru fiecare numar $mask$ intre $0$ si $2^r^ - 1$ vom obtine divizorul pentru care $b{~i~} = a{~i~} - bool(2^i^ `and` mask)$ si vom aduna la rapuns <tex> (-1)^{popcount(mask)} \Upsilon_{\Theta}(d) </tex>. In acest fel, nu mai e nevoie nici de recursivitate, nici de memoizare, nici de ciur, deoarece putem afla pe loc (in urma unei descompuneri in factori primi si a $2^r^$ ridicari la putere in timp logaritmic) valorile cautate.

private

protected