Witam.
Rozwiązuje zadany problem:
Policz ilość nieparzystych wartości Symbolu Newtona dla 0<= n,k <=N. Ograniczenie N<10^9
Do czego doszedłem. Po zamienieniu w Trójkącie Pascala (który jest zbiorem interesujących mnie wyników) wartości parzystych na 0 a nieparzystych na 1 uzykuję fraktal, Trójkąt Sierpińskiego. Indeksując od zera n jako wiersza a k jako kolumny, mam napisane rozwiązanie mojego problemu. Musze tylko jeszcze policzyć ilość jedynek i najlepiej w dość szybkim czasie.
Co zauważyłem:
- Każdy wiersz zawiera tyle 1 ile 2^x, a x to ilość jedynek w zapisie binarnym N (wiersz). Jednak dla miliarda N trochu to zajmie, nawet jeżeli ztablicuje wszystkie potęgi 2 do 32 (miliard mieści się w 32 bitach).
- Jeżeli n+1=2x to liczba nieparzystych rozwiązań wynosi 3x.
Teraz na pewno da się zrobić jakąs sprytną rekurencję (w SPACJA końcu to fraktal) do policzenia ilości jedynek między N a najbliższym 2^x. Proszęo pomoc i rady.
Pozdrawiam i przepraszam za błędy w pisowni.