== include(page="template/taskheader" task_id="abperm") ==
Poveste şi cerinţă...
Se dau două permutări de ordin $N$.
h2. 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
h2. Date de intrare
Fişierul de intrare $abperm.in$ ...
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[]$.
h2. Date de ieşire
În fişierul de ieşire $abperm.out$ ...
Î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.
h2. 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[]$.
h2. Exemplu
table(example). |_. abperm.in |_. abperm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1 3
1 2 3
3 2 1
| 8
|
h3. 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
table(example). |_. abperm.in |_. abperm.out |
| 2 3
1 2 3
3 2 1
| 4
|
h3. 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
== include(page="template/taskfooter" task_id="abperm") ==
== include(page="template/taskfooter" task_id="abperm") ==
