Lista de probleme 3

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3859 Cai

Se dă N, în câte moduri putem plasa 2 cai pe o tablă de șah de N pe N astfel încât să nu se atace?

Se dau Q interogări de tipul : n , st , dr , r , k. Pentru fiecare din aceste interogări să se determine care este numărul maxim din șirul [n xor st , n xor (st+1) , n xor (st+2) , .... , n xor dr] care dă restul k prin împărțire la r , precum și numărul de numere din secvența care dau restul k prin împărțire la r.

Anual, Imperiul Interstelar organizează o întâlnire administrativă în capitală. La întâlnire sunt invitați toți guvernatorii planetelor din imperiu. Planetele imperiului pot fi numerotate cu valori de la 0 la MOD-1(inclusiv) unde planeta 0 este chiar capitala. Distanțele mari dintre planete fac transportul obișnuit între planete aproape imposibil. Din fericire, găuri de vierme conectează tot imperiul. Vom nota planeta către care duce o gaură de vierme cu f(x) = (x * a + b) % MOD. Astfel, de la planeta x există un drum către planeta f(x) și un drum de la planeta f(x) la planeta x. Fiecare guvernator începe de pe o planetă cunoscută și trebuie să ajungă în capitală. Atenție, pozițiile inițiale nu trebuie să fie distincte! Fiecare salt printr-o gaură de vierme consumă o unitate de energie din rețeaua centrală. Se presupune că fiecare guvernator ia ruta cea mai scurtă către capitală. Din motive birocratice, sunteți rugați să calculați cantitatea de energie consumată de transportul guvernatorilor către captială.