Treść zadania można znaleźć np tu: http://main.edu.pl/pl/archive/oi/10/tro
Jeżeli to możliwe chciałbym prosić o wskazówki dotyczące rozwiązania zadania przy podanych ograniczeniach .(Dotychczas udało mi sie tylko napisać algorytm o złożoności wykładniczej, który służy chyba tylko do sprawdzania wyników dla większych danych testowych) Nie chcę zaglądać do rozwiązań, bo chciałbym sam wymyślić jakiś sensowny algorytm, ale fajnie byłoby gdyby ktoś naprowadził na właściwy kierunek
Na moje oko to musisz to rozwiazać po prostu matematycznie. Tzn wyznaczyć wzór na współczynnik "Ci" w zależności od N i od I
no właśnie, myślałem żeby korzystać tu z dwumianu Newtona, ale liczba operacji potrzebnych do obliczenia współczynnika bezpośrednio będzie pewnie i tak wykładnicza w stosunku do rozmiaru danych (co dla większego n okropnie spowalnia program), chyba że można jakoś prościej to obliczyć. Oczywiście wszystkie współczynniki możemy zastępować resztą z dzielenia przez 3 , ale to i tak nie zmienia liczby operacji, jednak nie działamy na dużych liczbach.
Spamiętywanie kolejnych wyników w tablicy raczej też bez sensu, bo tablica o takim rozmiarze przekracza duuużo rozmiar dostepnej pamięci ;(
Jaki znów dwumian newtona? Ja mówie o rozpisaniu sobie kilku przypadków i poszukaniu matematycznej zależności między współczynnikami dla kolejnych n oraz i.
Rozpisałem sobie kilka przypadków i owszem można się dopatrzyć zależności na wspolczynnik przy dowolnym n, ale nie kiedy i jest bliskie jakiemuś dużemu n.(przynajmniej ja nie potrafię albo nie widzę czegoś ;/) .I jak mamy te 2n wyrazów rozwinięcia to sobie można te współczynniki obliczyc do n-tego bo potem wszystko odwrotnie można przepisać bo sie powtarz, to takie moje spostrzeżenie z ostatniej chwili.
lol, to że wystarczy liczyc połowę współczynników bo się powtarzają to jest przecież oczywiste. Jeśli musiałeś nad tym myśleć to ja nie wiem czy OI jest dla ciebie...
To że polowe trzeba obliczyć to wiadomo, ale miałem na myśli, że nie da się wyznaczyć wzoru na podstawie kilku pierwszych przypadków na współczynnik/reszte przy dużym n oraz i. A nie pisałem nigdzie ,że zamierzam startować w OIu, zadania robię dla przyjemności :)
@feliksss nie da się, czy ty nie znalazłeś sposobu? A jak spróbujesz wyznaczyć taki wzór dla dla reszt z dzielenia przez 3 a nie dla samych współczynników?
Jedyny pomysł jaki mam to prymitywna funkcja rekurencyjna, dodatkowo wielokrotnie wylicza te same wartości. Wiem, niezbyt to mądre. Jakiś zarys sprytniejszego pomysłu?
niech program "rozpisuje" sobie to po kolei: (1+x+x²)3 = 1*(1+x+x²)3 = (1+x+x²)(1+x+x²)2 = (1+2x+3x²+2x³+x4)(1+x+x²)=...
http://ideone.com/oCAUZ
Aby pomnożyć wielomian przez wielomian tworzy się wektory wspolczynnikow
i uzupelnia do najwiekszej potegi
np (x^2 + 2x + 1)*(x^3 +1)
[1 0 0 1] -(x^3 +1)
[0 1 2 1] -(x^2 +2x + 1)
monzysz te dwa wektory tak jakbys mnozyl zwykle liczby
[1 0 0 1]
*[0 1 2 1]
----------------
1 0 0 1
2 0 0 2
1 0 0 1
+ 0 0 0 0
---------------- na koncu sumujesz
0 1 2 1 1 2 1
wynik:
x^5 + 2x^4 + x^3 + x^2 + 2x + 1
Skoro juz wiesz jak sie mnozy dwa wielomiany to wiesz jek sie mnozy 3 i wiecej przez siebie
(n-ta potega to tylko n-ta iteracja petli)
Dziwne, że nikt na tym forum na to nie wpadł tylko jakieś dziwne konstrukcje tworzycie.
Prawdopodobnie dlatego, że każdy na forum wie, że przy wielomianach podniesionych do wartości rzędu 10^15 takie rozwiązania nie przejdą.
Dokladnie. Proponuję oszacować sobie czas wykonania takiego programu dla n rzędu 10^15 i 400mln operacji na sek :). Sprytna rekurencja pewnie daje radę, ale żeby na nią wpaść trzeba sobie kilkanaście pierwszych przypadków dla reszt rozpisać.(Przynajmniej ja wcześniej nie widziałem zależności) O(log n) to chyba maks. ograniczenie. (Dla pojedynczego testu),
to co chcesz obliczyć to "trinomial coefficient". to nie jest takie proste jak by Ci się mogło wydawać. imho najlepiej było by wyrazić t.c. w postaci sumy iloczynów symboli newtona ("binomial coefficient") http://bit.ly/NMXhmP i skorzystać z "lucas' theorem", aby prosto obliczyć wartość s.n. modulo liczba pierwsza (3). całość łączymy pamiętając o podstawowych prawach arytmetyki modulo: (a+b) mod n = (a mod n + b mod n) mod n i analogicznie dla mnożenia. powodzenia przy O(log n), chyba że ktoś znajdzie jakiś prosty wzór analogiczny do obliczenia wartości s.n. mod 2 który obliczamy błyskawicznie operacjami bitowymi.
co do sprytnej rekurencji to można zauważyć pewną zależność... dla pewnych n wszystkie współczynniki c mod 3 przyjmują wartość 1. są to n z ciągu http://oeis.org/A003462
zamiast jak w standardowej rekurencji zmniejszać n o 1 aż dojdziemy do n == 0, można wykorzystać tą wiedzę i od razu wchodzić głębiej:
F(n,k) = F(n-1, k) + F(n-1, k-1) + F(n-1, k-2) = F(n-4, k) + ... + F(n-4, k-8) = F(n-13, k) + ... + F(n-13, k-26) = ... mod 3
http://ideone.com/RARln tu moja implementacja
Wczoraj też wydawało mi si, żę się nie da O(log n) ale psikus, bo można. Cały bajer zadania polega na tym, że my potrzebujemy współczynnika modulo 3. I to bardzo sprawę upraszcza.