Gigel a studiat recent şirurile cu n elemente, numere naturale. Pentru un astfel de şir S, Gigel doreşte să afle răspunsul la întrebările:
a) Care este numărul minim de subşiruri strict crescătoare în care se poate partiţiona S?
b) Care este numărul de secvenţe, modulo 20011, cu suma elementelor divizibilă cu k( care se pot obţine din S?
Cerinţă
Dându-se un şir S cu n elemente numere naturale şi un număr natural k se cere să se răspundă la cele două întrebări.
Date de intrare
Pe prima linie a fişierului calcule.in se află valorile naturale n şi k separate printr-un spaţiu. Pe următoarea linie se află cele n elemente ale şirului S, numere naturale separate prin câte un spaţiu.
Date de ieşire
Fişierul calcule.out va conţine două linii, pe prima linie fiind scris un număr natural reprezentând răspunsul la întrebarea a), iar pe a doua, un număr natural reprezentând răspunsul la întrebarea b).
Restricţii
• 1 < n < 100 000
• S are elemente mai mici sau egale cu 20 000
• k < 50 000, k < n
• Un subşir al şirului S se obţine selectând elemente din S în ordinea în care sunt în S, dar nu obligatoriu de pe poziţii consecutive, iar o secvenţă a şirului S se obţine selectând elemente în ordinea în care sunt în S, dar obligatoriu de pe poziţii consecutive. Se admit şi secvenţe sau subşiruri cu un singur element.
• Pentru 50 % din teste k < 10 000
• Mai multe subşiruri ale lui S formează o partiţie dacă elementele reuniunii subşirurilor pot fi reaşezate astfel încât să se obţină exact S.
• x modulo y reprezintă restul împărţirii lui x la y.
Exemple
calcule.in
calcule.out
Explicaţii
10 3
5 3 8 6 9 6 2 7 9 6
4
23
a) O partiţie cu număr minim (4) de subşiruri crescătoare este următoarea:
5 6 7 9
3 6 9
8
2 6
b)Există 23 de secvenţe cu suma divizibilă cu 3. Iată două dintre acestea:
3
6 2 7