Ile razy odpalaliście FFT na jeden testcase? Ja 5.

5

3

Łukasz 😮😮😮

2:

Fibonacci multiply(Fibonacci f, Lucas l) {
....auto result = convolve(f, l);
....Lucas reversed(l.size());
....REP(k,l.size()) reversed[l.size()-1-k] = (k%2 ? -1 : 1) * l[k];
....auto r = convolve(f,reversed);
....REP(i,r.size()) {
........int nk = i - (l.size()-1);
........result[abs(nk)] += r[i] * ((nk >= 0 || nk % 2 != 0) ? 1 : -1);
....}
....return result;
}

@Maciej. Wow. Sam to wymyśliłeś, czy znałeś wcześniej?

0. Zamieniam na system binarny, mnożę pisemnie, i zamieniam z powrotem.

Liczby Lucasa wyklikane na Wikipedii :)

Ja miałem 2 fft bez liczb Lucasa, wystarczyło pomieszać trochę wzorem F_a * F_b + F_(a - 1) * F_(b - 1) = F_(a + b) i zrobić podobne jak @Maciej, tylko że w drugiej nieparzyste elementy f mnożę przez -1.

Do ludzi, którzy mają 7/10. TLE na 2a, 8f, 9f?

@Tomek Czajka - tak w skrócie, jak zmieniało się szybko(nie O(n^2)) na binarny?

Po prawdzie to nie próbowałem tego klepać, ale czy nie zadziałałoby coś takiego?

Wiadomo, że F_n = q^n - (1/q)^n, gdzie q = 1+sqrt(5)/2, jeszcze razy jakaś nieistotna stała. Ale w takim razie można zapisać liczbę w systemie Fibonacciego jako W(q)-W(1/q), gdzie W jest wielomianem. Co jest równoważne W*(q) / q^n, gdzie W* jest wielomianem, który ma najpierw współczynniki W, a potem te same w odwrotnej kolejności.
No to pomnożenie dwóch takich wielomianów da się zrobić jednym FFT. A potem jeszcze trzeba wrócić z powrotem do systemu Fibonacciego - ale jeśli się nie mylę, iloczyn znowu będzie wielomianem "palindromicznym", więc powrót będzie bardzo łatwy.

@Lech Duraj: Robię mniej więcej w ten sposób właśnie. Korzystamy z tego, że sqrt(5)*F_n = x^n - (-x)^(-n), gdzie x to złoty podział. Zapisujemy liczby A i B używając tego jako wielomiany P i Q, t. że A*sqrt(5) = P(phi) i B*sqrt(5) = Q(phi). Będą one "palindromiczne" z tym, że przy ujemnych wykładnikach mamy przemnożenie przez +-1. Po wymnożeniu ich używając FFT dostajemy wielomian PQ, który spełnia A*B*5 = PQ(phi). Dzielimy PQ przez "sqrt(5)", czyli wielomian x^2 - x^(-2) i otrzymujemy A*B*sqrt(5). Jeśli "dobrze" zrobimy to dzielenie to dostaniemy znów "palindromiczny" wielomian i żeby wrócić do postaci Fibonacciego wystarczy wziąć współczynniki przy dodatnich wykładnikach.

1. Modyfikuję reprezentację Fibonacciego (Zeckendorfa) tak żeby jedyne niezerowe współczynniki były na pozycjach F0, F1, F40, F41, F80, F81, itd.
2. Teraz obliczam binarnie te liczby Fibonacciego i dodaję odpowiednie wielokrotności.
3. Mnożę binarnie (najprostszym algorytmem).
4. Dzielę przez ..., F120, F80, F40, F0, otrzymując reprezentację w której niezerowe współczynniki są na pozycjach F0, F40, F80, F120, ...
5. Naprawiam reprezentację tak żeby były same jedynki oddzielone zerami, robiąc to samo co w niebieskiej książeczce po dodawaniu ale na wielokrotnościach potęg dwójki, zaczynając od najwiekszej.

Krok 1 jest w czasie O(n), kroki 2,3,4 w czasie O(n^2/w^2) (gdzie w=32 to liczba bitów w słowach komputera), a krok 5 w czasie O(nw). Razem O(n^2/w^2) (o ile n > w^3). Zauważmy że to jest o(n^2), bo log n < w (skoro n da się reprezentować w zmiennej), więc O(n^2/w^2) = O(n^2 / log^2 n).

Można szybciej zamieniać na system binarny. W publikacji "On the Complexity of Fibonacci Coding" jest opisany algorytm działający w czasie O(M(n) lg n) zamiany na system binarny i w drugą stronę, gdzie M(n) to czas mnożenia liczb w zapisie binarnym.