Fişierul intrare/ieşire:	pscfft.in, pscfft.out	Sursă	ONI 2018, Baraj
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.2 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Pscfft

După îndelungi căutări, Tanaka a găsit manuscrisul adevărului, pe care erau scrise secretele antice ale FFT-ului. Cu ajutorul acestora a compus următoarea problemă:

Notăm cu ++ concatenarea a două șiruri (ex. [1, 2, 3] ++ [4, 5, 6] = [1, 2, 3, 4, 5, 6]).

Definim funcția inc în felul următor:
inc([a₀, ..., a_n-1], k, s) = [(a₀ + k) % s, ..., (a_{n - 1} + k) % s], unde prin a % b s-a notat restul împărțirii lui a la b.

Definim recursiv familia de șiruri FFT în felul urmă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]

Cerinţă

Dându-se un șir V de lungime N, un număr natural nenul S, se cere să se afle prima poziție unde se găsește V ca subsecvență în FFT( $10^{10^{10^{100}}}$ + 1, S) și să se afișeze restul împărțirii acesteia la 10⁹+7, sau să se precizeze că nu apare în șir.

Date de intrare

Pe primul rând al fișierului de intrare pscfft.in apare numărul natural nenul T care reprezintă numărul de teste. Urmează T teste, fiecare cu următorul format:
Pe primul rând al unui test va apărea un număr natural nenul N, și un număr natural nenul S. Pe următoarea linie vor apărea câte N numere naturale între 0 și S - 1, ce reprezintă valorile lui V.

Date de ieşire

În fișierul de ieșire pscfft.out pentru fiecare test se va afișa pe câte o linie fie restul împărțirii la 10⁹ + 7 a poziției de început a primei apariții a șirului v ca subsecvență în șirul FFT( $10^{10^{10^{100}}}$ + 1, S), sau -1 dacă aceasta nu există.

Restricţii și precizări

• 1 ≤ S ≤ 1 000 000 000
• 1 ≤ N ≤ 500 000
• 1 ≤ T ≤ 500 000
• Suma N-urilor pentru toate testele dintr-un fișier nu depășeste 500 000.
• Pentru 10% din punctaj, T ≤ 20, N ≤ 100 și S ≤ 3
• Pentru alte 10% din punctaj, avem T ≤ 20 , S ≤ 4 și răspunsul, dacă există, nu depășeș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 garantează că dacă pentru un test există un K astfel încât șirul V să apară în șirul FFT (K, S) atunci acest șir V va apărea și în șirul FFT ( $10^{10^{10^{100}}}$ + 1 + 1, S)

Exemplu

pscfft.in	pscfft.out
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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta