Liczba multisetów, dzięki czemu każda liczba od 1 do może być jednoznacznie wyrażona jako suma niektórych elementów multisetu

Mój problem. Biorąc pod uwagę, , chcę policzyć ważny multisets . Multiset jest ważny, jeśli$n$$S$$S$

• Suma elementów wynosi , i$S$$n$
• Każdy numer od do może być wyrażona jednoznacznie jako sumę niektórych elementów .$1$$n$$S$

Przykład. Na przykład, jeśli to są poprawne.$n=5$$\{1,1,1,1,1\}, \{1,2,2\}, \{1,1,3\}$

Jednak jest niepoprawny, ponieważ 2 może być utworzone zarówno przez i (tzn. 2 można wyrazić jako oba i ), więc drugi warunek nie obowiązuje. Podobnie 3 mogą być utworzone przez i .$S=\{1,1,1,2\}$$\{1,1\}$$\{2\}$$2=1+1$$2=2$$\{2,1\}$$\{1,1,1\}$

$S=\{1,2,4$ } jest również nieprawidłowe, ponieważ wszystkie liczby od do mogą być wykonane jednoznacznie, ale suma elementów nie wynosi .$1$$5$$S$$5$

Od dłuższego czasu próbowałem znaleźć dobry algorytm dla tego problemu, ale nie mogę go rozwiązać. Pochodzi z codechef . Widziałem niektóre z przesłanych rozwiązań, ale nadal nie mogłem zrozumieć logiki rozwiązania problemu. UWAGA: Limit czasu na pytanie wynosi 10 sekund, a$n<10^9$

W przypadku notacji jeśli , co oznacza, że występuje razy w multiset S.$S = \{(a_1, c_1), (a_2, c_2) ... \}$ $a_i<a_j$$i<j$$a_i$$c_i$

Do tej pory wyciągnąłem pewne wnioski

• Pierwszym elementem wymaganego sortowanego multisetu powinna być$1$
• Niech będzie zbiorem następujących dwóch właściwości, a następnie$S=\{1,a_2 \cdots a_k\} | a_1 \leq a_2\cdots \leq a_k$$\forall r<k \ \ a_{r+1} = a_r \text{ or } (\sum_{i=0}^ra_i) + 1$
• Niech , gdzie występuje razy, podąża za wymaganymi właściwościami, a następnie z powyższego wniosku możemy stwierdzić, że i jeśli . Dowód:S = { ( 1 , c 1 ) , ( a 2 , c 2 ) ⋯ ( a k , c k ) } | a 1 ≤ a 2 ⋯ ≤ a k a i c i ∀ i a i | n + 1 a i | a j j > i a i + 1$S=\{(1,c_1),(a_2,c_2) \cdots (a_k,c_k)\} | a_1 \leq a_2\cdots \leq a_k$$a_i$$c_i$$\forall i \ a_i|n+1$$a_i | a_j$$j > i$
  $a_{i+1} = (a_ic_i + a_i -1 ) + 1 \Rightarrow a_i | a_{i+1}$
• Rozważmy teraz tj. Wszystkie kolejne liczby po 1 będą wielokrotnością . Niech więc będzie liczbą takich multisetów możliwych, a następnie gdzie sumuję wszystkie możliwe liczby ( ). Innymi słowyS = { 1 , 1 ⋯ 1 ⏟ d - 1 , d , d ⋯ d , d m 1 , d m 1 ⋯ d m 1 , d m 2 , d m 2 ⋯ d m 2 , ⋯ } d f ( n ) f ( n ) = ∑ d | n + $S=\{ \underbrace{1,1 \cdots 1}_{d-1},d,d \cdots d,dm_1, dm_1 \cdots dm_1,dm_2, dm_2 \cdots dm_2, \cdots \}$$d$$f(n)$, d ≠ 1 f( n - ( d - 1 )d )1′s=d-1f(n-1)=g(n)=∑d| n,d≠ng(d$f(n) = \sum_{d|n+1, d\neq 1} f(\frac{n-(d-1)}{d})$$1's$$=d-1$$f(n-1)=g(n)=\sum_{d|n,d \neq n}g(d)$

Wreszcie mój problem został zredukowany do tego - znajdź w wydajny sposób, aby nie przekroczył limitu czasu.$g(n)$

Oto, co robi najszybsze rozwiązanie . Rzeczywiście oblicza twoją funkcję g ( n ) = ∑ d ∣ n d < n g ( d ) ,g ( 1 ) = 1. Biorąc pod uwagę n , uwzględniamy go (patrz poniżej), a następnie obliczamy wszystkie współczynniki (patrz poniżej) f 1 , … , f m w takiej kolejności, że f i | f j oznacza i ≤ j (właściwość P). Teraz obliczamy g według wzoru, przeglądając czynniki w podanej kolejności. Właściwość P zapewnia, że ​​obliczając g ( d ) , obliczaliśmy już g ( e ) dla wszystkich nietrywialnych czynników

Mówiąc bardziej szczegółowo, idziemy nad czynnikami w porządku, a dla każdego czynnika f I spotykamy wszystkich swoich nietrywialnych czynników o sprawdzenie, które z f 1 , ... , f I - 1 podziały f I .$f_i$$f_1,\ldots,f_{i-1}$$f_i$

Faktoring: Wstępne przetwarzanie: sporządzamy listę wszystkich liczb pierwszych poniżej 10 9 za pomocą sita Eratosthenes. Biorąc pod uwagę n , po prostu używamy podziału próbnego.$10^9$$n$

Generowanie wszystkich czynników: Odbywa się to rekurencyjnie. Załóżmy, że n = p k 1 1 ⋯ p k t t . Uruchamiamy t zagnieżdżonych pętli l 1 ∈ { 0 , … , k 1 } , … , l t ∈ { 0 , … , k t } i wyprowadzamy p l 1 1 ⋯ p l t t . Możesz udowodnić, że właściwość P jest indukcyjna.$n = p_1^{k_1} \cdots p_t^{k_t}$$t$$l_1 \in \{0,\ldots,k_1\},\ldots,l_t \in \{0,\ldots,k_t\}$$p_1^{l_1}\cdots p_t^{l_t}$

Optymalizacja: Ponieważ program działa na kilku wejściach, możemy wykorzystać memoizację, aby zaoszczędzić czas na różnych wejściach. Mamy tylko memoize małe wartości (do 10 5 ), a to pozwala nam na przechowywanie wszystkich memoized wartości w tablicy. Tablica jest inicjowana zerami, dzięki czemu możemy stwierdzić, które wartości są już znane (ponieważ wszystkie obliczone wartości są dodatnie).$10^5$

Jeśli pierwsza faktoryzacja n + 1 wynosi p k 1 1 , … , p k t t , to f ( n ) zależy tylko od ( k 1 , … , k t ) , a tak naprawdę tylko od posortowanej wersji tego wektora . Każda liczba poniżej 10 9 ma najwyżej 29 czynników pierwszych (z powtórzeniem), a ponieważ p ( 29 ) = 4565 , wydaje się, że można obliczyć $n+1$$p_1^{k_1},\ldots,p_t^{k_t}$$f(n)$$(k_1,\ldots,k_t)$$10^9$$29$$p(29)=4565$$f$(a raczej g ) dla nich wszystkich, rekurencyjnie. To rozwiązanie mogłoby być szybsze, gdyby było wiele różnych danych wejściowych; w tej chwili jest ich najwyżej 10 .$g$$10$

Możliwe jest również, że ta funkcja, odwzorowująca partycje na odpowiednie g , ma jawną formę analityczną. Na przykład g ( p k ) = 2 k - 1 , g ( p 1 … p t ) podano w A000670 , a g ( p 2 1 p 2 … p t ) podano w A005649 lub A172109 .$g$$g(p^k) = 2^{k-1}$$g(p_1\ldots p_t)$$g(p_1^2 p_2\ldots p_t)$

OK, więc masz relację powtarzalności dla g ( ⋅ ) (patrz koniec pytania).$g(\cdot)$

W tym momencie wydaje się, że naturalnym podejściem byłoby zapisanie algorytmu rekurencyjnego do obliczenia g ( n ) i zastosowanie zapamiętywania, aby nie obliczać g ( i ) więcej niż raz. Innymi słowy, obliczając g ( i ) , przechowujesz go w tabeli skrótów, która odwzorowuje i ↦ g ( i ) ; jeśli chcesz ponownie poznać g ( i ) w przyszłości, możesz to sprawdzić w tabeli skrótów.$g(n)$$g(i)$$g(i)$$i \mapsto g(i)$$g(i)$

Wymaga to faktorowania n , ale istnieją wydajne algorytmy faktorowania n, gdy n ≤ 10 9 .$n$$n$$n\le 10^9$

Możesz także poszukać sekwencji g ( 1 ) , g ( 2 ) , g ( 3 ) , g ( 4 ) , g ( 5 ) , … w Encyklopedii Sekwencji Całkowitych On-Line . Jeśli znajdziesz sekwencję w ich encyklopedii, czasem dostarczą one dodatkowych pomocnych informacji (np. Wydajnych algorytmów do obliczania sekwencji). To wprawdzie może zabrać zabawę.$g(1),g(2),g(3),g(4),g(5),\ldots$

Oto wskazówka na początek. Zastosuj standardowe algorytmy programowania dynamicznego do wyliczenia zestawu partycji liczb całkowitych i dodaj logikę, aby sprawdzić, który z nich pozwala na unikalne dokonywanie zmian poprzez iteracyjne sprawdzanie wszystkich sum, wprowadzanie zmian i weryfikowanie niepowtarzalności.

W nieco bardziej szczegółowo: Załóżmy, że masz multiset S . Biorąc pod uwagę liczbę i o wartości 1 ≤ i ≤ n , w jaki sposób można zidentyfikować podwielokrotność S, która sumuje się do i ? Jak mogłeś sprawdzić, czy ten subultiset jest wyjątkowy? Spróbuj dostosować standardowe techniki programowania dynamicznego do wprowadzania zmian . (Zobacz także to pytanie .)$S$$i$$1 \le i \le n$$S$$i$

Biorąc pod uwagę multiset S , jak możesz sprawdzić, czy spełnia on drugi warunek, tj. Czy każda liczba od 1 do n może być jednoznacznie wyrażona jako suma subultiset S (unikalny warunek zmiany)? To powinno być dość łatwe, jeśli rozwiązałeś poprzedni.$S$$n$$S$

niech P ( n ) oznacza listę multisets, które spełniają oba warunki. Jeśli znasz P ( 1 ) , P ( 2 ) , … , P ( n ) , jak możesz wykorzystać te informacje do skonstruowania P ( n + 1 ) ? Tutaj możesz chcieć dostosować standardowe techniki programowania dynamicznego do wyliczania partycji liczb całkowitych.$P(n)$$P(1), P(2), \dots, P(n)$$P(n+1)$

Oto podejście, które prawdopodobnie będzie lepsze.

Załóżmy, że S to zbiór, który spełnia oba warunki (dla n ). Jak możemy go rozszerzyć, aby uzyskać wielosekcyjny T, który ma jeszcze jeden element? Innymi słowy, w jaki sposób możemy zidentyfikować wszystkie sposoby dodania jeszcze jednego elementu do S , aby uzyskać nowy wielosekcyjny T, który spełnia oba warunki (dla niektórych n ′ )?$S$$n$$T$$S$$T$$n'$

Odpowiedź: jeśli x można wyrazić jako sumę niektórych elementów S , to nie ma sensu dodawać go do S : spowodowałoby to, że T naruszyłby warunek wyjątkowości. Możemy więc wyliczyć wszystkie liczby całkowite x , których nie można wyrazić jako sumę niektórych elementów S ; każdy z nich jest czymś, co można potencjalnie dodać do S, aby uzyskać nowy wielosetowy T , który spełni oba warunki (dla niektórych innych n ).$x$$S$$S$$T$$x$$S$$S$$T$$n$

Ponadto możliwe jest wyliczenie, które liczby całkowite mogą być wyrażone jako suma niektórych elementów S , a które nie, za pomocą programowania dynamicznego. Budujesz dwuwymiarową tablicę A [ 1 … | S | , 1 ... n ] Wartości zmiennych, w których [ i , j ] jest prawdziwe, czy nie jest sposobem wyrażania całkowitą j jako sumę niektóre z pierwszych ı elementów S (tylko pierwszy ı elementów S kwalifikują się do być użyte; gdzie $S$$A[1\ldots |S|,1 \ldots n]$$A[i,j]$$j$$i$$S$$i$$S$$S$zostały sortowane, więc S = { y 1 , y 2 , ... , s k } , a s 1 ≤ s 2 ≤ ⋯ ≤ y k ). Zauważ, że A [ i , j ] może być obliczane przy użyciu wartości A [ 1 … i - 1 , 1 … j - 1 ] : w szczególności A [ i , j $S=\{s_1,s_2,\dots,s_k\}$$s_1\le s_2 \le \cdots \le s_k$$A[i,j]$$A[1\ldots i-1, 1\ldots j-1]$= A [ i - 1 , j ] ∨ A [ i - 1 , j - s i ] jeśli j > s i lub A [ i , j ] = A [ i - 1 , j ] w przeciwnym razie. To pozwala nam zidentyfikować wszystkie numery, które są kandydatami do doliczone do S .$A[i,j] = A[i-1,j] \lor A[i-1,j-s_i]$$j>s_i$$A[i,j]=A[i-1,j]$$S$

Następnie dla każdego rozszerzenia kandydat T z S (otrzymanego przez dodanie jednego elementu do S ), chcemy sprawdzić, czy T spełnia oba warunki. Niech N oznacza sumę składników S , a n ' suma elementów T . Musimy sprawdzić, czy każdą liczbę całkowitą z zakresu n + 1 , n + 2 , … , n ′ można wyrazić jako sumę niektórych elementów $T$$S$$S$$T$$n$$S$$n'$$T$$n+1,n+2,\ldots,n'$$T$. To również można rozwiązać za pomocą programowania dynamicznego, przy użyciu standardowych algorytmów do wprowadzania zmian. (W rzeczywistości, jeśli nadal masz tablicę A wspomnianą powyżej, możesz łatwo ją trochę rozszerzyć, aby rozwiązać ten problem: robimy ją tablicą A [ 1 … | T | , 1 … n ′ ] , nadal wypełniamy wszystkie dodatkowych wpisów i upewnij się, że A [ | T | , n + 1 ] , A [ | T | , n + 2 ] $A$$A[1\ldots |T|, 1 \ldots n']$… , A [ | T | , n ′ ] są prawdziwe.) Teraz możemy wyliczyć wszystkie multisety T, które rozciągają S o jeden element i które spełniają oba warunki.$A[|T|,n+1], A[|T|,n+2], \ldots, A[|T|,n']$$T$$S$

To natychmiast sugeruje algorytm do wyliczenia wszystkich multisetów S, które spełniają twój warunek, dla wszystkich n do pewnego związanego, powiedzmy n ≤ 20 . Będziemy mieli tablicę P [ 1 … 20 ] , w której P [ 5 ] przechowuje wszystkie multisety S, które sumują się do 5, i ogólnie P [ n ] przechowuje zbiór wszystkich multisetów S, które sumują się do n .$S$$n$$n\le 20$$P[1\ldots 20]$$P[5]$$S$$P[n]$$S$$n$

Następnie możemy iteracyjnie wypełnić P [ n ] . Zacznij od ustawienia P [ 1 ] tak, aby zawierał tylko jeden multiset { 1 } . Następnie, dla każdego n (liczy się od 1 do 20), dla każdego S ∈ p [ n ] , wyliczyć wszystkich możliwych rozszerzeń T z S (z wykorzystaniem technik wyżej), niech n " oznacza sumę elementów T , i wstawić T do P [ n ′$P[n]$$P[1]$$\{1\}$$n$$S \in P[n]$$T$$S$$n'$$T$$T$$P[n']$jeśli nie jest już obecny, a jeśli n ' ≤ 20 .$n' \le 20$

To powinno być całkiem wykonalne. Powodzenia! Baw się dobrze! Przepracowanie szczegółów będzie dobrym ćwiczeniem do nauki w programowaniu dynamicznym.