Diferente pentru problema/pscfft intre reviziile #5 si #6

Diferente intre titluri:

Pscfft

pscfft

Diferente intre continut:

_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([a0, ..., an-1], k, s) = [(a0+k) $%$ s, ..., (an-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)

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([a0, ..., an-1], k, s) = [(a0+k) $%$ s, ..., (an-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]

*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. 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 (<tex>10^{10^{10^{100}}} </tex> + 1, s) și să se afișeze restul împărțirii acesteia la 1e9+7, sau să se precizeze că nu apare în șir.

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 (<tex>10^{10^{10^{100}}} </tex> + 1, s) și să se afișeze restul împărțirii acesteia la *10^9^+7*, sau să se precizeze că nu apare în șir.

h2. 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.

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*.

h2. 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 1e9+7 a poziției de început a primei apariții a șirului v ca subsecvență în șirul FFT (<tex>10^{10^{10^{100}}} </tex> + 1, s),
sau -1 dacă aceasta nu există.

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 *1^9^+7* a poziției de început a primei apariții a șirului *v* ca subsecvență în șirul FFT (<tex>10^{10^{10^{100}}} </tex> + 1, s),
sau *-1* dacă aceasta nu există.

h2. Restricţii și precizări

infoarena informatica de performanta

Diferente pentru problema/pscfft intre reviziile #5 si #6

Diferente intre titluri:

Diferente intre continut:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.