Revizia anterioară Revizia următoare
Solutii
Maxsecv
(clasele 9-10)
...
Chernel
(clasele 9-10)
Considerandu-se sirul a1 a2 ... aN pentru un N fixat, se observa ca dupa N-1 transformari, acesta devine a1 * CN-10 + a2 * CN-11 + a3 * CN-12 + ... + aN * CN-1N-1 . De aici reiese ca elementele sirului initial a calor valoare nu influenteaza numarul caracteristic (numarul din ultimul sir obtinut modulo M) sunt cele ai caror coeficienti sunt multipli ai lui M. Astfel problema se reduce la numararea combinarilor de N-1 luate cate i (cu i intre 0 si N-1) care sunt multipli de M. Aceasta se realizeaza simplu "generand" combinarile respective: ne bazam pe recurenta CNk+1 = CNk * (n-k) / (k+1) si verificam cate dintre acestea sunt divizibile cu M. Problema este ca aceste valori vor deveni uriase destul de rapid, iar stocarea lor in memoria calculatorului este ineficienta. Din acest motiv nu se vor retine numerele propriu zise, ci doar exponentii factorilor primi ai lui M, (numarul maxim de factori primi ai lui fiind maxim aproximat la O(ln ln M), si 9 pentru datele de test ale problemei) care se vor actualiza pentru fiecare combinare procesata.
Complexitatea finala a algoritmului devine astfel O(N * ln ln M).
Amenzi
(clasele 11-12)
...
Secventa 5
(clasele 11-12)
...
