dinamica

[•AlexandruValeanu]

Sunt nou in programare dinamica si am o problema la care as avea nevoie de ajutor:

"Coriolan Nepriceputeanu este un intelectual desăvârşit, care are o colecţie impresionantă formată din N cărţi. Fiecare dintre acestea are asociat un cod ISBN format din cel mult 9 cifre. Fiind foarte ataşat de cărţile sale lui Coriolan i-ar plăcea ca acestea să fie ordonate riguros, după anumite reguli, care unor neiniţiaţi le-ar putea părea uşor bizare. Astfel, pe primul raft, pe care încap exact M cărţi, el ar vrea să pună volume având suma codurilor ISBN divizibilă cu 100. Cum însă matematica nu e punctul lui forte, vă roagă pe voi să-l ajutaţi să calculeze numărul de variante de alegere a celor M cărţi conform criteriului impus de el. Fiind vorba de un număr foarte mare, Coriolan preferă să afle restul la împărţirea cu 9001 a acestuia."

[•repp4radu]

Dinamica de care vei avea nevoie va fi de genul acesta dp[ i][j][k] = numarul de moduri in care poti alege i carti din primele j astfel incat suma acestora sa aiba restul k la impartirea cu 100.
Recurentele sunt destul de usor de gasit.

Probabil se poate gasi ceva mai eficient, dar din cauza faptului ca nu ai pus restrictiile problemei, nu stiu daca este necesar.

[•AlexandruValeanu]

Mersi de indicatie

1 ≤ M ≤ N ≤ 1000
0 ≤ Ci ≤ 999999999 pentru 1 ≤ i ≤ N
Ordinea în care sunt placate cărţile pe raft nu contează ; (1,2,4) şi (4,1,2) reprezintă o singură variantă de alegere şi deci nu vor fi numărate separat.