Fişierul intrare/ieşire:abperm.in, abperm.outSursăad-hoc
AutorAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

ABPerm

Se dau două permutări de ordin N.

Cerinţă

Se precizează tipul T al cerinţei, care poate fi 1 sau 2:
1) Dacă T=1, atunci se cere să se afle câte permutări de ordin N se pot obţine după N paşi de "intercalare" a celor două permutări
2) Dacă T=2, atunci se cere să se afle câte permutări distincte de ordin N se pot obţine după N paşi de "intercalare" a celor două permutări

Date de intrare

Fişierul de intrare abperm.in conţine pe primul rând numerele T şi N. Pe al doilea rând, separate prin câte un spaţiu, se află elementele permutării a[], iar pe al treilea rând, separate prin spaţiu, se află elementele permutării b[].

Date de ieşire

În fişierul de ieşire abperm.out pe primul rând se află un singur număr natural reprezentând numărul cerut conform tipului cerinţei.

Restricţii

  • 1 ≤ N ≤ 10^5
  • Deoarece valorile cerute pot fi numere foarte mari se cere calcularea acestor valori modulo 10^9+7
  • În general, prin „intercalare” a două şiruri a[] şi b[], de lungimi n şi respectiv m, se înţelege determinarea unui nou şir c[], de lungime n+m, care conţine toate elementele celor două şiruri a[] şi b[]. Elementele şirurilor a[] şi b[] formează subşiruri în c[]. Dacă pentru primele k elemente din c[] au fost folosite primele i elemente din a[] şi primele j elemente din b[], atunci pentru elementul al k+1-lea din c[] va fi folosit a[i+1] sau b[j+1]. La fiecare pas de intercalare se adaugă încă un element sirului care se construieşte c[].

Exemplu

abperm.inabperm.out
1 3
1 2 3
3 2 1
8

Explicaţie

După 3 paşi de intercalare se pot obţine permutările: 1 2 3, 1 2 3, 1 3 2, 1 3 2, 3 1 2, 3 1 2, 3 2 1, 3 2 1

abperm.inabperm.out
2 3
1 2 3
3 2 1
4

Explicaţie

După 3 paşi de intercalare se pot obţine 4 permutări distincte: 1 2 3, 1 3 2, 3 1 2, 3 2 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?