Acum ca să obţinem o complexitate mai bună, ţinând cont şi de numele capitolului, vom încerca să reducem complexitatea loop-ului interior (cel după $k$).

h3. (#problema-2). Problema 2: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)
 
Un număr se numeşte urât dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact 2, 3, 5, 7.
Se dă un şir de N cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele 3^(N-1) variante de a insera semnele generează numerele urâte.
Exemplu: pentru cifrele 123456, expresia 1+234-5+6 = 236 care este număr urât, iar 123+4-56 = 71 nu este număr urât.
 
Soluţie:
Observăm că un număr este urât dacă dă cel puţin o dată restul 0 la împărţirea la numerele 2, 3, 5, 7. O abordare a problemei este parcurgerea tuturor variantelor de inserare şi calcularea celor 4 resturi, verificând dacă cel puţin unul este 0.
Vom folosi aritmetica modulară pentru a obţine o soluţie mai eficientă a problemei. Vom împărţi cele 3^(N-1) variante în clase, fiecare clasă reprezentând toate numerele care dau resturile (r_2, r_3, r_5, r_7) la împărţirea la cele 4 numere. Calculând pentru fiecare clasă numărul de numere generate, rezultatul final va fi suma valorilor calculate pentru toate clasele pentru care cel puţin un rest este egal cu 0. Intuim că putem utiliza clasele de resturi într-o soluţie cu programare dinamică.
Vom utiliza şirul auxiliar V[i][j] reprezentând numărul format prin concatenarea cifrelor de pe poziţiile consecutive i, i+1, ..., j din şirul dat, fără inserarea unor semne între cifre. De exemplu, V[2][4] = 234. Dacă notăm cu C[i][r_2][r_3][r_5][r_7] numărul de variante formate cu primele i cifre pentru care clasa de resturi este (r_2, r_3, r_5, r_7). Observăm că orice astfel de variantă se obţine dintr-o variantă cu j < i cifre după care adăugam + sau - apoi concatenăm restul cifrelor până la i fără semne. Dacă resturile pentru varianta cu j cifre erau (r_2, r_3, r_5, r_7) atunci resturile pentru varianta nouă sunt (r'_2, r'_3, r'_5, r'_7) = ((r_2 +/- V[j+1][i])%2, (r_3 +/- V[j+1][i])%3, (r_5 +/- V[j+1][i])%5, (r_7 +/- V[j+1][i])%7). Atunci numărul total de variante cu i cifre este suma după toate valorile j ale numerelor de variante cu j cifre.
C[i][r'_2][r'_3][r'_5][r'_7] = sum_{j<i} C[j][r_2][r_3][r_5][r_7]
 
== code(cpp)
    pentru i = 1, N execută
        V[i][i] = A[i]
        pentru j = i + 1, N execută
            V[i][j] = V[i][j - 1] + A[i];
        sfârşit pentru;
    sfârşit pentru;
 
    C[0][0][0][0][0] = 1;
    S = 0;
    pentru i = 1, N execută
        pentru r_2 = 0, 1 execută
            pentru r_3 = 0, 2 execută
                pentru r_5 = 0, 4 execută
                    pentru r_7 = 0, 6 execută
                        C[i][r_2][r_3][r_5][r_7] = 0;
                        pentru j = 0, i - 1 execută
                            C[i][r_2][r_3][r_5][r_7] += C[j][(r_2 + 2 - V[j+1][i])%2)][(r_3 + 3 - V[j+1][i])%3)]
                                                                             [(r_5 + 5 - V[j+1][i])%5)][(r_7 + 7 - V[j+1][i])%7)];
                            C[i][r_2][r_3][r_5][r_7] += C[j][(r_2 + V[j+1][i])%2)][(r_3 + V[j+1][i])%3)]
                                                                             [(r_5 + V[j+1][i])%5)][(r_7 + V[j+1][i])%7)];
                        sfârşit pentru;
 
                        dacă i == N şi (r_2 == 0 sau r_3 == 0 sau r_5 == 0 sau r_7 == 0)
                            S += C[i][r_2][r_3][r_5][r_7]
                        sfârşit pentru;
                    sfârşit pentru;
                sfărşit pentru;
            sfârşit pentru;
        sfârşit pentru;
    sfârşit pentru;
    returnează S;
==
O problemă în abordarea precedentă este calcularea matricii V, ale cărei valori devin foarte mari şi ies din precizia tipurilor de date disponibile. O soluţie posibilă este calcularea câte unei matrici de sume modulo R pentru fiecare rest R, adica a 4 matrici V_2, V_3, V_5 si V_7 ale resturilor împărţirii valorilor lui V la cele 4 numere prime. Folosind aritmetica modulară, aceste matrici pot fi calculate direct, fără a calcula V. Altă variantă este utilizarea teoremei chineze a resturilor, prin care un sistem de ecuaţii modulo câteva numere prime între ele poate fi redus la o ecuaţie modulo produsul numerelor date. În cazul nostru, numerele sunt prime, deci putem aplica teorema. Astfel, putem reduce problema resturilor împărţirii la (2, 3, 5, 7) la problema restului împărţirii la 2*3*5*7=210, deci fiecare clasa (r_2, r_3, r_5, r_7) se reduce la un rest R < 210. Modificăm pseudocodul astfel:
== code(cpp)
    pentru i = 1, N execută
        V[i][i] = A[i] % 210
        pentru j = i + 1, N execută
            V[i][j] = (V[i][j - 1] + A[i]) % 210;
        sfârşit pentru;
    sfârşit pentru;
 
    C[0][0] = 1;
    S = 0;
    pentru i = 1, N execută
        pentru r = 0, 209 execută
            C[i][r] = 0;
            pentru j = 0, i - 1 execută
                C[i][r] += C[j][(r + 210 - V[j+1][i]) % 210];
                C[i][r] += C[j][(r + V[j+1][i]) % 210];
            sfârşit pentru;
 
            dacă i == N şi (r % 2 == 0 sau r % 3 == 0 sau r % 5 == 0 sau r % 7 == 0)
                S += C[i][r];
            sfârşit pentru;
        sfârşit pentru;
    sfărşit pentru;
    returnează S;
==

h2. Programare dinamica folosind bitmask