1015 Xp

[•stef2n]

Aici puteti discuta despre problema Xp.

[•S7012MY]

Exista vreo proprietate pt (a/b) %p ?

[•pauldb]

Citeste aici.

[•toni2007]

Se face si fara invers modular, in o(n).

[•S7012MY]

Multumesc mult  
Ma intereseaza ceva fara invers modular(daca exista)

[•toni2007]

Imparti in bucati de sqrt.

[•S7012MY]

Am citit solutia oficiala si nu spune nimic despre invers modular. Poate cineva sa descrie solutia cu invers modular?   

[•freak93]

Nu stiu daca chiar vrei sa afli solutia cu invers modulari. Asta e cea care am implementat-o in timpul olimpiadei si am luat 80 nu 100.
Cred totusi ca se poate obtine si 100 daca e optimizata asa ca hai sa-ti explic:

Descompui numarul Q in factori primi Q=p1^q1 * p2^q2 * ..... *pk^qk

Orice numar val[ i ] din sir poate fi impartit in xval[ i ] si yval[ i ] astfel incat xval[ i ] * yval[ i ] = val[ i ] si xval[ i ] are factori primi numai din multimea {p1,p2,....,pk} si yval[ i ] factori primi care nu apartin aceastei multimi.

Daca notam cu P produsul val[1] * val[2] * .... * val[n], cu xP produsul xval[1] * xval[2] * ... * xval[n] si tot la fel yP din yval[1] s.a.m.d,  atunci P = xP * yP

Pentru a putea calcula prod[ i ] se observa ca in loc sa calculam P/val[ i ] putem calcula (xP/xval[ i ]) * (yP/yval[ i ]) (modulo Q).

yp si yval[ i ] necontinand factori primi comuni cu Q sunt prime cu Q si deci putem aplica invers modular pe ele. Calculam inversul modular a lui yval[ i ] si il inmultim cu yP. Asa obtinem o parte din prod[ i ].

Pentru a obtine a xP/xval[ i ] putem putem face o precalculare. Observam ca k (numarul de factori primi din descompunerae lui Q) e relativ mic <=20. Aflam pentru fiecare valoare la ce putere se afla in xP(sa o notam cu zk). Asta se face la prima parcurgere a sirului cand se calculeaza si yP. Observam ca p1^z1 * p2^z2 * ... * pk^zk = xP

Dupa ce aflam aceste valori se poate calcula o matrice calc in care calc[ i ][ j ] reprezinta pi^(zi-j). j<=30 (evident modulo Q).

Avand aceste valori calculate putem afla pentru orice xval[ i ] cat face xP/xval[ i ]. Il descompunem pe xval[ i ]= p1 ^ q1' * p2 ^q2' * ... * pk^qk'. Atunci xP/xval[ i ] va fi egal cu produsul elementelor calc[ i ][ qi' ] pentru i de la 1 la k.

Asa se formeaza solutia:
1) La prima parcurgere se descompune fiecare val in xval si yval si se calculeaza zi (pentru i de la k) si yP;
2) Se calculeaza matricea calc. (asta se face usor prin exponentiere rapida pana la zi-30( pentru i de la 1 la k) si inmultind cu pi pana se ajunge la zi cu exponentul.
2) La a doua parcurgere se descompun iar numerele val in xval si yval(pentru ca evident ele nu se pot mentine in memorie). Se calculeaza xP/xval[ i ] dupa procedeul descris mai sus si yP/yval[ i ] folosind invers modulare. Se inmultesc cele 2 astfel obtinandu-se prod[ i ] care se XOR-eaza cu raspunsul .

Later Edit: Complexitatea Worst Case este O(n*log₂(val_max) ) unde val_max in situatia de fata este 1.000.000.000. Pe cazul mediu se comporta mult mai bine, un O(n) cu constanta 8 din cate cred, voi incerca sa calculez si sa pun aici.

[•S7012MY]

Ms mult 

[•dushmi]

A reusit cineva sa ia 100 pe acesta problema cu divide et impera??? Eu am tot incercat diverse optimizari si nu reusesc sa intru in timp pe ultimele 5 teste

[•klamathix]

Ma indoiesc ca se poate, am incercat si eu de cateva ori. Mergea foarte greu pe teste mari si l-am rugat intr-o seara pe Dragos Rotaru, cel care a pus problema in arhiva, sa mareasca pentru cateva minute limita la 20 de secunde ca sa vad de curiozitate cat i-ar lua executia pe infoarena.
http://infoarena.ro/job_detail/493324

Deci slabe sanse. Eu pana la urma am bagat varianta in sqrt(n) memorie

[•dushmi]

Multumesc mult pt raspunsul rapid... Ma mir cu de ia asa de mult timp... Mie imi intra in < 6 secunde pe toate testele de la ONI ( Celeron la 1.8 GHz si 2 GB de RAM)...

O sa incerc si solutia de sqrt(n)

[•SpiderMan]

Vai doamne ce horror e problema asta, am reusit sa iau 100 cu divide et impera  http://infoarena.ro/job_detail/601094.

[•danalex97]

Poate cineva sa imi explice solutia cu invers modular sau sa imi trimita/posteze sursa ? Am facut si eu una cu invers modular , insa intra doar pt primele 5 teste 

Multumesc anticipat 

[•geniucos]

Imi poate spune si mie cineva ce e gresit in sursa mea de nu prinde nici un test?Pe primul exemplu am urmarit cu watch-ul si imi merge ca la carte.

Cod:

void divide(unsigned long long i,unsigned long long j,unsigned long long ai,unsigned long long bi,unsigned long long prod)
{
	if(i==j)
	{
		nr++;
		if(nr==1) s=prod;
		else s=s^prod;
	}
	else
	{
		unsigned long long c1,c2,c3,c4,ai1,bi1,a1,b1,p1,p2;
		unsigned long long c5;
		ai1=ai;
		bi1=bi;
		unsigned long long mij=(i+j)/2;
		unsigned long long k;
		a1=ai;
		b1=bi;
		k=i;
		p1=max(1,((k%p)^((a1+1)&(b1+1))%p)%p);
		for(k=i+1;k<=mij;k++)
		{
			a1=((ai+p-1)^(bi+1))%p;
			b1=((ai+p-1)|(bi+1))%p;
			p1=(1LL*p1*max(1,((k%p)^((a1+1)&(b1+1))%p)%p))%q;
			ai=a1;
			bi=b1;
		}
		/////////////////
		a1=((ai+p-1)^(bi+1))%p;
		b1=((ai+p-1)|(bi+1))%p;
		divide(mij+1,j,a1,b1,(prod*p1)%q);
		ai=a1;
		bi=b1;
		k=mij+1;
		p2=max(1,((k%p)^((a1+1)&(b1+1))%p)%p);
		for(k=mij+1;k<=j;k++)
		{
			a1=((ai+p-1)^(bi+1))%p;
			b1=((ai+p-1)|(bi+1));
			p2=(1LL*p2*max(1,((k%p)^((a1+1)&(b1+1))%p)%p))%q;
			ai=a1;
			bi=b1;
		}
		divide(i,mij,ai1,bi1,(1LL*prod*p2)%q);
	}
}

Foloseste tag-ul code cand postezi cod pe forum