== include(page="template/taskheader" task_id="pscfft") ==
Poveste şi cerinţă...
_După îndelungi căutări, Tanaka a găsit manuscrisul adevărului, pe care erau scrise secretele antice ale $FFT$-ului. Cu ajutorul acestora a compus următoarea problemă:_
Notăm cu $++$ concatenarea a două șiruri $(ex. [1, 2, 3] ++ [4, 5, 6] = [1, 2, 3, 4, 5, 6]).$
Definim funcția inc în felul următor:
$inc([a{~0~}, ..., a{~n-1~}], k, s) = [(a{~0~} + k) $%$ s, ..., (a{~n - 1~} + k) $%$ s]$, unde prin $a % b$ s-a notat restul împărțirii lui $a$ la $b$.
Definim recursiv familia de șiruri $FFT$ în felul următor:
$FFT (0, s) = [0]$
$FFT (k + 1, s) = inc(FFT (k, s), 0, s) ++ inc(FFT (k, s), 1, s) ++ ... ++ inc(FFT (k, s), s - 1, s)$
De exemplu:
$FFT (1, 3) = [0, 1, 2],$
$FFT (2, 3) = [0, 1, 2, 1, 2, 0, 2, 0, 1],$
$FFT (3, 3) = [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0]$
h2. Cerinţă
Dându-se un șir $V$ de lungime $N$, un număr natural nenul $S$, se cere să se afle prima poziție unde se găsește V ca subsecvență în FFT(<tex>10^{10^{10^{100}}}</tex> + 1, S) și să se afișeze restul împărțirii acesteia la $10^9^+7$, sau să se precizeze că nu apare în șir.
h2. Date de intrare
Fişierul de intrare $pscfft.in$ ...
Pe primul rând al fișierului de intrare pscfft.in apare numărul natural nenul $T$ care reprezintă numărul de teste. Urmează $T$ teste, fiecare cu următorul format:
Pe primul rând al unui test va apărea un număr natural nenul $N$, și un număr natural nenul $S$. Pe următoarea linie vor apărea câte $N$ numere naturale între $0$ și $S - 1$, ce reprezintă valorile lui $V$.
h2. Date de ieşire
h2. Date de ieşire
În fişierul de ieşire $pscfft.out$ ...
În fișierul de ieșire pscfft.out pentru fiecare test se va afișa pe câte o linie fie restul împărțirii la $10^9^ + 7$ a poziției de început a primei apariții a șirului $v$ ca subsecvență în șirul FFT(<tex>10^{10^{10^{100}}} </tex> + 1, S), sau $-1$ dacă aceasta nu există.
h2. Restricţii
h2. Restricţii și precizări
* $... ≤ ... ≤ ...$
• $1 ≤ S ≤ 1 000 000 000$
• $1 ≤ N ≤ 500 000$
• $1 ≤ T ≤ 500 000$
• Suma $N$-urilor pentru toate testele dintr-un fișier nu depășeste $500 000$.
• Pentru $10%$ din punctaj, $T ≤ 20, N ≤ 100$ și $S ≤ 3$
• Pentru alte $10%$ din punctaj, avem $T ≤ 20 , S ≤ 4$ și răspunsul, dacă există, nu depășește $500 000$
• Pentru alte $10%$ din punctaj, $S ≤ 4$
• Pentru alte $30%$ din punctaj, $S ≤ 5$
• Pentru alte $30%$ din punctaj, $S ≤ N$
• Se garantează că dacă pentru un test există un $K$ astfel încât șirul $V$ să apară în șirul $FFT (K, S)$ atunci acest șir $V$ va apărea și în șirul FFT (<tex>10^{10^{10^{100}}} </tex> + 1 + 1, S)
h2. Exemplu
table(example). |_. pscfft.in |_. pscfft.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
4 2
1 0 1 1
5 3
2 0 1 2 1
20 6
2 4 5 0 1 2 3 5 0 1 2 3 4 0 1 2 3 4 5 1
2 10000000
5 5
5 5
4 3 2 1 0
| 11
134
83
273492549
-1
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="pscfft") ==
