CJam (69 bajtów)
]qi:X,{1e|,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/z
Demo online
Wyjaśnienie
Podstawową ideą jest wdrożenie funkcji generowania opisanej w OEIS. Wejście to paskudny przypadek specjalny, ale ostatnie poprawki, które wprowadziłem, zakończyły się produkcją - 10−1 dla tego przypadku, więc (dla wartości bezwzględnej) porządkuje to. To najdziwniejsza sztuczka tutaj.z
.*:+ powtarza się trzy razy i wygląda na to, że zapisałby bajt, jeśli zostałby wyodrębniony jako {.*:+}:F~ . To jednak zrywa ze specjalnym przypadkiem , ponieważ w ogóle nie wykonuje pętli zewnętrznej.0
Używamy pomocniczej funkcji generującej dla A000081 , której warunki mają powtarzalność
a[0] = 0
a[1] = 1
For n >= 1, a[n+1] = (sum_{k=1}^n a[n-k+1] * sum_{d|k} d * a[d]) / n
Jestem pewien, że niektóre języki mają wbudowane odwrotne przekształcenie Mobiusa , ale CJam nie; najlepszym rozwiązaniem znalazłem jest budowanie tablicy odwzorowania d do , a następnie wykonać mnożenie punktowo użyciu . Zauważ, że tutaj wygodnie jest zbudować wartość początkową od indeksu 1, ponieważ chcemy uniknąć dzielenia przez zero podczas ustawiania wag. Należy również zauważyć, że jeśli dwie tablice dostarczone do operacji punktowej nie są tej samej długości, wówczas wartości z dłuższej pozostają niezmienione: dlatego musimy przyjąć pierwsze k wyrażeń∑d∣kd×a[d]dk % d == 0 ? d : 0a.*ak lub ustaw tablicę wag w górę do n . Ten ostatni wydaje się krótszy. Więc ta odwrotna transformacja Möbiusa odpowiadaanN\f{1$%!*}W$.*:+
Jeżeli nazywamy wyniku odwrotnego przekształcenia Möbiusa M, mamy
a[n+1]=1n∑k=1na[n−k+1]×M[k]
aM1nn+1a od 1 zamiast 0. Mamy teraz stanowiły
qi:X,{ ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/
Punkt pomocniczej funkcji generującej jest określony przez sekcję formuły A000055:
G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2,
where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.
a
[x=0]+a[x]+12(a[x/2]−∑i=0na[i]×a[n−i])
a[x/2]x otrzymujemy 0. Najkrótsza droga Znalazłem na to jest, aby napompować zerami ( 1,*), a następnie podjąć elementu X-tym ( X=).
0\+a[0]=0X=0W\+−2a[x]+∑ni=0a[i]×a[n−i]2a[x]
Więc wyjaśniliśmy
qi:X,{ ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/
1]N=1
1]qi:X,1>{ ... }/
X=0a[-1 1]0[x=0] ). Naprawiliśmy to dla trzech znaków albo jako finał, X!+albo przy użyciu standardowej techniki „rezerwowej” jako 1e|.
a1N=0
]qi:X,{ ... /+}/
oczywiście daje podział przez zero. Ale jeśli spróbujemy
]qi:X,{1e| ... /+}/
to działa. Dostajemy
e# Stack: [] 0
1e| e# Stack: [] 1
,:):N e# Stack: [] [1]
{ e# We only execute this loop once
N\f{1$%!*} e# 1 divides 1, so stack: [] [1]
W$.* e# Remember: if the two arrays supplied to the pointwise operation
e# are not the same length then the values from the longer one are
e# left untouched. Stack: [] [1]
:+ e# Fold over a singleton. Stack: [] 1
}% e# And that was a map, so stack: [] [1]
1$W%.*:+ e# Another [1] [] .*:+, giving the same result: 1
N,/ e# 1 / 1 = 1
+ e# And we append 1 to a giving [1]
co daje dokładnie taką wartość, jakiej potrzebujemy.
X=0−1[-1](−1−12(−1×−1))=−101−11z
