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 sai sunt setati pe valoarea 0. Fie flip(l, r) o operatie ce schimba elementele sirului in felul urmator:
• Daca rangul elementului la care ne referim nu apartine intervalului [l, r], atunci elementul respectiv ramane neschimbat;
• Altfel, elementul isi schimba valoarea (adica din 0 devine 1 si, respectiv, 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 ≤ T ≤ 250
  • 1 ≤ N, K ≤ 300 000
  • 2 ≤ MOD ≤ 1 000 000 007
  • Suma tuturor N-urilor din fisier ≤ 600 000
  • Subtask 1 (10 puncte): 1 ≤ N ≤ 8, 1 ≤ K ≤ 4 - Fiecare test din grupa are T = 32 si fiecare pereche (N, K) apare maxim o data in input (Feedback testul 2)
  • Subtask 2 (15 puncte): 1 ≤ N ≤ 14, 1 ≤ K ≤ 14 - Fiecare test din grupa are T = 52 si fiecare pereche (N, K) apare maxim o data in input (totusi, testele grupei nu sunt maxime cu aceasta proprietate - altfel ar fi trebuit marita mult prea mult limita de timp pentru un astfel de subtask mic) (Feedback testul 3)
  • Subtask 3 (25 puncte): 1 ≤ N x K ≤ 300 000, iar suma dupa toate testele din fisierul curent din N x K ≤ 1 200 000 (Feedback testele 7 si 8)
  • Subtask 4 (25 puncte): 1 ≤ N, K ≤ 300 000, MOD = 109 + 7 (Feedback testele 11 si 15)
  • Subtask 5 (25 puncte): Restrictii initiale (Feedback testele 17, 19 si 20)

Exemplu

preasimplu.inpreasimplu.out
1
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?