505. Cwany Lutek [CWANY_LU]

Zadanie:
https://pl.spoj.com/problems/CWANY_LU

Skrócony opis problemu:

Sprawdź czy dla danych $n$ i $k$ ($n, k \in \left<0;10^9\right>$) $\binom{n}{k}$ jest liczbą parzystą czy nieparzystą.

Rozwiązanie naiwne:

Możemy obliczyć silnię z $n$, $k$ oraz $n-k$ i podzielić je przez siebie.

Złożoność: $O\left(n \left(\log n \log \log n\right)^2\right)$. Skąd taka dziwna złożoność? Wydaje się, że liczenie silni jest liniowe. Jest, ale dla małych silni. Dla większych standardowe typy danych nie wystarczą i trzeba będzie użyć np. algorytmu Piotra Borweina z powyższą złożonością.

Rozwiązanie sprytniejsze:

Możemy zliczyć ilość dwójek w rozkładzie na czynniki pierwsze liczb $n$, $k$ oraz $n-k$. Innymi słowy interesuje nas największa potęga dwójki, która dzieli $n!$ (oznaczmy ją przez $a$), $k!$ ($b$) oraz $(n-k)!$ ($c$). Jeśli $a > b+c$ to znaczy, że w liczniku zostaną jeszcze jakieś nieskrócone z mianownikiem dwójki, a więc wynik będzie parzysty. W przeciwnym wypadku wynik będzie nieparzysty.

Jak obliczyć największą potęgę 2 dzielącą $n!$? Można zauważyć, że będzie to iloczyn największych potęg dwójek dzielących wszystkie czynniki silni. Czyli np. dla 5! to będzie największa potęga 2 dzieląca (NP2D) 1 (czyli 1) razy NP2D 2 (czyli 2) razy NP2D 3 (czyli 1) razy NP2D 4 (czyli 4) razy NP2D 5 (czyli 1). Mamy więc $1 \cdot 2 \cdot 1 \cdot 4 \cdot 1 = 8$. I faktycznie $\frac{120}{8}=15$ daje liczbę nieparzystą. Jak widać czynniki nieparzyste możemy pomijać. Tak więc nasz wzór to:

$$\prod_{k=1}^{\left\lfloor \frac{n}{2} \right\rfloor} NP2D(2k)$$

Największą potęgę 2 dzielącą $x$ możemy policzyć np. w czasie logarytmicznym sprawdzając czy kolejne potęgi 2 dzielą $x$.

Zaletą tego rozwiązania jest niezależność od rozmiaru danych, gdyż nie musimy liczyć samych silni.

Złożoność: $O(n \log n)$, bo dla każdej z $\frac{n}{2}$ czynników silni liczymy w czasie logarytmicznym NP2D ten czynnik. I tak dla $n!$, $k!$ i $(n-k)!$.

Algorytm:

int NP2D(int n) // wykładnik największej potęgi 2 dzielącej n
{
    int i;
    for(i = 1; n%(1<<i) == 0; ++i); // zaczynamy od 2^1, bo sprawdzamy tylko liczby parzyste
    return i; // zwracamy wykładnik, czyli ilość 2 w iloczynie
}

int NP2DS(int n) // wykładnik największej potęgi 2 dzielącej silnię
{
    int i, x = 0;
    for(i = 2; i <= n; i += 2)
        x += NP2D(i);
    return x; // zwracamy wykładnik
}

int main()
{
    int n, k;
    get(n, k);
    if(n < k)
        puts("P");
    else
        puts(NP2DS(n) > NP2DS(k)+NP2DS(n-k) ? "P" : "N"); // operator trójwarunkowy
}

Rozwiązanie sprytniejsze nr 2:

Możemy obliczyć największą potęgę 2 dzielącą (NP2D) czynnik z silni w czasie stałym. Niestety my potrzebujemy wykładnik tej potęgi, gdyż chcemy znać ilość 2 w rozkładzie na czynniki pierwsze silni. Możemy jednak w czasie logarytmicznym zamienić potęgę 2 na jej wykładnik dzieląc ją przez 2 aż się będzie dało i inkrementując cały czas wykładnik (który na początku jest równy 0). Jak jednak obliczyć potęgę 2 dzielącą jakieś $x$ w czasie stałym? Ano tak:

$$NP2D(x) = \left(x_2 \wedge -x_2\right)_{10}$$

Dlaczego? Gdyż liczby całkowite są reprezentowane w systemie U2. Oznacza to, że zmiana znaku liczby na przeciwny to odwrócenie wszystkich bitów, a następnie dodanie 1. Gdyby nie do dodanie 1, to iloczyn logiczny ($\wedge$) byłby równy 0, gdyż $x \wedge \neg x = 0$. Ta jedynka idąc od końca liczby w zapisie binarnym (czyli od najmniej znaczących bitów) zamienia wszystkie 1-nki na zera, aż nie napotka zera, które zamieni na 1-nkę (tak samo jak dodając w systemie dziesiętnym 1 do 6999 zamieniamy 9 na 0 aż nie napotkamy nie-9). No a skoro zamienia 1-nki na zera, to wynik dla tych zer również będzie zerem. Pozostałe pozycje również dadzą 0, gdyż wszędzie będą przeciwne wartości (0 i 1 lub 1 i 0). Wyjątkiem jest tylko ta jedna nowopowstała 1-nka, która pokryje się z dodatnią wartością $x$. Jako że będzie to jedyna 1-nka w reprezentacji binarnej wyniku, to sam wynik będzie potęgą 2.

Złożoność: $O(n \log n)$, bo dla każdej z $\frac{n}{2}$ czynników silni obliczamy z niego NP2D w czasie logarytmicznym.

Algorytm:

int NP2D(int n) // wykładnik największej potęgi 2 dzielącej n
{
    int x = 0; // na początku wykładnik jest równy 0
    n &= -n; // obliczamy największą potęgę 2 dzielącą n
    while(!(n&1)) // dopóki n dzieli się bez reszty przez 2
        ++x, // inkrementujemy licznik
        n >>= 1; // dzielimy n przez 2
    return x;
}

Rozwiązanie jeszcze sprytniejsze:

Możemy znaleźć wykładnik potęgi 2 w czasie $O(\log \log n)$.

Dla pierwszego "sprytniejszego" algorytmu możemy to zrobić wyszukując binarnie $NP2D(x)$. Tak więc nie sprawdzamy najpierw 2, potem 4, itd., ale najpierw sprawdzamy $2^{15}$ i jeśli się dzieli to sprawdzamy czy dzieli się przez $2^{\frac{15+30}{2}}$, a jeśli nie to czy dzieli się przez $2^{\frac{1+15}{2}}$. Czyli szukamy binarnie wykładnika.

Złożoność: $O(n \log \log n)$, bo dla każdego z $n$ czynników sprawdzamy pesymistycznie logarytmiczną ilość potęg 2, a ich też jest logarytmiczna ilość względem $n$. Czyli logarytmiczna ilość logarytmicznej ilości $n$.

Rozwiązanie jeszcze² sprytniejsze:

Okazuje się, że da się obliczyć NP2D silni (NP2DS) w czasie logarytmicznym.

Póki co dla każdego z $\frac{n}{2}$ czynników (2, 4, ..., n) sprawdzamy w czasie stałym NP2D tego czynnika. A gdyby zrobić na odwrót? Czyli dla każdej potęgi dwójki chcemy zliczyć ilość jej wystąpień w iloczynie wszystkich czynników w czasie stałym. Tak więc obliczamy kolejne potęgi $2^i$ aż przekroczymy $n$ i dla każdej z nich do wyniku dodajemy $\left\lfloor \frac{n}{2^i} \right\rfloor$. Dlaczego? Dlatego, że obliczamy ile jest czynników, które się dzielą przez $2^i$. Jest ich właśnie $\left\lfloor \frac{n}{2^i} \right\rfloor$, bo jak mamy np. $10!=1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10$ to przez $2^1$ dzieli się $\frac{10}{2}=5$ liczb. Przez $2^2$ dzieli się $\frac{10}{4}=2$ liczby. Itd. A dlaczego sumujemy dla każdej potęgi 2 sumę czynników, które się przez nią dzielą? Ano dlatego, że np. w 8 są 3 dwójki i musimy ją policzyć 3 razy (dla 2, 4 i 8).

Na końcu porównujemy $NP2DS(n)$ oraz $NP2DS(k) \cdot NP2DS(n-k)$ i jeśli to pierwsze jest większe, to wypisujemy, że symbol Newtona jest parzysty, a w przeciwnym wypadku nieparzysty.

Złożoność: $O(\log n)$.

Algorytm:

int NP2DS(int n) // wykładnik największej potęgi 2 dzielącej silnię
{
    int i, x = 0;
    for(i = 2; n/i; i <<= 1)
        x += n/i; // automatyczny floor
    return x;
}

Rozwiązanie najsprytniejsze:

Cały problem możemy rozwiązać... w czasie stałym! Opętał mnie szatan? Nie. Wszystko wynika z twierdzenia Lucasa.

O co chodzi w teorii Lucasa? Ano o taką jedną kongruencję:
$$\binom{n}{k} \equiv \prod_{i=0}^{\left\lfloor \log_2 \max(n,k) \right\rfloor} \binom{n_i}{k_i} \pmod{p}$$
...gdzie:
$$n = \prod_{i=0}^{\left\lfloor \log_2 n \right\rfloor} n_i \cdot p^i \\ k = \prod_{i=0}^{\left\lfloor \log_2 k \right\rfloor} k_i \cdot p^i \\ p \in \mathbb{P}$$

Innymi słowy, $n$ i $k$ zamieniamy na system pozycyjny o podstawie $p$, gdzie $p$ jest jakąś liczbą pierwszą. W naszym przypadku $p=2$, gdyż interesuje nas parzystość symbolu Newtona.

Dodatkowo wyjaśnię, że kongruencja to równość modulo coś. Tak więc np. $69 \equiv 96 \pmod{9}$, gdyż obie liczby dają tą samą resztę z dzielenia przez 9.

No i po co nam to twierdzenie? Przyjrzyjmy się co się dzieje dla $p=2$. Zamieniamy obie liczby na system binarny i chcemy obliczyć symbole Newtona dla wszystkich cyfr binarnych. Co nam to daje? Przecież mieliśmy obliczyć jeden symbol Newtona, a teraz mamy ich logarytmiczną ilość! Owszem, ale możemy zauważyć, że są tylko 4 możliwe wyniki takiego symbolu. Musimy umieć obliczyć tylko $\binom{0}{0}, \binom{0}{1}, \binom{1}{0}, \binom{1}{1}$. Wszystkie owe symbole dają 1 oprócz $\binom{0}{1}$. My musimy wymnożyć dla każdej pozycji $\binom{n_i}{k_i}$. Wynikiem będzie 1 albo 0. Jeśli wynikiem będzie 1, to symbol Newtona jest nieparzysty (bo reszta z dzielenia przez 2 to będzie 1), a jeśli 0, to parzysty. Tak więc de facto, jeśli na jakiejś pozycji w $n$ będzie 0, a na tej samej pozycji w $k$ będzie 1, to symbol jest nieparzysty. Moglibyśmy oczywiście sprawdzić to w czasie logarytmicznym, zamieniając $n$ i $k$ na system binarny, ale jak to szybciej zrobić? Ano tak, że obliczamy sumę logiczną $n \vee k$ i jeśli będzie ona równa $n$ to symbol jest nieparzysty. Dlaczego? Bo jeśli na danej pozycji w $n$ mamy jedynkę, to niezależnie od cyfry na tej samej pozycji w $k$ suma logiczna da nam 1 (czyli tak samo jak w $n$). Jeśli natomiast będziemy na jakiejś pozycji w $n$ i $k$ mieli zera, to suma logiczna zwróci nam 0 (czyli tak samo jak w $n$). Jeśli z kolei będziemy mieć w $n$ 0, a w $k$ na tej samej pozycji $1$ to suma logiczna zwróci nam 1, a w $n$ na tej pozycji było 0. Więc jeśli suma logiczna $n \vee k$ nie da nam $n$ to znaczy, że był symbol $\binom{0}{1}$, który będąc zerem wyzeruje nam cały iloczyn, a więc da resztę z dzielenia przez 2 zero, co oznacza, że symbol jest parzysty.

Złożoność: $O(1)$.

Przykład:
$n = 49$, $k = 13$
$$49_{10} = 101111_2 \\ 13_{10} = 001101_2$$

Jak widzimy, suma logiczna to $101111_2 = 49_{10}$, a więc tyle, co $n$. Oznacza to, że $\binom{47}{13}$ jest nieparzyste. I faktycznie, iloczyn symboli ze wszystkich pozycji to 1, jako że wszystkie symbole są równe 1.

$n = 45$, $k = 14$
$$45_{10} = 101101_2 \\ 14_{10} = 001110_2$$

Tutaj z kolei, na drugiej pozycji od końca mamy parę 0-1. I faktycznie suma logiczna to $101111_2 = 49_{10} \neq 45_{10}$.

Ostateczny algorytm:

int main()
{
    int n, k;
    get(n, k);
    puts((n|k) == n ? "N" : "P");
}