509 Functii

[•DITzoneC]

Aici puteţi discuta despre problema Functii.

[•Florian]

Cod:

 Ea [b]trebui[/b] sa numere cate functii surjective definite pe multimea { 1,2,3,4..n } cu valori in multimea numerelor { 0,-1,1 } [i]exista[/i] astfel incat |f(1)| + |f(2)| + .. |f(n)| =S (toate sunt in modul) . 

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

[•devilkind]

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

[•Dastas]

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

[•devilkind]

Cod:

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

[•stef2n]

Sau ca sa eviti while-ul:

Cod:

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

[•c_sebi]

Cand trimit o sursa imi apare eroarea

Eroare de compilare in evaluator:
sh: g++: command not found

[•DITzoneC]

Ar trebui sa se fi rezolvat problema acum.

Daca mai apare vreo chestie ciudata nu ezitati sa semnalati.

[•devilkind]

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

[•Dastas]

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

[•Florian]

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

[•iepuras_binar]

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

[•devilkind]

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

[•iepuras_binar]

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

[•Florian]

@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 ]

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

[•stef2n]

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.

[•Florian]

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! 

[•devilkind]

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

[•stef2n]

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.

E corect.

[•Florian]

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

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

[•cosmin79]

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? 

[•costyrazvy]

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

[•AlexandruValeanu]

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

[•valentin50517]

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.

[•Djok]

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