Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | matrita.in, matrita.out | Sursă | Junior Challenge 2018 |
| Autor | Andrei Coman | Adăugată de |  Junior Challenge •JuniorChallenge2018 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Matrita
Plictisit de inmultirea polinoamelor in timp liniar, de rezolvarea conjecturilor sau a altor banalitati precum “Traveling salesman problem”, Nry s-a decis sa porneasca in cautarea secretului fericirii eterne. Privind insa in jurul sau, a constatat cu stupoare ca olimpicii recurg la tehnici necurate in acest joc pentru satisfactie, de la sustrasul subtil al surselor sau al ideilor de probleme, pana la acte mult mai grave, precum insusirea locurilor la IOI sau a editiilor precedente de Junior Challenge. Dorind insa sa fie original (si sa pastreze in acelasi timp noua traditie), Nry a ajuns la urmatoarea concluzie: trebuie sa subtilizeze Matrita!
Odata ajuns in posesia elixirului magic, acesta l-a asezat intr-un colt al Beciului Olimpic (unul din cele mai sigure adaposturi, in care dusmanii pot patrunde doar prin tavanul de sticla). Insa, pentru a se asigura ca noua sa achizitie nu va disparea in mod neasteptat, acesta a decis sa formeze un sistem de aparare in modul urmator: el a privit Beciul ca o matrice patratica de latura N + 1 (liniile si coloanele sunt numerotate de la 0 la N), Matrita aflandu-se in patratul aflat pe linia 0 si coloana 0. El doreste sa plaseze mai multe capcane in patrate cu indicii liniilor si ai coloanelor cuprinsi intre 1 si N, astfel incat fiecare capcana sa fie vizibila din punctul in care se afla Matrita (cu alte cuvinte, sa nu existe doua capcane situate in (l1, c1), respectiv (l2, c2) si un numar real k cu proprietatea ca x1 = x2 * k si y1 = y2 * k).
Nry va roaga sa raspundeti la urmatoarea intrebare: stiind numarul N, in cate moduri isi poate construi el sistemul de aparare al Matritei? Raspunsul trebuie afisat modulo MOD (un numar citit din fisierul de intrare).
Date de intrare
Fişierul de intrare matrita.in contine o singura linie pe care sunt scrise doua numere, N si MOD, cu semnificatia din enunt.
Date de ieşire
În fişierul de ieşire matrita.out veti afisa un singur numar natural, si anume raspunsul cerintei modulo MOD.
Restricţii
- Nry dispune de un numar nelimitat de capcane
- Fiind foarte paranoic, acesta va plasa intotdeauna cel putin o capcana
- 1 ≤ N ≤ 12.000.000
- 1 ≤ MOD ≤ 2.000.000.000
- Pentru teste in valoare 5 puncte N ≤ 10 si MOD = 1000000007
- Pentru alte teste in valoare de 10 puncte N ≤ 1900 si MOD = 1000000007
- Pentru alte teste in valoare de 15 de puncte N ≤ 4250 si MOD = 1000000007
- Pentru alte teste in valoare de 30 de puncte N ≤ 750.000
- Pentru alte teste in valoare de 30 de puncte N ≤ 5.000.000
- Pentru alte teste in valoare de 10 puncte N ≤ 12.000.000
- Legenda spune ca oricine gusta din Matrita are un loc asigurat la IOI 2020
Exemplu
| matrita.in | matrita.out |
|---|---|
| 1 1000000007 | 1 |
| 2 1000000007 | 11 |
| 5 1000000007 | 3538943 |
| 768325 1000000007 | 667479250 |
Explicaţie
Pentru primul exemplu, el poate doar sa amplaseze o capcana in patratul (1, 1).
Pentru cel de-al doilea exemplu, sunt valide urmatoarele configuratii:
{(1, 1)}, {(1, 1), (1, 2)}, {(1, 1), (2, 1)}, {(1, 1), (1, 2), (2, 1)},
{(2, 2)}, {(2, 2), (1, 2)}, {(2, 2), (2, 1)}, {(2, 2), (1, 2), (2, 1)},
{(1, 2)}, {(2, 1)}, {(1, 2), (2, 1)}.
Configuratia {(1, 1), (2, 2)} nu poate fi aleasa deoarece capcana (2, 2) nu este vizibila.
Nry considera ca o explicatie a ultimelor doua exemple ar fi inadecvat de lunga.
