Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-07-11 19:11:53.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:preasimplu.in, preasimplu.outSursăJunior Challenge 2016
AutorAndrei Constantinescu, Costin OncescuAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Prea Simplu!

In drumul sau spre olimpiadele internationale Arhitectul Ierdnac s-a gandit la urmatoarea problema:

Fie un sir binar bi cu N elemente. Initial toti bitii sunt setati pe valoarea 0. Fie flip(l, r) o operatie ce schimba elementele sirului in felul urmator:
• Daca rangul elementului nu apartine intervalului [l, r], atunci elementul respectiv ramane neschimbat;
• Altfel, elementul isi schimba valoarea (adica din 0 devine 1 si din 1 devine 0).
Se cere numarul de siruri finale ce se pot obtine daca se efectueaza fix K operatii de flip la alegere. Deoarece raspunsul poate fi destul de mare, se cere afisarea acestuia modulo 109 + 7.

Vazut fiind acolo, acesta s-a intalnit cu Bossu' Frumosu' si i-a povestit despre problema. Acesta a raspuns imediat prin faimoasa deja replica "Prea simplu!" si a sugerat mai multe metode de a complica artificial problema. Dupa lungi deliberari, comisia a decis - numarul de solutii va trebui afisat modulo un numar natural nenul MOD arbitrar!

Din nefericire, Bossu' Frumosu' nu stia sa solutioneze noua problema, dar Arhitectul Ierdnac exclama imediat "Da' stai dom'le ca e usoara!" si, astfel, problema a ajuns in setul de probleme Junior Challenge 2016.

Date de intrare

Fişierul de intrare preasimplu.in va contine pe prima linie un numar natural nenul T, semnificand numarul de teste ce vor urma. Apoi, testele vor fi descrise pe cate o linie de forma N K MOD.

Date de ieşire

Fişierul de ieşire preasimplu.out va contine T linii, fiecare continand raspunsul pentru testul corespunzator din input.

Restricţii

  • 1 ≤ N, K ≤ 2 000 000
  • 2 ≤ MOD ≤ 1 000 000 007
  • Subtask 1 (10 puncte): 1 ≤ N ≤ 8, 1 ≤ K ≤ 4
  • Subtask 2 (10 puncte): 1 ≤ N ≤ 15, 1 ≤ K ≤ 15
  • Subtask 3 (10 puncte): 1 ≤ N, K ≤ 500
  • Subtask 4 (20 puncte): 1 ≤ N x K ≤ 1 000 000
  • Subtask 5 (25 puncte): 1 ≤ N, K ≤ 2 000 000, MOD = 109 + 7
  • Subtask 6 (25 puncte): Restrictii initiale

Exemplu

preasimplu.inpreasimplu.out
2 1 1000
3

Explicaţie

Sirul initial este 0 0.

Folosind operatia flip(1, 1), se obtine sirul 1 0;
Folosind operatia flip(2, 2), se obtine sirul 0 1;
Folosind operatia flip(1, 2), se obtine sirul 1 1.

Asadar, se pot obtine 3 siruri.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?