infoarena

Aici puteţi discuta despre problema Functii (http://infoarena.ro/problema/functii).

Cuvantul "exista" e pus de la mine... Cred k ar trebui reparate aceste 2 greseli.  :)

enuntul a fost modificat. De asemenea a fost modificata o restrictie (oops  :oops:). Imi cer scuze ptr cei care s-au chinuit sa rezolve problema si au luat 0 din cauza enuntului.

Cum se poate calcula o expresie de genul [(x^y)-k] % p? Sau trebuie numere mari pt efectuarea ridicarii la putere?

rest= x^y%p;
rest-=k;
while (rest<0) rest+=p;

Sau ca sa eviti while-ul:

Cand trimit o sursa imi apare eroarea

Ar trebui sa se fi rezolvat problema acum.

Daca mai apare vreo chestie ciudata nu ezitati sa semnalati.

S-a mai modificat odata enuntul. Rezultatul trebuie afisat modulo 30103. Scuze  :oops:

In sfarsit... habar n-aveam de la ce primeam WA...

Care e cea mai rapida metoda de a calcula Comb(n,k) la problema asta? Am vazut ca in complexitate O(n*k) nu intra in timp...

E o problema...

Nu se poate unui X sa apartina mai multe Y..ori asta s ar intampla daca X ar fi mai mic ca Y cum e in ex vostru..intervalul 1 < n < 10000 e prost facut

Floryan a vazut asta primul...

@florian: daca ti-ai face o matrice C[ i ][ j ] - combinari de i luate cate j, ai putea calcula independent fiecare linie in o(n). Gandestete cum ai putea sa scoti din C[ i ][ j ] pe C[ i ][ j+1 ]

@Alexandru_B: Nu e prost facut intervalul. Daca nu poate exista o functie ptr care proprietatile din enunt sa fie indeplinite mie mi se pare normal ca raspunsul sa fie 0.

Ok...scz credeam ca pur si simplu nu are cazuri imposibile.
Ce matrice este aia C[j]?

Nu prea am inteles ce vrei sa spui... Clasic se rezolva cu c[ i ][ j ]=c[ i-1 ][ j ]+c[ i-1 ][ j-1 ]. Eventual se reduce memoria, utilizand doar doi vectori [pt ultimile 2 linii]. Aceasta rezolvare are complexitate O(N*K) si nu intra in timp. Poti detalia putin ideea ta...?  :)

Tie iti trebuie doar restul la impartirea cu 30103 (numar prim). Poti sa precalculezi resturile factorialelor, iar pentru combinari folosesti definitia: C(N, K) = N! / (K! * (N - K)!). Inmultesti un numar cu 2 inverse modulare ale celorlalte.

Ok. Va multumesc amandorura pentru raspunsuri.
@devilkind : astept sa vii cu o explicatie putin mai detaliata... pare interesant ce ai spus, dar nu ma prind.

Apropop de inverse modulare. Nu am lucrat niciodata si cred ca e timpul sa ma apuc. Sper sa nu fiu prea offtopic.
Sa consideram o formula mai simpla, deci sa zicem ca am de calculat ( X/Y ) % P. In loc sa calculez impartirea, mai bine inmultesc X cu inversul lui Y. Inversul lui Y (de la mate) este 1/Y. Dar acum apare Fermat si spune ca X^(P-1) % P = 1 => X^(-1)=X(P-2) (mod P). Asadar, inversul lui Y [din formula noastra] devine Y^(P-2). Asadar, problema se reduce la egalitatea:

.                                     X/Y = X * Y^(P-2) ( mod P)

Iar in cazul problemei "functii", X este n!, iar Y este k! (si apoi (n-k)! ), iar P este 30103.

Cam asta stiam eu.. insa nu am lucrat niciodata cu asta. E bine ce am spus ? Daca am gresit in vreun loc, va rog sa imi spuneti. Multumesc!  :ok:

C(n,k)= n!/k!*(n-k)! = n!/( (k-1)!*(n-k+1)! )   * (n-k+1)/k = C(n,k-1) * (n-k+1)/k

E corect.

Interesanta idee. E bn de stiut lucrul asta. Multumesc.  :D
 
Multumesc si tie, Stefan Istrate.  :ok:

Salut.Am o nelamurire la problema asta.Eu m-am gandit cam asa:
E clar ca daca |f(1)| + |f(2)| + .. |f(n)| =S exista fix S din cele n valori din domeniu egale cu 1 sau -1 si mai sunt deci n-S valori de 0.Ca functiile cautate sa fie sigur surjective Aleg cate o valoare de 1 si de -1(e garantat faptul ca vor fi zerouri).Sunt n*(n-1)posibilitati de alegere a celor 2 valori de 1 si -1.Pe urma au mai ramas S-2 valori de 1 sau -1 de pus.Sunt comb[n-2][S-2] metode de a alege o configuratie de S-2 valori din n-2 posibile.Pentru fiecare configuratie sunt 2^(S-2) metode de a alege 1 sau -1.
Ca urmare => rezultatul cautat ar trebui sa fie : n*(n-1)*comb[n-2][S-2]*2^(S-2) ,avand grija la operatiile in modul. Pe exemplu n=5,S=3 => inlocuind: 5*4*comb[3][1]*2^1=5*4*3*2=120 ,nu 60. Poate cineva sa ma lamureasca unde gresesc in rationament?  :-k

Imi puteti da si mie o functie invmodular(x)??? Ca nu inteleegg

Despre invers modular poti citi aici: http://www.infoarena.ro/problema/inversmodular.

poate cineva sa-mi explice de ce 60 dar nu 80? problema consta in cate combinari de {1,0,-1} luate cate N exista astfel incat suma modulelor lor sa fie S sau eu ceva nu am inteles corect? dupa logica mea ar trebui sa fie C(N,K)*2^K. ](*,)

nu e chiar 2^K (unde K == sum)

e (2^K)-2

1) excluzi mulțimea vidă
2) surjectivitatea înseamnă că trebuie să ai valori și de -1 și de 0 și de 1, cu alte cuvinte n-ai voie să ai doar 0 și 1 sau doar 0 și -1