Lista de probleme 5

Filtrare

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

Se dă a, b și c, să se calculeze \({a}^{{b}^{c}}\) modulo \({10}^{9}+7\).

Se dă N și Q, apoi Q interogări de tipul K X pentru fiecare interogare să se afișeze separate prin spațiu ( ficare interogare pe un rând diferit ):

1. Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) & \(a_2\) & ... & \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu & am notat operația pe biți AND.

2. Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) | \(a_2\) | ... | \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu | am notat operația pe biți OR.

3.Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) ^ \(a_2\) ^ ... ^ \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu ^ am notat operația pe biți XOR.

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