Problema Numere – OJI 2007, Clasa a 11-a

• Dificultate:
• Autor: Ilie Vieru
• Online: InfoArena, PbInfo

Rezumat

Se dau două numere naturale nenule $a$ și $b$ Să se determine numărul de numere naturale cu proprietatea că au $a$ cifre și produsul cifrelor egal cu $b$ Răspunsul va fi calculat modulo $9973$

Soluție

Aceasta este o problemă foarte simplă de programare dinamică. Notăm cu $\mathrm{dp}[n][p]$ numărul de numere de lungime $n$ cu produsul cifrelor $p$ Acesta este egal cu suma valorilor de forma $\mathrm{dp}[n - 1][p \mathbin{/} d]$ unde $d$ este o cifră nenulă divizibilă cu $p$ Cazul de bază este $\mathrm{dp}[0][1] = 1$

Implementarea directă a acestei recurențe nu se va încadra în timp pe toate testele, deoarece calculăm o grămadă de stări inutile. Mai exact, pe noi nu ne interesează decât stările $\mathrm{dp}[n][p]$ cu proprietatea că $p \mid b$ Prin urmare, ar fi util să reținem de la început divizorii lui $b$ într-un vector div și să calculăm doar stările aferente acestor divizori.

Chiar și așa, limita de memorie nu ne va permite să reținem toată matricea dp, așa că va trebui să aplicăm o optimizare de memorie foarte comună în problemele de programare dinamică, și anume să reținem doar două linii din matrice – linia curentă și cea precedentă.

Sursă C++

#include <bits/stdc++.h>
using namespace std;

ifstream fin("numere.in");
ofstream fout("numere.out");

const int MOD = 9973;
inline void add(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }

int main() {
   int a, b; fin >> a >> b;
   vector<int> div, pos(b + 1);
   for (int d = 1; d <= b; d++)
       if (b % d == 0) {
           pos[d] = div.size();
           div.push_back(d);
       }

   vector dp(2, vector<int>(div.size()));
   bool ind = 0;
   dp[0][0] = 1;
   for (int i = 1; i <= a; i++, ind ^= 1)
       for (int j = 0; j < int(div.size()); j++) {
           dp[!ind][j] = 0;
           for (int d = 1; d < 10; d++)
               if (div[j] % d == 0)
                   add(dp[!ind][j], dp[ind][pos[div[j] / d]]);
       }
   fout << dp[ind][div.size() - 1] << '\n';
   return 0;
}

Dacă ai vreo nedumerire cu privire la problema Numere, lasă un comentariu și te voi ajuta