English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [DRZ] Rozwiazanie
Jak ktos sie chce pochwalic, to jestem bardzo ciekawy rozwiazania do drzew rozpinajacych.
Łatwe O(n^3) to przyłożyć twierdzeniem Kirchhoffa (https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem).
Też chętnie posłucham jak komuś się udało coś mądrzejszego wymyśleć.
Też chętnie posłucham jak komuś się udało coś mądrzejszego wymyśleć.
Owszem korzystamy z Kirchoffa
Pierwszy krok: mając tą macierz chcemy umieć szybko pomnożyć przez nią wektor, zauważamy, że jak dla każdego d <= zakres weźmiemy wszystkie indeksy podzielne przez d i dla każdej komórki na przecięciu wiersza i kolumny z tego zbioru dodamy -phi(d), to w komórce i,j dodamy łącznie sumę po d dzielących gcd(a_i, a_j) z -phi(d), czyli -gcd(a_i,a_j), czyli dostajemy to, co trzeba z dokładnością do wyrazów na przekątnej, tłumacząc na mnożenie wektora przez macierz: dla każdego d bierzemy sumę wyrazów na indeksach takich, że d dzieli a_i, mnożymy przez -phi(d) i dodajemy wynik do tych samych indeksów w wynikowym wektorze a na koniec dla każdego indeksu dodajemy w wynikowym wektorze wejściową wartość na tym samym indeksie razy różnicę między tym co jest w macierzy na przekątnej a tym, co powinno być. Tu jest jeszcze jeden haczyk, jak napiszemy to tak jak powiedziałem, to jest n * maksymalna liczba dzielników, czyli trochę za wolno, trzeba najpierw pogrupować takie same wartości a_i i zostawić tylko sumę tych elementów wektora, odpalić całą tą procedurę i na koniec każdy wyraz zastąpić przez n kopii, to wyjdzie suma po *różnych* liczbach liczb ich dzielników, czyli zakres * log(zakres)
To teraz druga część mając macierz przez którą umiemy szybko mnożyć obliczyć jej wyznacznik, brzmi bardzo standardowo, więc się zdziwiłem, że nic nie mogłem na ten temat znaleźć (jak ktoś kojarzy jakieś źródło, które potencjalnie robi prościej to będę wdzięczny za linka), ja zrobiłem tak:
Najpierw wylosowałem dla każdego wiersza losową stałą i przełożyłem cały wiersz przez nią (tłumacząc na obliczanie przekształcenia najpierw pomnożyłem każdy element wektora przez odpowiadającą mu stałą) i na koniec otrzymany wyznacznik podzielę przez iloczyn tych stałych, zaraz się okaże dlaczego tak, następnie biorę dwa losowe wektory u, v i liczę u^T(A^k)v dla k od 0 do 2n+2 i wrzucam to w Masseya (https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm), to co Massey mi zwróci to najkrótszy możliwy ciąg a_i taki, że \sigma a_iu^T(A^k)v = 0, czyli u^T(\sigma a_iA^k)v = 0, u i v było losowe, więc praktycznie na pewno jest to po prostu minimalny ciąg taki, że \sigma a_iA^k = 0, czyli wielomian minimalny macierzy, teraz wielomian minimalny może się różnić od wielomianu charakterystycznego tylko jak macierz ma wielokrotne wartości własne, jako że wylosowałem te stałe dla wierszy, to raczej tak się nie stanie, więc wyznacznik to po prostu wyraz wolny*(-1)^{n-1}, jedyny wyjątek to jak macierz od razu miała rząd mniejszy o co najmniej 2 od liczby wierszy, wtedy przez co jej nie przemnożę, to nadal ma podwójną wartość własną 0, więc doifowałem, że jak Massey znajdzie krótszą rekurencję, to wypisuję 0 (inb4: wyznacznik liczy drzewa rozpinające, a wiemy że co najmniej jedno istnieje, tak, ale to nie znaczy, że reszta z dzielenia przez 10^9+7 też jest niezerowa, nie wiem, czy był na to test, ale podejrzewam, że da się taki ułożyć)
Jak chcemy jakoś udowodnić, że faktycznie nie będzie tych wielokrotnych wartości własnych, to żeby tak było, to wielomian charakterystyczny musi mieć pierwiastki wielokrotne, czyli musi mieć jakiś wspólny pierwiastek ze swoją pochodną (jak jesteśmy w ciele skończonym, gdzie nie ma pojęcia granicy dalej możemy zdefiniować pochodną wielomianu https://en.wikipedia.org/wiki/Formal_derivative i dalej ma ona własności typu (fg)'=f'g+fg' i z tego wyprowadzamy, że p^2 | f wtedy i tylko wtedy gdy p | f i p | f', czyli f i f' mają wspólny dzielnik), czyli ich https://en.wikipedia.org/wiki/Resultant jest równa 0, resultant to wielomian stopnia O(n^2) od tych współczynników dla wierszy, czyli jeśli tylko istnieją jakieś parametry (i to jest fragment który nie wiem jak zrobić) dla których jest niezerowa, to z lematu Schwartza-Zippela prawdopodobieństwo, że wyjdzie 0 jest co najwyżej O(n^2/p), czyli bardzo mało
I jeszcze na koniec jak n=1, to de facto liczymy wyznacznik macierzy 0x0, jakby chcieć go zdefiniować, to istotnie wyjdzie 1, ale coś w kodzie się wywala, ja tego nie doifowałem i tylko 9/10 ☹️
Pierwszy krok: mając tą macierz chcemy umieć szybko pomnożyć przez nią wektor, zauważamy, że jak dla każdego d <= zakres weźmiemy wszystkie indeksy podzielne przez d i dla każdej komórki na przecięciu wiersza i kolumny z tego zbioru dodamy -phi(d), to w komórce i,j dodamy łącznie sumę po d dzielących gcd(a_i, a_j) z -phi(d), czyli -gcd(a_i,a_j), czyli dostajemy to, co trzeba z dokładnością do wyrazów na przekątnej, tłumacząc na mnożenie wektora przez macierz: dla każdego d bierzemy sumę wyrazów na indeksach takich, że d dzieli a_i, mnożymy przez -phi(d) i dodajemy wynik do tych samych indeksów w wynikowym wektorze a na koniec dla każdego indeksu dodajemy w wynikowym wektorze wejściową wartość na tym samym indeksie razy różnicę między tym co jest w macierzy na przekątnej a tym, co powinno być. Tu jest jeszcze jeden haczyk, jak napiszemy to tak jak powiedziałem, to jest n * maksymalna liczba dzielników, czyli trochę za wolno, trzeba najpierw pogrupować takie same wartości a_i i zostawić tylko sumę tych elementów wektora, odpalić całą tą procedurę i na koniec każdy wyraz zastąpić przez n kopii, to wyjdzie suma po *różnych* liczbach liczb ich dzielników, czyli zakres * log(zakres)
To teraz druga część mając macierz przez którą umiemy szybko mnożyć obliczyć jej wyznacznik, brzmi bardzo standardowo, więc się zdziwiłem, że nic nie mogłem na ten temat znaleźć (jak ktoś kojarzy jakieś źródło, które potencjalnie robi prościej to będę wdzięczny za linka), ja zrobiłem tak:
Najpierw wylosowałem dla każdego wiersza losową stałą i przełożyłem cały wiersz przez nią (tłumacząc na obliczanie przekształcenia najpierw pomnożyłem każdy element wektora przez odpowiadającą mu stałą) i na koniec otrzymany wyznacznik podzielę przez iloczyn tych stałych, zaraz się okaże dlaczego tak, następnie biorę dwa losowe wektory u, v i liczę u^T(A^k)v dla k od 0 do 2n+2 i wrzucam to w Masseya (https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm), to co Massey mi zwróci to najkrótszy możliwy ciąg a_i taki, że \sigma a_iu^T(A^k)v = 0, czyli u^T(\sigma a_iA^k)v = 0, u i v było losowe, więc praktycznie na pewno jest to po prostu minimalny ciąg taki, że \sigma a_iA^k = 0, czyli wielomian minimalny macierzy, teraz wielomian minimalny może się różnić od wielomianu charakterystycznego tylko jak macierz ma wielokrotne wartości własne, jako że wylosowałem te stałe dla wierszy, to raczej tak się nie stanie, więc wyznacznik to po prostu wyraz wolny*(-1)^{n-1}, jedyny wyjątek to jak macierz od razu miała rząd mniejszy o co najmniej 2 od liczby wierszy, wtedy przez co jej nie przemnożę, to nadal ma podwójną wartość własną 0, więc doifowałem, że jak Massey znajdzie krótszą rekurencję, to wypisuję 0 (inb4: wyznacznik liczy drzewa rozpinające, a wiemy że co najmniej jedno istnieje, tak, ale to nie znaczy, że reszta z dzielenia przez 10^9+7 też jest niezerowa, nie wiem, czy był na to test, ale podejrzewam, że da się taki ułożyć)
Jak chcemy jakoś udowodnić, że faktycznie nie będzie tych wielokrotnych wartości własnych, to żeby tak było, to wielomian charakterystyczny musi mieć pierwiastki wielokrotne, czyli musi mieć jakiś wspólny pierwiastek ze swoją pochodną (jak jesteśmy w ciele skończonym, gdzie nie ma pojęcia granicy dalej możemy zdefiniować pochodną wielomianu https://en.wikipedia.org/wiki/Formal_derivative i dalej ma ona własności typu (fg)'=f'g+fg' i z tego wyprowadzamy, że p^2 | f wtedy i tylko wtedy gdy p | f i p | f', czyli f i f' mają wspólny dzielnik), czyli ich https://en.wikipedia.org/wiki/Resultant jest równa 0, resultant to wielomian stopnia O(n^2) od tych współczynników dla wierszy, czyli jeśli tylko istnieją jakieś parametry (i to jest fragment który nie wiem jak zrobić) dla których jest niezerowa, to z lematu Schwartza-Zippela prawdopodobieństwo, że wyjdzie 0 jest co najwyżej O(n^2/p), czyli bardzo mało
I jeszcze na koniec jak n=1, to de facto liczymy wyznacznik macierzy 0x0, jakby chcieć go zdefiniować, to istotnie wyjdzie 1, ale coś w kodzie się wywala, ja tego nie doifowałem i tylko 9/10 ☹️
> to nie znaczy, że reszta z dzielenia przez 10^9+7 też jest niezerowa, nie wiem, czy był na to test, ale podejrzewam, że da się taki ułożyć
Był taki test (10j), mam z jego powodu 9/10.
Chciałem być mądry i stwierdziłem w algorytmie: jeśli mam pecha i przy bardzo nieszczęśliwym wyborze wektorów u, v i mnożników dla wierszy wyjdzie zbyt mały wielomian minimalny, to zaczynam od nowa, z nowym zestawem losowych współczynników, while(true). Zupełnie nie przeszło mi przez myśl, że wynik może być podzielny przez 10^9+7 i wtedy wielomian minimalny będzie zawsze stopnia mniejszego niż n. 🤡
Był taki test (10j), mam z jego powodu 9/10.
Chciałem być mądry i stwierdziłem w algorytmie: jeśli mam pecha i przy bardzo nieszczęśliwym wyborze wektorów u, v i mnożników dla wierszy wyjdzie zbyt mały wielomian minimalny, to zaczynam od nowa, z nowym zestawem losowych współczynników, while(true). Zupełnie nie przeszło mi przez myśl, że wynik może być podzielny przez 10^9+7 i wtedy wielomian minimalny będzie zawsze stopnia mniejszego niż n. 🤡
My solution to DRZ. It's better to read it in the markdown editor.
First we can define a $(n-1) \times (n-1) $ matrix $P$, where $P = D - G$ , where $D$ is a diagonal matrix, and $G_{i, j} = \gcd(a_i, a_j)$.
We have $G_{i,j} = \sum_{d|a_i, d|a_j} \phi(d)$, so we can define two matrix $(n-1) \times m$ matrix, where $m$ is the maximum of $a_i$. Let $U_{i, d} = \phi(d)\cdot [d|a_i], V_{i, d} = [d|a_i]$. We have $G = UV^T$.
We can apply [Matrix determinant lemma](https://en.wikipedia.org/wiki/Matrix_determinant_lemma), to compute $\det(P) = \det(D-G) = \det(I_m - V^TD^{-1} U)\det(D)$.
Let $Q = I_m - V^T D^{-1} U, Q' = V^T D^{-1} U$. $Q'_{i, j} = \sum_{i|a_k, j|a_k} \frac{1}{d_k}$. So $Q_{i, j}\neq 0$ only if $\mathrm{lcm}(i,j) \leq m$. $Q$ is very sparse and has a special structure.
So we can use Gaussian elimination from $i = m \to 1$ to compute the determination of $Q$. It's fast due to the structure of $Q$. I guess it may be faster than $O(m^2)$.
First we can define a $(n-1) \times (n-1) $ matrix $P$, where $P = D - G$ , where $D$ is a diagonal matrix, and $G_{i, j} = \gcd(a_i, a_j)$.
We have $G_{i,j} = \sum_{d|a_i, d|a_j} \phi(d)$, so we can define two matrix $(n-1) \times m$ matrix, where $m$ is the maximum of $a_i$. Let $U_{i, d} = \phi(d)\cdot [d|a_i], V_{i, d} = [d|a_i]$. We have $G = UV^T$.
We can apply [Matrix determinant lemma](https://en.wikipedia.org/wiki/Matrix_determinant_lemma), to compute $\det(P) = \det(D-G) = \det(I_m - V^TD^{-1} U)\det(D)$.
Let $Q = I_m - V^T D^{-1} U, Q' = V^T D^{-1} U$. $Q'_{i, j} = \sum_{i|a_k, j|a_k} \frac{1}{d_k}$. So $Q_{i, j}\neq 0$ only if $\mathrm{lcm}(i,j) \leq m$. $Q$ is very sparse and has a special structure.
So we can use Gaussian elimination from $i = m \to 1$ to compute the determination of $Q$. It's fast due to the structure of $Q$. I guess it may be faster than $O(m^2)$.