For a fixed \(n\), define
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}.$$
The quantity \(D(n)\) is the maximum size of a subset \(S\subseteq V\) such that the map \(f_n\) sends every selected element to a distinct unselected element. Equivalently, the set must satisfy
$$f_n(S)\cap S=\varnothing \qquad \text{and} \qquad |f_n(S)|=|S|.$$
Since \(V\) is finite, the second condition simply says that \(f_n\) is injective on \(S\). The overall Project Euler task is to evaluate
$$\sum_{i=1}^{100} D(100000+i).$$
The map \(f_n\) naturally defines a functional graph, and the whole problem becomes a graph optimization problem with a very local constraint.
Draw one directed edge from each residue \(x\in V\) to \(f_n(x)\). Every vertex has out-degree exactly \(1\), so each connected component of the graph consists of one directed cycle together with rooted in-trees feeding into that cycle.
Let
$$P(u)=\{x\in V:f_n(x)=u\}$$
be the set of predecessors of \(u\). The drifting condition is equivalent to the local rule
$$|S\cap (\{u\}\cup P(u))|\le 1 \qquad \text{for every } u\in V.$$
Indeed, if two chosen elements had the same image \(u\), then two members of \(P(u)\) would lie in \(S\). If a chosen element mapped to another chosen element, then both a vertex and one of its predecessors would lie in \(S\). So the global condition reduces to a one-vertex-at-a-time exclusion rule.
Repeatedly remove vertices of in-degree \(0\). This standard indegree-peeling process deletes every tree vertex and leaves exactly the directed cycles. The removed vertices appear in an order in which all predecessors of a peeled vertex are processed before the vertex itself, which is exactly what the dynamic program needs.
After this peeling step, each remaining cycle vertex becomes the root of an attached incoming tree formed by the removed vertices that eventually flow into it.
Fix a peeled vertex \(u\), and let \(C(u)\) be its peeled predecessors, meaning the tree vertices \(c\) with \(f_n(c)=u\). Define:
$$A_u=\text{best value in the tree of }u\text{ when }u\notin S,$$
$$B_u=\text{best value in the tree of }u\text{ when }u\in S.$$
If \(u\) is selected, then none of its predecessors may be selected, because they would either share the image \(u\) or land inside the chosen set. Therefore
$$B_u=1+\sum_{c\in C(u)} A_c.$$
If \(u\) is not selected, then at most one predecessor may be selected, because all predecessors map to the same target \(u\). So we may take the baseline in which every predecessor stays unselected, and optionally upgrade one predecessor to its selected state:
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
This recurrence is the key tree formula used by all three implementations.
Now consider one directed cycle \(c_0,c_1,\dots,c_{k-1}\) with
$$f_n(c_i)=c_{i+1} \quad \text{for } i \pmod{k}.$$
For each cycle vertex \(c_i\), let \(T_i\) be the non-cycle predecessors attached to it. Their tree contribution can be summarized by two numbers:
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right).$$
Here \(a_i\) is the baseline if all attached predecessors stay unselected, and \(g_i\) is the best optional bonus from selecting one attached predecessor. If we decide not to select any cycle vertex at all, then the entire component contributes
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i).$$
Suppose we now decide to select the cycle vertex \(c_i\). Relative to the baseline \(C_0\), this has three effects:
$$+1 \text{ for selecting } c_i,$$
$$-g_i \text{ because no attached predecessor of } c_i \text{ may be selected},$$
$$-g_{i+1} \text{ because } c_i \text{ already occupies the unique chosen predecessor slot into } c_{i+1}.$$
So the net weight of selecting \(c_i\) is
$$w_i=1-g_i-g_{i+1}.$$
Also, two adjacent cycle vertices cannot both be selected: if \(c_i\in S\), then \(f_n(c_i)=c_{i+1}\notin S\). Hence we must choose a maximum-weight independent set on a cycle with vertex weights \(w_i\).
For a path, the usual recurrence is
$$P_j=\max(P_{j-1},P_{j-2}+u_j),$$
which computes the best non-adjacent sum of weights \(u_j\). For a cycle of length \(k>1\), split into two cases:
$$\text{Case A: do not select } c_0,$$
$$\text{Case B: select } c_0 \text{ and therefore forbid } c_1 \text{ and } c_{k-1}.$$
This yields
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr).$$
The contribution of the whole component is then
$$D_{\text{comp}}=C_0+\text{best}.$$
If \(k=1\), the cycle is a self-loop, so the cycle vertex maps to itself and can never be selected. In that special case the contribution is just \(a_0+g_0\).
For \(n=10\), the map is
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9.$$
So there are two cycle components: the 2-cycle \(1\leftrightarrow 3\), and the self-loop \(9\mapsto 9\).
The attached tree leaves are \(\{0,2,5,7,8\}\) into \(1\), \(\{6\}\) into \(3\), and \(\{4\}\) into \(9\). Every such leaf has
$$A=0,\qquad B=1.$$
For the cycle \(1\leftrightarrow 3\), this gives
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1,$$
so
$$C_0=(0+1)+(0+1)=2,$$
and both cycle weights are
$$w=1-1-1=-1.$$
Thus the best cycle correction is \(0\), and this component contributes \(2\).
For the self-loop at \(9\), we have \(a=0\) and \(g=1\), and the loop vertex itself cannot be selected. So that component contributes \(1\).
Therefore
$$D(10)=2+1=3.$$
One optimal subset is \(\{0,4,6\}\), whose image is \(\{1,9,3\}\); the image is disjoint from the subset and all three images are distinct.
The C++, Python, and Java implementations all follow the same pipeline.
First, they build the successor of every residue \(x\), count in-degrees, and store reverse predecessor lists. Second, they run indegree peeling with a queue, which identifies the tree vertices and leaves only the cycle vertices unpeeled.
Next, they process the peeled vertices in queue order and compute the two tree-DP states described above. Once that is done, every cycle vertex already knows the optimal contribution of its attached trees.
Finally, they walk through each remaining directed cycle, assemble the baseline \(a_i+g_i\) values, translate the cycle choice into a maximum-weight independent-set problem, solve the two path cases, and add the resulting component contribution to \(D(n)\).
After computing one \(D(n)\), the implementation repeats the procedure for \(n=100001,100002,\dots,100100\) and sums the answers.
For one value of \(n\), graph construction touches each vertex once and creates exactly one outgoing edge per vertex, so it costs \(O(n)\) time and \(O(n)\) memory. Indegree peeling is also \(O(n)\), because every vertex enters the queue at most once and every edge is examined a constant number of times.
The tree dynamic program processes each peeled predecessor relation once, and the cycle stage visits every unpeeled vertex exactly once. Therefore the total cost for a single \(D(n)\) remains
$$O(n)\text{ time and }O(n)\text{ memory.}$$
The final Project Euler sum covers 100 consecutive values of \(n\), so the full runtime is linear in the total number of processed residues across those 100 instances.
Für ein festes \(n\) definieren wir
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}.$$
Die Größe \(D(n)\) ist die maximale Mächtigkeit einer Teilmenge \(S\subseteq V\), so dass \(f_n\) jedes gewählte Element auf ein anderes, nicht gewähltes Ziel abbildet und dabei auf \(S\) injektiv ist. Äquivalent dazu gelten
$$f_n(S)\cap S=\varnothing \qquad \text{und} \qquad |f_n(S)|=|S|.$$
Da \(V\) endlich ist, bedeutet die zweite Bedingung genau, dass keine zwei Elemente aus \(S\) denselben Bildwert haben. Gesucht ist schließlich
$$\sum_{i=1}^{100} D(100000+i).$$
Die Kongruenz erzeugt einen funktionalen Graphen. Dadurch lässt sich die Aufgabe in Baumteile und Zyklusanteile zerlegen.
Zu jedem Rest \(x\in V\) zeichnen wir eine gerichtete Kante \(x\to f_n(x)\). Jeder Knoten hat Ausgrad \(1\), also besteht jede Zusammenhangskomponente aus genau einem gerichteten Zyklus mit eingehängten Wurzelbäumen.
Schreibe
$$P(u)=\{x\in V:f_n(x)=u\}$$
für die Vorgängermenge von \(u\). Dann ist die Drift-Bedingung äquivalent zu
$$|S\cap (\{u\}\cup P(u))|\le 1 \qquad \text{für alle } u\in V.$$
Damit ist sofort klar: Man darf nie zwei gewählte Elemente mit demselben Bild haben, und man darf nie gleichzeitig einen Knoten und einen seiner Vorgänger wählen.
Entfernt man wiederholt Knoten mit Eingangsgrad \(0\), verschwinden genau die Baumteile. Übrig bleiben exakt die gerichteten Zyklen. Gleichzeitig entsteht eine Verarbeitungsreihenfolge, in der alle Vorgänger eines entfernten Knotens schon bekannt sind, bevor der Knoten selbst behandelt wird.
Jeder verbleibende Zyklusknoten ist danach die Wurzel eines eingehenden Baums aus bereits entfernten Knoten.
Sei \(u\) ein entfernter Knoten und \(C(u)\) die Menge seiner ebenfalls entfernten Vorgänger mit \(f_n(c)=u\). Wir definieren zwei Zustände:
$$A_u=\text{optimale Anzahl im Baum von }u\text{, falls }u\notin S,$$
$$B_u=\text{optimale Anzahl im Baum von }u\text{, falls }u\in S.$$
Wird \(u\) gewählt, darf keiner seiner Vorgänger gewählt werden. Also
$$B_u=1+\sum_{c\in C(u)} A_c.$$
Wird \(u\) nicht gewählt, darf höchstens ein Vorgänger gewählt werden, weil alle auf dasselbe Ziel \(u\) zeigen. Daher
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
Genau diese Rekursion berechnet den optimalen Beitrag jedes Baumknotens.
Betrachte nun einen Zyklus \(c_0,c_1,\dots,c_{k-1}\) mit
$$f_n(c_i)=c_{i+1} \quad \text{für } i \pmod{k}.$$
Sei \(T_i\) die Menge der nichtzyklischen Vorgänger von \(c_i\). Deren gesamter Baumbeitrag lässt sich durch
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right)$$
zusammenfassen. Wenn kein Zyklusknoten gewählt wird, erhält man als Baseline
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i).$$
Hier steht \(g_i\) für den besten optionalen Gewinn, den man durch die Wahl eines einzigen angehängten Vorgängers von \(c_i\) erzielen kann.
Wählt man den Zyklusknoten \(c_i\), dann ändert sich die Baseline um
$$+1 \text{ für die Wahl von } c_i,$$
$$-g_i \text{, weil dann kein angehängter Vorgänger von } c_i \text{ gewählt werden darf},$$
$$-g_{i+1} \text{, weil } c_i \text{ bereits den einzigen gewählten Vorgänger von } c_{i+1} \text{ darstellt}.$$
Der Nettoeffekt ist also
$$w_i=1-g_i-g_{i+1}.$$
Außerdem dürfen nie zwei benachbarte Zyklusknoten gleichzeitig gewählt werden, denn aus \(c_i\in S\) folgt \(f_n(c_i)=c_{i+1}\notin S\). Also suchen wir eine maximale gewichtete unabhängige Menge auf einem Zyklus.
Für einen Pfad genügt die Standardrekursion
$$P_j=\max(P_{j-1},P_{j-2}+u_j).$$
Für den Zyklus der Länge \(k>1\) trennen wir zwei Fälle:
$$\text{Fall A: } c_0 \text{ wird nicht gewählt},$$
$$\text{Fall B: } c_0 \text{ wird gewählt, also sind } c_1 \text{ und } c_{k-1} \text{ verboten}.$$
Damit ist
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr).$$
Der Beitrag der ganzen Komponente lautet
$$D_{\text{comp}}=C_0+\text{best}.$$
Bei einem Selbstloop (\(k=1\)) kann der Zyklusknoten nie gewählt werden, weil er auf sich selbst zeigt. Dann bleibt nur \(a_0+g_0\).
Für \(n=10\) gilt
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9.$$
Damit entstehen die Zykluskomponenten \(1\leftrightarrow 3\) und \(9\mapsto 9\).
Die Blätter \(\{0,2,5,7,8\}\) führen in \(1\), \(\{6\}\) führt in \(3\), und \(\{4\}\) führt in \(9\). Jedes dieser Blätter hat
$$A=0,\qquad B=1.$$
Für den 2-Zyklus erhält man
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1,$$
also
$$C_0=2$$
und
$$w=1-1-1=-1$$
für beide Zyklusgewichte. Die beste Zykluskorrektur ist daher \(0\), und die Komponente trägt \(2\) bei.
Beim Selbstloop \(9\mapsto 9\) gilt \(a=0\) und \(g=1\); der Knoten \(9\) selbst ist verboten. Also kommt dort noch \(1\) hinzu.
Somit
$$D(10)=2+1=3.$$
Eine optimale Menge ist zum Beispiel \(\{0,4,6\}\).
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf.
Zuerst berechnen sie für jeden Rest seinen Nachfolger, die Eingangsgrade und die Rückwärtslisten der Vorgänger. Danach folgt das Peeling über eine Queue, wodurch alle Baumknoten markiert und alle Zyklusknoten übrig gelassen werden.
Anschließend werden die entfernten Knoten in Peeling-Reihenfolge verarbeitet, um die zwei DP-Zustände jedes Baumknotens zu berechnen. Danach kennt jeder Zyklusknoten bereits den optimalen Beitrag seiner anhängenden Bäume.
Zum Schluss wird jeder Restzyklus einmal abgelaufen, in einen Basiswert plus ein gewichtetes Independent-Set-Problem umgewandelt und zum Gesamtergebnis \(D(n)\) addiert. Dieser Vorgang wird für \(n=100001\) bis \(100100\) wiederholt.
Für ein festes \(n\) werden beim Graphaufbau alle \(n\) Knoten genau einmal betrachtet, also kostet dieser Schritt \(O(n)\) Zeit und \(O(n)\) Speicher. Das Peeling ist ebenfalls linear, weil jeder Knoten höchstens einmal in die Queue gelangt.
Auch die Baum-DP und die Zyklusverarbeitung sind linear, da jede Vorgängerbeziehung und jeder Zyklusknoten nur konstant oft benutzt werden. Insgesamt ergibt sich daher für ein einzelnes \(D(n)\)
$$O(n)\text{ Zeit und }O(n)\text{ Speicher.}$$
Die abschließende Summe über 100 Werte von \(n\) bleibt damit linear in der Gesamtzahl aller verarbeiteten Reste.
Sabit bir \(n\) için
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}$$
tanımını yapalım. \(D(n)\), \(S\subseteq V\) altkümesinin alabileceği en büyük boyuttur; burada \(f_n\), seçilen her elemanı seçilmemiş ve birbirinden farklı bir görüntüye göndermelidir. Eşdeğer olarak
$$f_n(S)\cap S=\varnothing \qquad \text{ve} \qquad |f_n(S)|=|S|$$
olmalıdır. Son ifade, sonlu bir kümede \(f_n\)'in \(S\) üzerinde birebir olması demektir. Genel hedef ise
$$\sum_{i=1}^{100} D(100000+i)$$
toplamını hesaplamaktır.
Bu dönüşüm doğal olarak bir functional graph üretir. Böylece problem, ağaç parçaları ve cycle parçaları üzerinde yerel bir optimizasyona dönüşür.
Her \(x\in V\) için \(x\to f_n(x)\) yönlü kenarını çizelim. Her düğümün çıkış derecesi tam olarak \(1\) olduğu için her bağlı bileşen, tek bir yönlü cycle ve bu cycle'a akan köklü giriş ağaçlarından oluşur.
\(u\) düğümünün öncüllerini
$$P(u)=\{x\in V:f_n(x)=u\}$$
ile gösterelim. O zaman drifting koşulu şu yerel kurala eşdeğerdir:
$$|S\cap (\{u\}\cup P(u))|\le 1 \qquad \text{her } u\in V \text{ için.}$$
Yani aynı hedefe giden iki seçili eleman olamaz; ayrıca seçili bir düğüm ile onun seçili bir öncülü birlikte bulunamaz.
Giriş derecesi \(0\) olan düğümleri tekrar tekrar silersek, bütün ağaç kısımları kaybolur ve geriye yalnızca cycle düğümleri kalır. Bu peeling süreci aynı zamanda, kaldırılan bir düğüm işlenirken onun kaldırılmış öncüllerinin zaten hazır olduğu bir sıra üretir.
Böylece her cycle düğümü, kendisine bağlanan bir giriş ağacının kökü haline gelir.
\(u\) soyulmuş bir düğüm olsun ve \(C(u)\), \(f_n(c)=u\) koşulunu sağlayan soyulmuş öncülleri göstersin. İki durum tanımlayalım:
$$A_u=\text{\(u\) seçilmediğinde }u\text{ ağacındaki en iyi değer},$$
$$B_u=\text{\(u\) seçildiğinde }u\text{ ağacındaki en iyi değer}.$$
\(u\) seçilirse hiçbir öncülü seçilemez. Bu yüzden
$$B_u=1+\sum_{c\in C(u)} A_c.$$
\(u\) seçilmezse, tüm öncüller aynı hedefe baktığı için en fazla bir tanesi seçilebilir. Dolayısıyla önce hepsini seçilmemiş kabul eder, sonra istersek yalnızca birini yükseltiriz:
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
Çözümün ağaç tarafındaki temel formülü budur.
Şimdi
$$f_n(c_i)=c_{i+1} \quad \text{\(i\) mod }k$$
olan \(c_0,c_1,\dots,c_{k-1}\) cycle'ını ele alalım. \(T_i\), \(c_i\)'ye bağlanan cycle dışı öncüller olsun. Bu ağaç katkısı iki sayıyla özetlenir:
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right).$$
\(a_i\) taban katkıdır; \(g_i\) ise \(c_i\)'ye gelen ağaçta seçilebilecek en iyi tek düğümün ek kazancıdır. Eğer hiçbir cycle düğümü seçilmezse bileşenin katkısı
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i)$$
olur.
\(c_i\) cycle düğümünü seçmenin, taban durumuna göre etkisi şöyledir:
$$+1 \text{ çünkü } c_i \text{ seçildi},$$
$$-g_i \text{ çünkü } c_i \text{ seçilirse ona bağlı ağaçtan düğüm seçilemez},$$
$$-g_{i+1} \text{ çünkü } c_i,\ c_{i+1} \text{ için zaten seçili tek öncül slotunu doldurur}.$$
Bu nedenle net ağırlık
$$w_i=1-g_i-g_{i+1}$$
olur. Ayrıca yan yana iki cycle düğümü birlikte seçilemez; çünkü \(c_i\in S\) ise \(f_n(c_i)=c_{i+1}\notin S\) olmalıdır.
Böylece problem, bu ağırlıklarla bir cycle üzerinde maksimum ağırlıklı bağımsız küme problemine dönüşür. Bir path üzerinde standart geçiş
$$P_j=\max(P_{j-1},P_{j-2}+u_j)$$
şeklindedir. Cycle uzunluğu \(k>1\) ise iki durum yeterlidir:
$$\text{Durum A: } c_0 \text{ seçilmez},$$
$$\text{Durum B: } c_0 \text{ seçilir; o halde } c_1 \text{ ve } c_{k-1} \text{ yasaktır}.$$
Dolayısıyla
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr)$$
ve bileşen katkısı
$$D_{\text{comp}}=C_0+\text{best}$$
olur. \(k=1\) ise self-loop vardır; düğüm kendisine gittiği için seçilemez ve katkı sadece \(a_0+g_0\)'dır.
\(n=10\) olduğunda dönüşüm
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9$$
şeklindedir. Burada iki cycle bileşeni vardır: \(1\leftrightarrow 3\) ve \(9\mapsto 9\).
\(1\)'e gelen yapraklar \(\{0,2,5,7,8\}\), \(3\)'e gelen yaprak \(\{6\}\), \(9\)'a gelen yaprak ise \(\{4\}\)'tür. Her yaprak için
$$A=0,\qquad B=1$$
olur.
Bu yüzden 2-cycle için
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1,$$
ve dolayısıyla
$$C_0=2,\qquad w=1-1-1=-1.$$
Cycle düzeltmesi \(0\) çıkar; bu bileşen \(2\) katkı verir. Self-loop tarafında \(a=0\) ve \(g=1\) olduğundan oradan da \(1\) gelir.
Sonuç olarak
$$D(10)=2+1=3.$$
Örneğin \(\{0,4,6\}\) kümesi optimaldir.
C++, Python ve Java implementations aynı mantığı izler.
Önce her kalanın görüntüsü hesaplanır, giriş dereceleri sayılır ve ters öncül listeleri oluşturulur. Sonra queue tabanlı peeling ile ağaç düğümleri ayrılır, cycle düğümleri ise geride bırakılır.
Daha sonra soyulan düğümler sırayla işlenir ve her biri için iki DP durumu hesaplanır. Böylece her cycle düğümü, kendisine bağlı ağaçların en iyi katkısını hazır halde taşır.
Son aşamada her cycle bir kez dolaşılır, taban katkı ile ağırlıklı bağımsız küme düzeltmesi hesaplanır ve bileşen sonucu \(D(n)\)'ye eklenir. Aynı süreç \(100001\) ile \(100100\) arasındaki tüm \(n\) değerleri için tekrarlanır.
Tek bir \(n\) için grafı kurmak \(O(n)\) zaman ve \(O(n)\) bellek gerektirir; çünkü her düğüm tam bir çıkış kenarı üretir. Peeling işlemi de lineerdir; her düğüm kuyruğa en fazla bir kez girer.
Ağaç DP'si ile cycle işleme aşaması da lineerdir, çünkü her öncül ilişkisi ve her cycle düğümü sabit sayıda kullanılır. Bu nedenle tek bir \(D(n)\) hesabının toplam maliyeti
$$O(n)\text{ zaman ve }O(n)\text{ bellek}$$
olarak kalır. Nihai toplam da 100 örnek boyunca işlenen toplam düğüm sayısına lineer bağlıdır.
Para un \(n\) fijo, definimos
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}.$$
La cantidad \(D(n)\) es el tamaño máximo de un subconjunto \(S\subseteq V\) tal que \(f_n\) envía cada elemento elegido a un elemento distinto y no elegido. De forma equivalente, el conjunto debe cumplir
$$f_n(S)\cap S=\varnothing \qquad \text{y} \qquad |f_n(S)|=|S|.$$
Como \(V\) es finito, la segunda condición significa simplemente que \(f_n\) es inyectiva sobre \(S\). La pregunta final del problema es
$$\sum_{i=1}^{100} D(100000+i).$$
La aplicación polinómica genera un grafo funcional. Eso permite separar la optimización en partes arbóreas y partes cíclicas.
Dibujamos una arista dirigida \(x\to f_n(x)\) para cada \(x\in V\). Como cada vértice tiene grado de salida \(1\), toda componente conexa contiene exactamente un ciclo dirigido y varios árboles entrantes que desembocan en ese ciclo.
Sea
$$P(u)=\{x\in V:f_n(x)=u\}$$
el conjunto de predecesores de \(u\). Entonces la condición de drifting equivale a
$$|S\cap (\{u\}\cup P(u))|\le 1 \qquad \text{para todo } u\in V.$$
Esta regla local resume todo: nunca se pueden elegir dos elementos con la misma imagen, y tampoco se puede elegir simultáneamente un vértice y uno de sus predecesores.
Si borramos repetidamente los vértices de grado de entrada \(0\), desaparecen exactamente las partes arbóreas y quedan solo los ciclos dirigidos. Además, el orden de eliminación garantiza que los predecesores ya procesados de un vértice estén listos cuando llegue su turno.
Después de este peeling, cada vértice del ciclo actúa como raíz de un árbol entrante formado por los vértices ya eliminados.
Sea \(u\) un vértice eliminado, y sea \(C(u)\) el conjunto de predecesores eliminados \(c\) con \(f_n(c)=u\). Definimos dos estados:
$$A_u=\text{mejor valor en el árbol de }u\text{ cuando }u\notin S,$$
$$B_u=\text{mejor valor en el árbol de }u\text{ cuando }u\in S.$$
Si elegimos \(u\), no podemos elegir ninguno de sus predecesores. Por tanto
$$B_u=1+\sum_{c\in C(u)} A_c.$$
Si no elegimos \(u\), como todos los predecesores apuntan al mismo destino \(u\), a lo sumo uno de ellos puede ser elegido. Entonces
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
Esta es la recurrencia central en la parte arbórea.
Consideremos ahora un ciclo \(c_0,c_1,\dots,c_{k-1}\) con
$$f_n(c_i)=c_{i+1} \quad \text{para } i \pmod{k}.$$
Sea \(T_i\) el conjunto de predecesores no cíclicos que entran en \(c_i\). Su contribución completa se resume por
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right).$$
Aquí \(a_i\) es la contribución base de dejar sin seleccionar todos los árboles adjuntos, y \(g_i\) es la mejor mejora posible si se selecciona un único predecesor adjunto. Si no se selecciona ningún vértice del ciclo, la componente aporta
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i).$$
Seleccionar el vértice cíclico \(c_i\) cambia la base \(C_0\) de esta manera:
$$+1 \text{ por seleccionar } c_i,$$
$$-g_i \text{ porque ya no puede seleccionarse ningún predecesor adjunto de } c_i,$$
$$-g_{i+1} \text{ porque } c_i \text{ ocupa el único puesto permitido entre los predecesores de } c_{i+1}.$$
Así, el peso neto es
$$w_i=1-g_i-g_{i+1}.$$
Además, dos vértices consecutivos del ciclo no pueden elegirse a la vez, ya que \(c_i\in S\) obliga a que \(f_n(c_i)=c_{i+1}\notin S\). Por lo tanto, el problema del ciclo es un conjunto independiente de peso máximo.
En un camino, la recurrencia estándar es
$$P_j=\max(P_{j-1},P_{j-2}+u_j).$$
Para un ciclo de longitud \(k>1\), bastan dos casos:
$$\text{Caso A: no seleccionar } c_0,$$
$$\text{Caso B: seleccionar } c_0 \text{ y prohibir } c_1 \text{ y } c_{k-1}.$$
Entonces
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr),$$
y la contribución de la componente es
$$D_{\text{comp}}=C_0+\text{best}.$$
Si \(k=1\), el ciclo es un lazo propio y ese vértice nunca puede seleccionarse porque apunta a sí mismo. En ese caso la contribución es solo \(a_0+g_0\).
Cuando \(n=10\), la aplicación queda
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9.$$
Las componentes cíclicas son el 2-ciclo \(1\leftrightarrow 3\) y el lazo \(9\mapsto 9\).
Las hojas que entran en \(1\) son \(\{0,2,5,7,8\}\), la hoja que entra en \(3\) es \(\{6\}\), y la hoja que entra en \(9\) es \(\{4\}\). Cada una de esas hojas tiene
$$A=0,\qquad B=1.$$
Para el 2-ciclo obtenemos
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1,$$
por lo que
$$C_0=2,\qquad w=1-1-1=-1.$$
La mejor corrección cíclica es \(0\), de modo que esa componente aporta \(2\). El lazo de \(9\) aporta \(1\), porque \(a=0\) y \(g=1\).
Por consiguiente,
$$D(10)=2+1=3.$$
Un subconjunto óptimo es \(\{0,4,6\}\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea.
Primero construyen el sucesor de cada residuo, los grados de entrada y las listas inversas de predecesores. Después aplican peeling con una cola para separar los vértices arbóreos de los vértices cíclicos.
Luego recorren los vértices eliminados en ese orden y calculan los dos estados de la DP sobre árboles. Cuando termina esa fase, cada vértice del ciclo ya conoce la mejor contribución posible de los árboles que desembocan en él.
Por último, cada ciclo restante se recorre una sola vez, se transforma en un problema de conjunto independiente ponderado y se suma su valor a \(D(n)\). El proceso se repite para \(n=100001,\dots,100100\).
Para un valor fijo de \(n\), construir el grafo cuesta \(O(n)\) tiempo y \(O(n)\) memoria, porque cada vértice produce exactamente una arista saliente. El peeling también es lineal: cada vértice entra en la cola como mucho una vez.
La DP de los árboles y el procesamiento de los ciclos siguen siendo lineales, ya que cada relación de predecesor y cada vértice del ciclo se utiliza un número constante de veces. En resumen, para un solo \(D(n)\) el coste total es
$$O(n)\text{ tiempo y }O(n)\text{ memoria.}$$
La suma final sobre 100 valores conserva esa linealidad respecto del número total de residuos procesados.
对固定的 \(n\)，定义
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}.$$
\(D(n)\) 表示满足下述条件的子集 \(S\subseteq V\) 的最大大小：每个被选中的元素在 \(f_n\) 下都会漂移到一个没有被选中的位置，而且不同的被选中元素必须漂移到不同的位置。等价地说，\(S\) 必须满足
$$f_n(S)\cap S=\varnothing \qquad \text{且} \qquad |f_n(S)|=|S|.$$
由于 \(V\) 是有限集，第二个条件等价于 \(f_n\) 在 \(S\) 上是单射。最终要求计算的是
$$\sum_{i=1}^{100} D(100000+i).$$
这个三次多项式模映射天然定义了一个函数图。理解这个函数图之后，问题就可以拆成树形部分的动态规划，以及环形部分的加权独立集问题。
对每个 \(x\in V\) 画一条有向边 \(x\to f_n(x)\)。因为每个点的出度恰好是 \(1\)，所以每个连通块都具有同样的结构：恰好一个有向环，外加若干棵朝向这个环汇入的有根入树。
记
$$P(u)=\{x\in V:f_n(x)=u\}$$
为所有指向 \(u\) 的前驱集合。那么 drifting 条件可以完全改写成下面的局部约束：
$$|S\cap (\{u\}\cup P(u))|\le 1 \qquad \text{对所有 } u\in V.$$
这条规则非常关键。它表示：
如果两个被选中的点有相同的像，那么它们会同时落在 \(P(u)\) 中，违反约束；如果某个点和它的前驱同时被选中，那么被选中的点的像仍然落在集合内部，也同样违反约束。于是，全局条件被压缩成了“对每个顶点单独检查一次”的局部规则。
不断删除入度为 \(0\) 的顶点。这个过程会把所有树形部分全部剥掉，而最后剩下的恰好就是所有有向环。与此同时，还会得到一个天然的处理顺序：当某个被剥离的顶点轮到计算时，它的树形前驱已经先被处理完了。
因此，剥离完成之后，每个剩余的环顶点都可以看成一棵入树的根，而这些入树已经准备好用动态规划汇总贡献。
设 \(u\) 是一个已经被剥离的顶点，\(C(u)\) 表示所有满足 \(f_n(c)=u\) 的、同样已被剥离的前驱。定义两个状态：
$$A_u=\text{当 }u\notin S\text{ 时，以 }u\text{ 为根的树能取得的最优值},$$
$$B_u=\text{当 }u\in S\text{ 时，以 }u\text{ 为根的树能取得的最优值}.$$
如果选择了 \(u\)，那么所有前驱都不能再选，因为它们都会把像送到 \(u\)，从而和 \(u\) 本身冲突。因此
$$B_u=1+\sum_{c\in C(u)} A_c.$$
如果不选 \(u\)，那么所有前驱都共享同一个目标 \(u\)，所以至多只能选其中一个。于是先取所有前驱都不选的基线，再看是否值得把其中一个前驱切换到“选中”状态：
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
这正是三种实现共享的树形递推公式。它抓住了问题的本质：同一个目标点 \(u\) 只能接受最多一个被选中的前驱。
现在考虑一个有向环 \(c_0,c_1,\dots,c_{k-1}\)，其中
$$f_n(c_i)=c_{i+1} \quad \text{下标按 }k\text{ 取模}.$$
记 \(T_i\) 为所有接到 \(c_i\) 上、但本身不在环上的前驱。整个入树的贡献可以压缩成两个数：
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right).$$
其中 \(a_i\) 表示把 \(c_i\) 的所有树形前驱都保持“不选”时的总贡献，\(g_i\) 表示如果允许在这些前驱里挑一个选中，最多还能额外增加多少。
如果整个环上一个顶点都不选，那么这一个连通块的贡献就是
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i).$$
这一步把复杂的树结构压缩成了沿环排列的一组局部参数。
接下来考虑选择环顶点 \(c_i\) 本身，相对于基线 \(C_0\)，会发生三件事：
$$+1 \text{，因为我们选中了 } c_i,$$
$$-g_i \text{，因为一旦 } c_i \text{ 被选，它自己的入树中就不能再选任何前驱},$$
$$-g_{i+1} \text{，因为 } c_i \text{ 已经占用了进入 } c_{i+1} \text{ 的唯一可选前驱名额}.$$
于是选择 \(c_i\) 的净增量为
$$w_i=1-g_i-g_{i+1}.$$
另外，相邻的两个环顶点不能同时选中；因为如果 \(c_i\in S\)，那么它的像 \(f_n(c_i)=c_{i+1}\) 必须不在 \(S\) 中。这样一来，环上的最优选择就等价于一个带权环图上的最大权独立集问题。
对于一条路径，最大非相邻权值和可以用标准递推
$$P_j=\max(P_{j-1},P_{j-2}+u_j)$$
在线性时间内求出。对于长度 \(k>1\) 的环，只需拆成两个情况：
$$\text{情况 A：不选 } c_0,$$
$$\text{情况 B：选 } c_0,\ \text{于是 } c_1 \text{ 和 } c_{k-1} \text{ 都不能选}.$$
因此有
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr).$$
整个环连通块的贡献就是
$$D_{\text{comp}}=C_0+\text{best}.$$
如果 \(k=1\)，那就是自环。自环顶点映射到自己，所以它永远不能被选中，此时贡献直接等于 \(a_0+g_0\)。
当 \(n=10\) 时，映射为
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9.$$
因此图里有两个环连通块：一个是 \(1\leftrightarrow 3\) 的 2 环，另一个是 \(9\mapsto 9\) 的自环。
指向 \(1\) 的树叶是 \(\{0,2,5,7,8\}\)，指向 \(3\) 的树叶是 \(\{6\}\)，指向 \(9\) 的树叶是 \(\{4\}\)。这些树叶都没有进一步的树形前驱，所以它们都有
$$A=0,\qquad B=1.$$
对 2 环 \(1\leftrightarrow 3\) 而言，得到
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1.$$
所以基线贡献是
$$C_0=(0+1)+(0+1)=2,$$
而两个环顶点的净权值都是
$$w=1-1-1=-1.$$
这说明选环顶点并不会带来正收益，最优修正量是 \(0\)，因此这个环连通块总贡献为 \(2\)。
对于自环 \(9\mapsto 9\)，有 \(a=0\)、\(g=1\)，但顶点 \(9\) 自身不能被选，所以该连通块贡献 \(1\)。
于是
$$D(10)=2+1=3.$$
一个最优解是 \(\{0,4,6\}\)。它的像是 \(\{1,9,3\}\)，和原集合不相交，而且三个像互不相同。
C++、Python 和 Java 实现遵循同一条计算流水线。
第一步，枚举每个余数 \(x\)，计算它的后继 \(f_n(x)\)，统计每个顶点的入度，并保存反向前驱表。第二步，用队列执行入度剥离，把所有树顶点依次移除，从而识别出哪些顶点属于环。
第三步，按照剥离顺序处理所有树顶点，并为每个顶点计算上面的两个 DP 状态。这样一来，每个环顶点所连接的入树贡献都已经被压缩成基线和增益。
第四步，逐个遍历剩下的有向环，把每个环转化成带权独立集问题，求出该连通块的最佳修正值，再与基线相加得到该块贡献。所有环块求和后就是 \(D(n)\)。
最后，对 \(n=100001,100002,\dots,100100\) 重复这一过程并累加结果。
对单个 \(n\) 而言，建图阶段访问每个顶点一次，并且每个顶点只产生一条出边，因此时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)。入度剥离同样是线性的，因为每个顶点最多入队一次。
树上的动态规划只会对每条前驱关系做常数次处理，环上的计算也只会访问每个剩余顶点一次，所以整个 \(D(n)\) 的计算仍然保持
$$O(n)\text{ 时间和 }O(n)\text{ 空间。}$$
最终需要求和的 100 个实例，总时间与这 100 个 \(n\) 的顶点总数成线性关系。
Для фиксированного \(n\) зададим отображение
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}.$$
Величина \(D(n)\) равна максимальному размеру подмножества \(S\subseteq V\), для которого каждое выбранное число переходит в различную и при этом не выбранную вершину. Эквивалентная запись такова:
$$f_n(S)\cap S=\varnothing \qquad \text{и} \qquad |f_n(S)|=|S|.$$
Поскольку \(V\) конечно, второе условие означает, что \(f_n\) инъективно на \(S\). Итоговый запрос задачи имеет вид
$$\sum_{i=1}^{100} D(100000+i).$$
Полиномиальное отображение по модулю удобно рассматривать как функциональный граф. После этого задача распадается на DP по деревьям и отдельную оптимизацию по циклам.
Для каждого остатка \(x\in V\) проводим ориентированное ребро \(x\to f_n(x)\). Так как из каждой вершины выходит ровно одно ребро, каждая компонента связности состоит из одного ориентированного цикла и набора входящих деревьев, которые в этот цикл впадают.
Обозначим через
$$P(u)=\{x\in V:f_n(x)=u\}$$
множество предшественников вершины \(u\). Тогда условие drifting эквивалентно локальному правилу
$$|S\cap (\{u\}\cup P(u))|\le 1 \qquad \text{для каждого } u\in V.$$
Именно это правило и нужно оптимизировать: нельзя одновременно выбрать две вершины с одним и тем же образом, и нельзя выбрать вершину вместе с одним из ее предшественников.
Повторяем следующую операцию: удаляем вершины с входящей степенью \(0\). Так исчезают все древесные части, а после завершения процесса остаются ровно вершины циклов. Одновременно получается порядок обработки, в котором все уже удаленные предшественники вершины известны до обработки самой вершины.
После такого peeling каждая циклическая вершина становится корнем входящего дерева из ранее удаленных вершин.
Пусть \(u\) уже удалена, а \(C(u)\) обозначает множество ее удаленных предшественников \(c\) с условием \(f_n(c)=u\). Введем два состояния:
$$A_u=\text{оптимум в дереве вершины }u\text{ при }u\notin S,$$
$$B_u=\text{оптимум в дереве вершины }u\text{ при }u\in S.$$
Если вершина \(u\) выбрана, то ни один ее предшественник быть выбран не может. Поэтому
$$B_u=1+\sum_{c\in C(u)} A_c.$$
Если вершина \(u\) не выбрана, то из всех ее предшественников можно выбрать не более одного, так как все они отображаются в одну и ту же вершину \(u\). Отсюда
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
Эта рекурсия полностью описывает оптимальное поведение на древесной части компоненты.
Рассмотрим цикл \(c_0,c_1,\dots,c_{k-1}\), где
$$f_n(c_i)=c_{i+1} \quad \text{по модулю }k.$$
Пусть \(T_i\) состоит из всех нециклических предшественников вершины \(c_i\). Их суммарный вклад можно заменить двумя числами:
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right).$$
Здесь \(a_i\) дает базовый вклад при невыборе всех прикрепленных предшественников, а \(g_i\) показывает лучший возможный дополнительный выигрыш от выбора ровно одного такого предшественника. Если вершины цикла вообще не выбирать, то вклад всей компоненты равен
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i).$$
Теперь посмотрим, что происходит, если выбрать саму циклическую вершину \(c_i\). Относительно базы \(C_0\) мы получаем
$$+1 \text{ за выбор } c_i,$$
$$-g_i \text{, потому что тогда нельзя выбирать прикрепленного предшественника вершины } c_i,$$
$$-g_{i+1} \text{, потому что } c_i \text{ уже занимает единственное допустимое место среди предшественников } c_{i+1}.$$
Следовательно, чистый вес выбора \(c_i\) равен
$$w_i=1-g_i-g_{i+1}.$$
Соседние вершины цикла одновременно выбирать нельзя: из \(c_i\in S\) сразу следует \(f_n(c_i)=c_{i+1}\notin S\). Значит, на цикле нужно найти максимальное взвешенное независимое множество.
Для пути используется стандартная рекурсия
$$P_j=\max(P_{j-1},P_{j-2}+u_j).$$
Для цикла длины \(k>1\) достаточно двух случаев:
$$\text{Случай A: } c_0 \text{ не выбирается},$$
$$\text{Случай B: } c_0 \text{ выбирается, а значит } c_1 \text{ и } c_{k-1} \text{ запрещены}.$$
Тогда
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr),$$
а вклад компоненты равен
$$D_{\text{comp}}=C_0+\text{best}.$$
Если \(k=1\), то это петля. Такую вершину нельзя выбрать вообще, потому что она отображается сама в себя. Тогда вклад просто равен \(a_0+g_0\).
При \(n=10\) отображение имеет вид
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9.$$
Отсюда видно две циклические компоненты: цикл \(1\leftrightarrow 3\) и петля \(9\mapsto 9\).
В вершину \(1\) входят листья \(\{0,2,5,7,8\}\), в вершину \(3\) входит лист \(\{6\}\), а в вершину \(9\) входит лист \(\{4\}\). Для любого такого листа имеем
$$A=0,\qquad B=1.$$
Следовательно, для цикла \(1\leftrightarrow 3\)
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1,$$
поэтому
$$C_0=2,\qquad w=1-1-1=-1.$$
Лучшая циклическая поправка равна \(0\), так что эта компонента дает вклад \(2\). Для петли в вершине \(9\) имеем \(a=0\) и \(g=1\), следовательно, вклад равен \(1\).
Итак,
$$D(10)=2+1=3.$$
Один из оптимальных наборов: \(\{0,4,6\}\).
Реализации на C++, Python и Java устроены одинаково.
Сначала они строят массив переходов, подсчитывают входящие степени и сохраняют обратные списки предшественников. Затем запускают peeling по вершинам с нулевой входящей степенью, тем самым отделяя деревья от циклов.
После этого удаленные вершины обрабатываются в порядке peeling, и для каждой вычисляются два древесных DP-состояния. В результате каждая вершина цикла уже знает, какой оптимальный вклад дают ее прикрепленные деревья.
Далее каждый оставшийся цикл обходится один раз, преобразуется в задачу о взвешенном независимом множестве на цикле, и его вклад прибавляется к \(D(n)\). Затем тот же процесс повторяется для \(n=100001,\dots,100100\).
Для одного значения \(n\) построение графа требует \(O(n)\) времени и \(O(n)\) памяти, потому что каждая вершина порождает ровно одно исходящее ребро. Peeling тоже работает за линейное время: каждая вершина попадает в очередь не более одного раза.
DP на деревьях и обработка циклов также линейны, поскольку каждая связь предшественник-вершина и каждая циклическая вершина рассматриваются лишь константное число раз. Поэтому для одного \(D(n)\) общая сложность равна
$$O(n)\text{ по времени и }O(n)\text{ по памяти.}$$
Финальная сумма по 100 последовательным значениям \(n\) остается линейной относительно общего числа обработанных вершин.
لعدد ثابت \(n\)، نعرّف
$$f_n(x)\equiv x^3+x+1 \pmod{n}, \qquad V=\{0,1,\dots,n-1\}.$$
الكمية \(D(n)\) هي أكبر حجم لمجموعة جزئية \(S\subseteq V\) بحيث إن كل عنصر مختار ينتقل تحت \(f_n\) إلى عنصر غير مختار ومختلف عن صور العناصر المختارة الأخرى. وبصياغة مكافئة يجب أن يتحقق
$$f_n(S)\cap S=\varnothing,\qquad |f_n(S)|=|S|.$$
وبما أن \(V\) منتهية، فهذا يعني أن \(f_n\) حقنية على \(S\). والسؤال النهائي في المسألة هو حساب
$$\sum_{i=1}^{100} D(100000+i).$$
الدالة كثيرة الحدود هذه تولد رسمًا وظيفيًا بطبيعته، وعند النظر إليها بهذه الطريقة تصبح المسألة مزيجًا من برمجة ديناميكية على الأشجار ومعالجة مستقلة للدورات.
نرسم حافة موجهة من كل \(x\in V\) إلى \(f_n(x)\). ولكون كل رأس يملك درجة خروج تساوي \(1\)، فإن كل مركبة متصلة تتكون من دورة موجهة واحدة بالضبط، ومعها أشجار داخلة تتجه نحو تلك الدورة.
لنكتب
$$P(u)=\{x\in V:f_n(x)=u\}$$
لمجموعة السوابق التي تصل إلى \(u\). عندئذ تصبح خاصية drifting مكافئة تمامًا للقيد المحلي
$$|S\cap (\{u\}\cup P(u))|\le 1 \quad (u\in V).$$
هذا القيد يلخص كل شيء: لا يجوز اختيار عنصرين لهما الصورة نفسها، ولا يجوز أيضًا اختيار رأس مع أحد أسلافه المباشرين الذين يصلون إليه.
نحذف الرؤوس ذات درجة الدخول \(0\) مرارًا وتكرارًا. بهذه العملية تختفي الأجزاء الشجرية كلها، وما يبقى في النهاية هو رؤوس الدورات فقط. كذلك نحصل على ترتيب معالجة مناسب: عندما نصل إلى رأس مقشور تكون السوابق الشجرية التابعة له قد عولجت بالفعل.
بعد اكتمال هذا التقشير يصبح كل رأس دوري جذرًا لشجرة داخلة من الرؤوس التي أزيلت سابقًا.
ليكن \(u\) رأسًا مقشورًا، ولتكن \(C(u)\) مجموعة السوابق المقشورة \(c\) التي تحقق \(f_n(c)=u\). نعرّف حالتين:
\(A_u\) هي أفضل قيمة داخل شجرة \(u\) عندما يكون \(u\notin S\).
\(B_u\) هي أفضل قيمة داخل شجرة \(u\) عندما يكون \(u\in S\).
إذا اخترنا \(u\)، فلا يمكن اختيار أي سابق له، لأن جميعهم يرسلون صورهم إلى \(u\). لذلك
$$B_u=1+\sum_{c\in C(u)} A_c.$$
أما إذا لم نختر \(u\)، فلا يمكن اختيار أكثر من سابق واحد، لأن جميع السوابق تتشارك الهدف نفسه \(u\). ومن ثم
$$A_u=\sum_{c\in C(u)} A_c+\max\left(0,\max_{c\in C(u)}(B_c-A_c)\right).$$
هذه العلاقة هي جوهر الحل على الأجزاء الشجرية.
لننظر الآن إلى دورة \(c_0,c_1,\dots,c_{k-1}\) حيث
$$f_n(c_i)=c_{i+1}\quad (i \bmod k).$$
ولتكن \(T_i\) مجموعة السوابق غير الدورية الداخلة إلى \(c_i\). يمكن تلخيص مساهمة تلك الأشجار برقمين:
$$a_i=\sum_{t\in T_i} A_t,$$
$$g_i=\max\left(0,\max_{t\in T_i}(B_t-A_t)\right).$$
\(a_i\) هو المساهمة الأساسية إذا بقيت جميع السوابق الملحقة غير مختارة، أما \(g_i\) فهو أفضل ربح إضافي ممكن إذا اخترنا سابقًا واحدًا فقط من تلك السوابق. إذا لم نختر أي رأس من رؤوس الدورة أصلًا، فإن مساهمة المركبة كلها تساوي
$$C_0=\sum_{i=0}^{k-1}(a_i+g_i).$$
إذا اخترنا الرأس الدوري \(c_i\)، فإن التغير بالنسبة إلى الأساس \(C_0\) هو
التعديل الصافي يتكون من ثلاثة حدود: ربح \(+1\) بسبب اختيار \(c_i\)، وخسارة \(g_i\) لأن أسلاف \(c_i\) الملحقة تصبح ممنوعة، وخسارة \(g_{i+1}\) لأن \(c_i\) يشغل الخانة الوحيدة المسموح بها بين السوابق الداخلة إلى \(c_{i+1}\).
$$+1,\qquad -g_i,\qquad -g_{i+1}.$$
إذًا الوزن الصافي لاختيار \(c_i\) هو
$$w_i=1-g_i-g_{i+1}.$$
ولا يجوز أيضًا اختيار رأسين متجاورين على الدورة معًا؛ فإذا كان \(c_i\in S\) فلا بد أن يكون \(f_n(c_i)=c_{i+1}\notin S\). وهكذا تتحول المسألة على الدورة إلى مسألة مجموعة مستقلة موزونة على دورة.
على مسار خطي نستخدم العلاقة القياسية
$$P_j=\max(P_{j-1},P_{j-2}+u_j).$$
أما للدورة ذات الطول \(k>1\)، فنفصل حالتين:
الحالة A: لا نختار \(c_0\).
الحالة B: نختار \(c_0\)، وعندها يصبح كل من \(c_1\) و\(c_{k-1}\) ممنوعًا.
فنحصل على
$$\text{best}=\max\Bigl(0,\ \operatorname{Path}(w_1,\dots,w_{k-1}),\ w_0+\operatorname{Path}(w_2,\dots,w_{k-2})\Bigr).$$
وبالتالي تكون مساهمة المركبة
$$D_{\text{comp}}=C_0+\text{best}.$$
إذا كان \(k=1\)، فلدينا حلقة ذاتية، أي إن الرأس يشير إلى نفسه، ولذلك لا يمكن اختياره أبدًا، وتكون المساهمة ببساطة \(a_0+g_0\).
عندما \(n=10\)، تكون الدالة
$$0\mapsto 1,\ 1\mapsto 3,\ 2\mapsto 1,\ 3\mapsto 1,\ 4\mapsto 9,\ 5\mapsto 1,\ 6\mapsto 3,\ 7\mapsto 1,\ 8\mapsto 1,\ 9\mapsto 9.$$
إذن لدينا مركبتان دوريتان: الدورة \(1\leftrightarrow 3\) والحلقة الذاتية \(9\mapsto 9\).
الأوراق الداخلة إلى \(1\) هي \(\{0,2,5,7,8\}\)، والورقة الداخلة إلى \(3\) هي \(\{6\}\)، والورقة الداخلة إلى \(9\) هي \(\{4\}\). وكل ورقة منها تحقق
$$A=0,\qquad B=1.$$
لذلك نحصل في الدورة \(1\leftrightarrow 3\) على
$$a_1=0,\ g_1=1,\qquad a_2=0,\ g_2=1,$$
ومن ثم
$$C_0=2,\qquad w=1-1-1=-1.$$
أفضل تصحيح دوري يساوي \(0\)، فتكون مساهمة هذه المركبة \(2\). أما الحلقة عند \(9\) فلها \(a=0\) و\(g=1\)، فيكون إسهامها \(1\).
إذن
$$D(10)=2+1=3.$$
ومن الأمثلة على مجموعة مثلى: \(\{0,4,6\}\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا.
في البداية تُبنى صورة كل باقٍ، وتُحسب درجات الدخول، وتُخزن قوائم السوابق العكسية. بعد ذلك يُنفذ التقشير المعتمد على الطابور من أجل فصل الرؤوس الشجرية عن الرؤوس الدورية.
ثم تُعالَج الرؤوس المقشورة بترتيب التقشير لحساب حالتي البرمجة الديناميكية لكل رأس شجري. وعند انتهاء هذه المرحلة يكون كل رأس دوري قد عرف المساهمة المثلى لأشجاره الملحقة.
أخيرًا تُمر كل دورة مرة واحدة، وتُحوَّل إلى مسألة مجموعة مستقلة موزونة، ثم تُضاف مساهمة المركبة إلى \(D(n)\). وبعد حساب قيمة واحدة من \(D(n)\)، تتكرر العملية للقيم \(100001\) حتى \(100100\).
لبنية واحدة ذات حجم \(n\)، يستغرق بناء الرسم \(O(n)\) زمنًا و\(O(n)\) ذاكرة، لأن كل رأس يولد حافة خروج واحدة فقط. وكذلك عملية التقشير خطية، إذ لا يدخل أي رأس الطابور أكثر من مرة.
أما البرمجة الديناميكية على الأشجار ومعالجة الدورات فتبقيان خطيتين أيضًا، لأن كل علاقة سلف-رأس وكل رأس دوري يُستخدمان عددًا ثابتًا من المرات. لذا يبقى حساب \(D(n)\) الواحد بكلفة
أي أن الكلفة الكلية هي \(O(n)\) زمنًا و\(O(n)\) ذاكرة.
وعند جمع 100 قيمة متتالية، يظل الزمن الكلي خطيًا في مجموع عدد الرؤوس المعالجة عبر تلك القيم.