Problema Numere – OJI 2007, Clasa a 11-a

Problema Numere – OJI 2007, Clasa a 11-a

Rezumat

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

Soluție

Aceasta este o problemă foarte simplă de programare dinamică. Notăm cu dp[n][p]\mathrm{dp}[n][p] numărul de numere de lungime nn cu produsul cifrelor pp Acesta este egal cu suma valorilor de forma dp[n1][p/d]\mathrm{dp}[n - 1][p \mathbin{/} d] unde dd este o cifră nenulă divizibilă cu pp Cazul de bază este dp[0][1]=1\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 dp[n][p]\mathrm{dp}[n][p] cu proprietatea că pbp \mid b Prin urmare, ar fi util să reținem de la început divizorii lui bb î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++

Problema Numere
#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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii