The problem studies the \(k\)-variable Markov-type equation
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
A Vieta-style move chooses one coordinate and replaces it by
$$x_i'=k\prod_{j\ne i}x_j-x_i,$$
which preserves the equation. Starting from \((1,1,\dots,1)\), let \(\mathcal{V}_k(N)\) be the set of distinct integers \(x\le N\) that appear in at least one reachable positive tuple, and define
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
The required quantity is
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
The key difficulty is that small \(k\) produce a branching state graph, while large \(k\) collapse into a short deterministic chain.
The implementation uses a hybrid argument: exact breadth-first exploration while genuine branching is still possible, and a closed-form tail once the bound \(N\) rules out tuples with three nontrivial entries.
Fix all coordinates except \(x_i\). Then the defining equation becomes a quadratic in one variable:
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
If one root is \(X=x_i\), Vieta's formulas show that the other root is
$$X'=k\prod_{j\ne i}x_j-x_i.$$
So replacing \(x_i\) by \(x_i'\) keeps the tuple on the same equation. The start tuple \((1,\dots,1)\) is valid because both sides equal \(k\). Every tuple examined by the exact search is generated from this seed by repeated applications of the same invariant move.
The equation and the move are symmetric in the coordinates, so order does not matter. The implementation therefore stores only the entries greater than \(1\), sorted increasingly. A stored state
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
represents the full \(k\)-tuple with \(k-t\) hidden ones. This compression is exact because the empty product is \(1\), and the move formulas become:
If a hidden \(1\) is replaced, the new value is
$$y=k\prod_{r=1}^{t}a_r-1.$$
If the stored value \(a_i\) is replaced, the new value is
$$y=k\prod_{r\ne i}a_r-a_i.$$
If \(y=1\), that coordinate simply disappears from the stored state. If \(y>1\), it is inserted back and the state is sorted again. This turns a \(k\)-tuple problem into a search over small sorted multisets.
For fixed \(k\), a breadth-first search starts from the empty stored state, which represents \((1,\dots,1)\). Each reachable state with all entries at most \(N\) is visited once, and every distinct value appearing in any visited state is inserted into \(\mathcal{V}_k(N)\). Because states are stored canonically as sorted multisets, permuting coordinates does not create duplicates.
This phase is exact: it does not rely on heuristics, only on the move formulas above and on the bound \(x\le N\). The sum \(M_k(N)\) is therefore the sum of distinct reachable values, not the sum over states.
Let
$$a_0=1,\qquad a_1=k-1.$$
The smallest possible state with one stored entry is therefore \((a_1)\). Replacing one more hidden \(1\) gives the smallest possible two-entry state, whose new value is
$$a_2=ka_1-a_0=k^2-k-1.$$
Now ask for the smallest possible state with three stored entries. The minimal way to create it is to start from the minimal two-entry state \((a_1,a_2)\) and replace yet another hidden \(1\). That produces
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1.$$
Hence if \(b_3>N\), then no reachable tuple contributing to \(M_k(N)\) can contain three coordinates greater than \(1\). This gives the exact cutoff
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}.$$
The implementation explores \(k\le \kappa_4\) exactly and handles \(k>\kappa_4\) by formulas.
Once three stored entries are impossible, every relevant state has at most two coordinates greater than \(1\). In that regime the reachable values follow the recurrence
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1.$$
The first terms are
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1.$$
For \(k\ge 3\), the sequence is strictly increasing: if \(a_n>a_{n-1}\), then
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
The next term is
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1,$$
and it satisfies
$$a_4-b_3=(k-2)(k^2-k-1)>0.$$
So if \(k>\kappa_4\), then \(b_3>N\), hence \(a_4>N\) and every later chain term is also \(>N\). Therefore only \(1\), \(a_1\), \(a_2\), and \(a_3\) can contribute in the large-\(k\) range.
Define the two remaining thresholds
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}.$$
Then for every \(k>\kappa_4\),
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
The term \(k\) is simply \(1+(k-1)\), the guaranteed contribution of the seed value and the first nontrivial value.
For \(k=4\), the chain begins with
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41.$$
The smallest possible third stored entry is
$$b_3=4\cdot 3\cdot 11-1=131>100.$$
So no tuple with three entries greater than \(1\) can contribute. The only reachable values at or below \(100\) are therefore
$$1,\ 3,\ 11,\ 41,$$
which gives
$$M_4(100)=1+3+11+41=56.$$
Together with the \(k=3\) contribution, the full check value is
$$S(4,100)=229,$$
matching the program's built-in sanity test.
The C++, Python, and Java implementations all follow the same structure. First, they compute the quartic cutoff \(\kappa_4\) and run an exact breadth-first search separately for each \(k\) from \(3\) up to \(\min(K,\kappa_4)\). A queue stores canonical states, a visited set prevents repeats, and a second set records the distinct integers that have appeared so they are counted only once in \(M_k(N)\).
During each transition, the implementation multiplies only up to the cap needed to decide whether the next value could still be at most \(N\). That prevents unnecessary big intermediate products and prunes branches as soon as they are certainly too large. When several equal entries appear in a state, only one representative replacement needs to be tried, because replacing identical coordinates yields the same canonical successor.
After the exact range, the implementation switches to the chain formulas. Three binary searches locate \(\kappa_2\), \(\kappa_3\), and \(\kappa_4\). The remaining contribution is then written as a sum of piecewise polynomials in \(k\), so it can be accumulated from closed forms for
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
modulo \(1405695061\). Modular inverses of \(2\) and \(6\) are used to evaluate the usual prefix-sum formulas inside the modulus.
Let \(T_k(N)\) be the number of canonical states visited in the exact search for a fixed \(k\). The exact phase costs
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right),$$
where \(c_k\) is the average work per state for capped products, successor construction, and set operations. The memory usage of that phase is \(O(T_k(N))\) per active \(k\), dominated by the visited states and the set of distinct numbers.
The important structural fact is that \(\kappa_4\) is defined by a quartic inequality, so the exact outer loop covers only \(O(N^{1/4})\) values of \(k\). The large-\(k\) tail needs only three binary searches, hence \(O(\log N)\) time, plus \(O(1)\) arithmetic for the closed-form interval sums. In practice the runtime is dominated by the exact searches near the cutoff, and the tail is negligible.
Untersucht wird die \(k\)-variable Markov-Gleichung vom Typ
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
Ein Vieta-Schritt ersetzt eine Koordinate durch
$$x_i'=k\prod_{j\ne i}x_j-x_i,$$
und erhält die Gleichung. Ausgehend von \((1,1,\dots,1)\) sei \(\mathcal{V}_k(N)\) die Menge aller verschiedenen ganzen Zahlen \(x\le N\), die in mindestens einem erreichbaren positiven Tupel vorkommen. Dann ist
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
Gesucht wird
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
Die Schwierigkeit besteht darin, dass für kleine \(k\) ein verzweigter Zustandsgraph entsteht, während für große \(k\) nur noch eine kurze deterministische Kette übrig bleibt.
Die Implementierung kombiniert exakte Zustandsraumsuche mit einer geschlossenen Formel für den Bereich, in dem durch die Schranke \(N\) bereits alle Tupel mit drei nichttrivialen Einträgen ausgeschlossen sind.
Fixiert man alle Koordinaten außer \(x_i\), so wird die definierende Gleichung zu einer quadratischen Gleichung in einer Variablen:
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
Ist \(X=x_i\) eine Nullstelle, dann liefert die Viète-Beziehung als zweite Nullstelle
$$X'=k\prod_{j\ne i}x_j-x_i.$$
Darum bleibt das Tupel auf derselben Gleichung, wenn man \(x_i\) durch \(x_i'\) ersetzt. Der Startpunkt \((1,\dots,1)\) ist gültig, weil beide Seiten gleich \(k\) sind. Alle im exakten Teil untersuchten Tupel entstehen durch wiederholte Anwendung genau dieses invarianten Schritts.
Da Gleichung und Übergang symmetrisch in den Koordinaten sind, ist die Reihenfolge unerheblich. Gespeichert werden daher nur die Einträge größer als \(1\), aufsteigend sortiert. Ein gespeicherter Zustand
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
steht für das vollständige \(k\)-Tupel mit \(k-t\) verborgenen Einsen. Diese Kompression ist exakt, denn das leere Produkt ist \(1\), und die Übergänge lauten dann:
Ersetzt man eine verborgene \(1\), so ist der neue Wert
$$y=k\prod_{r=1}^{t}a_r-1.$$
Ersetzt man den gespeicherten Wert \(a_i\), so ist der neue Wert
$$y=k\prod_{r\ne i}a_r-a_i.$$
Falls \(y=1\), verschwindet der Eintrag aus dem gespeicherten Zustand. Falls \(y>1\), wird er wieder eingefügt und neu sortiert. So wird aus einem Problem über \(k\)-Tupel eine Suche über kleine sortierte Multimengen.
Für festes \(k\) startet eine Breitensuche beim leeren Zustand, also bei \((1,\dots,1)\). Jeder erreichbare Zustand, dessen Einträge alle höchstens \(N\) sind, wird genau einmal besucht, und jeder unterschiedliche Wert, der in einem besuchten Zustand vorkommt, wird in \(\mathcal{V}_k(N)\) aufgenommen. Da die Zustände kanonisch als sortierte Multimengen gespeichert werden, erzeugen Koordinatenpermutationen keine Duplikate.
Dieser Teil ist exakt: Es gibt keine heuristische Abschätzung, sondern nur die oben hergeleiteten Übergangsformeln und die Schranke \(x\le N\). \(M_k(N)\) ist also die Summe der verschiedenen erreichbaren Werte und nicht die Summe über Zustände.
Setze
$$a_0=1,\qquad a_1=k-1.$$
Der kleinste mögliche Zustand mit einem gespeicherten Eintrag ist also \((a_1)\). Ersetzt man eine weitere verborgene \(1\), erhält man den kleinsten möglichen Zweierzustand mit neuem Wert
$$a_2=ka_1-a_0=k^2-k-1.$$
Nun fragen wir nach dem kleinsten möglichen Zustand mit drei gespeicherten Einträgen. Der minimale Weg dorthin führt vom minimalen Zweierzustand \((a_1,a_2)\) durch Ersetzen einer weiteren verborgenen \(1\). Dadurch entsteht
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1.$$
Gilt also \(b_3>N\), dann kann kein zu \(M_k(N)\) beitragendes Tupel drei Koordinaten größer als \(1\) besitzen. Das liefert den exakten Cutoff
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}.$$
Die Implementierung behandelt \(k\le \kappa_4\) exakt und \(k>\kappa_4\) durch Formeln.
Sobald drei gespeicherte Einträge unmöglich sind, hat jeder relevante Zustand höchstens zwei Koordinaten größer als \(1\). In diesem Bereich folgen die erreichbaren Werte der Rekursion
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1.$$
Die ersten Glieder sind
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1.$$
Für \(k\ge 3\) wächst die Folge streng: Aus \(a_n>a_{n-1}\) folgt
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
Das nächste Glied ist
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1,$$
und es gilt
$$a_4-b_3=(k-2)(k^2-k-1)>0.$$
Also folgt aus \(k>\kappa_4\), dass bereits \(b_3>N\), damit auch \(a_4>N\), und erst recht alle späteren Kettenglieder. Im großen-\(k\)-Bereich können also nur \(1\), \(a_1\), \(a_2\) und \(a_3\) beitragen.
Definiere die beiden restlichen Schwellen
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}.$$
Dann gilt für jedes \(k>\kappa_4\)
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
Der Term \(k\) ist nichts anderes als \(1+(k-1)\), also der sichere Beitrag des Startwerts und des ersten nichttrivialen Werts.
Für \(k=4\) beginnt die Kette mit
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41.$$
Der kleinste mögliche dritte gespeicherte Eintrag ist
$$b_3=4\cdot 3\cdot 11-1=131>100.$$
Also kann kein Tupel mit drei Einträgen größer als \(1\) beitragen. Die einzigen erreichbaren Werte bis \(100\) sind deshalb
$$1,\ 3,\ 11,\ 41,$$
und damit
$$M_4(100)=1+3+11+41=56.$$
Nimmt man noch den \(k=3\)-Beitrag hinzu, erhält man den Gesamtprüfwert
$$S(4,100)=229,$$
genau wie im eingebauten Test des Programms.
Die Implementierungen in C++, Python und Java folgen alle derselben Struktur. Zuerst wird der quartische Cutoff \(\kappa_4\) berechnet, und für jedes \(k\) von \(3\) bis \(\min(K,\kappa_4)\) wird eine exakte Breitensuche ausgeführt. Eine Queue speichert die kanonischen Zustände, eine Besuchsmenge verhindert Wiederholungen, und eine zweite Menge sammelt die verschiedenen auftretenden Zahlen, damit jeder Wert in \(M_k(N)\) nur einmal gezählt wird.
Während eines Übergangs wird nur bis zu jener Schranke multipliziert, die ausreicht, um zu entscheiden, ob der nächste Wert noch höchstens \(N\) sein kann. Dadurch werden unnötig große Zwischenprodukte vermieden und Äste sofort abgeschnitten, sobald sie sicher zu groß sind. Wenn ein Zustand mehrere gleiche Einträge enthält, genügt ein einziger repräsentativer Austausch, weil identische Koordinaten zum selben kanonischen Nachfolger führen.
Nach dem exakten Bereich wechselt die Implementierung zu den Kettenformeln. Drei Binärsuchen bestimmen \(\kappa_2\), \(\kappa_3\) und \(\kappa_4\). Der restliche Beitrag ist dann eine stückweise polynomiale Funktion von \(k\) und lässt sich daher aus geschlossenen Formeln für
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
modulo \(1405695061\) aufsummieren. Modulare Inverse von \(2\) und \(6\) dienen dazu, die üblichen Präfixsummenformeln im Modul auszuwerten.
Sei \(T_k(N)\) die Anzahl der kanonischen Zustände, die in der exakten Suche für festes \(k\) besucht werden. Dann kostet die exakte Phase
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right),$$
wobei \(c_k\) die mittlere Arbeit pro Zustand für begrenzte Produkte, Nachfolgerkonstruktion und Mengenoperationen bezeichnet. Der Speicherbedarf dieser Phase ist \(O(T_k(N))\) pro aktivem \(k\), dominiert von den besuchten Zuständen und der Menge der verschiedenen Zahlen.
Die entscheidende Struktur ist, dass \(\kappa_4\) durch eine quartische Ungleichung definiert ist; der exakte äußere Loop umfasst also nur \(O(N^{1/4})\) Werte von \(k\). Der große Rest benötigt lediglich drei Binärsuchen, also \(O(\log N)\) Zeit, und anschließend \(O(1)\)-Arithmetik für die geschlossenen Bereichssummen. Praktisch dominiert daher die exakte Suche in der Nähe des Cutoffs, während der Tail vernachlässigbar billig ist.
Problem, şu \(k\) değişkenli Markov-tip denklemi inceler:
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
Bir Vieta adımı, bir koordinatı
$$x_i'=k\prod_{j\ne i}x_j-x_i$$
ile değiştirir ve denklemi korur. \((1,1,\dots,1)\) başlangıcından hareketle, \(\mathcal{V}_k(N)\) kümesini en az bir erişilebilir pozitif dizide görülen ve \(x\le N\) olan farklı tamsayıların kümesi olarak tanımlayalım. O zaman
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
İstenen toplam
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
Ana zorluk şudur: küçük \(k\) değerlerinde durum grafiği dallanır, büyük \(k\) değerlerinde ise yapı kısa bir deterministik zincire indirgenir.
Uygulama hibrit bir yöntem kullanır: dallanmanın gerçekten mümkün olduğu aralıkta tam genişlik öncelikli arama yapılır; \(N\) sınırı üç gayri-trivial koordinatı zaten imkansız kıldığında ise kapalı form kuyruk toplamına geçilir.
\(x_i\) dışındaki tüm koordinatlar sabitlenirse tanımlayıcı denklem tek değişkenli ikinci derece denkleme dönüşür:
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
Köklerden biri \(X=x_i\) ise Vieta bağıntıları diğer kökün
$$X'=k\prod_{j\ne i}x_j-x_i$$
olduğunu söyler. Dolayısıyla \(x_i\) yerine \(x_i'\) yazmak diziyi aynı denklem üzerinde tutar. Başlangıç dizisi \((1,\dots,1)\) geçerlidir; çünkü iki taraf da \(k\)'ye eşittir. Tam aramada incelenen bütün diziler bu değişmez hareketin tekrarlı uygulanmasıyla üretilir.
Denklem ve geçiş kuralı koordinatlara göre simetrik olduğu için sıra önemli değildir. Bu nedenle uygulama yalnızca \(1\)'den büyük girişleri artan sırayla saklar. Saklanan bir durum
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
\(k-t\) tane gizli \(1\) içeren tam \(k\)-liyi temsil eder. Bu sıkıştırma tamdır; çünkü boş çarpım \(1\)'dir ve geçişler şu hale gelir:
Bir gizli \(1\) değiştirilirse yeni değer
$$y=k\prod_{r=1}^{t}a_r-1$$
olur. Saklanan \(a_i\) değeri değiştirilirse yeni değer
$$y=k\prod_{r\ne i}a_r-a_i$$
şeklindedir.
Eğer \(y=1\) olursa o koordinat saklanan durumdan düşer. Eğer \(y>1\) ise geri eklenir ve tekrar sıralanır. Böylece \(k\)-li problemi, küçük sıralı çoklu kümeler üzerinde aramaya dönüşür.
Sabit bir \(k\) için genişlik öncelikli arama boş durumdan, yani \((1,\dots,1)\)'den başlar. Bütün girişleri en fazla \(N\) olan her erişilebilir durum tam bir kez ziyaret edilir; ziyaret edilen durumlardan herhangi birinde görülen her farklı değer de \(\mathcal{V}_k(N)\) kümesine eklenir. Durumlar sıralı çoklu küme olarak kanonik tutulduğu için koordinat permütasyonları tekrar üretmez.
Bu aşama tamdır; hiçbir kestirim veya yaklaşık formül yoktur. Yalnızca yukarıdaki geçiş denklemleri ve \(x\le N\) sınırı kullanılır. Bu yüzden \(M_k(N)\), durumların toplamı değil, erişilebilir farklı değerlerin toplamıdır.
Şunu yazalım:
$$a_0=1,\qquad a_1=k-1.$$
O halde tek saklanan girişe sahip en küçük durum \((a_1)\) olur. Bir gizli \(1\) daha değiştirildiğinde en küçük iki girişli durumun yeni değeri
$$a_2=ka_1-a_0=k^2-k-1$$
olur. Şimdi üç saklanan girişe sahip en küçük durumu soralım. Bunun en küçük oluşma yolu, minimal iki girişli durum \((a_1,a_2)\) içinden bir gizli \(1\)'i daha değiştirmektir. Bu da
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1$$
değerini üretir. Dolayısıyla \(b_3>N\) ise \(M_k(N)\)'ye katkı yapabilecek hiçbir erişilebilir dizide \(1\)'den büyük üç koordinat bulunamaz. Tam kesim noktası böylece
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}$$
şeklindedir. Uygulama \(k\le \kappa_4\) için tam arama, \(k>\kappa_4\) için formül kullanır.
Üç saklanan giriş imkansız olduğunda, ilgili her durumda en fazla iki koordinat \(1\)'den büyüktür. Bu rejimde erişilebilir değerler
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1$$
özyinelemesini izler. İlk terimler
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1$$
şeklindedir. \(k\ge 3\) için dizi sıkı biçimde artar; çünkü \(a_n>a_{n-1}\) ise
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
Bir sonraki terim
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1$$
olur ve
$$a_4-b_3=(k-2)(k^2-k-1)>0$$
eşitsizliğini sağlar. Bu yüzden \(k>\kappa_4\) olduğunda zaten \(b_3>N\) olur; dolayısıyla \(a_4>N\) ve ondan sonraki bütün zincir terimleri de \(N\)'yi aşar. Yani büyük-\(k\) aralığında yalnızca \(1\), \(a_1\), \(a_2\) ve \(a_3\) katkı verebilir.
Kalan iki eşiği
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}$$
olarak tanımlayalım. O zaman her \(k>\kappa_4\) için
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
Buradaki \(k\) terimi yalnızca \(1+(k-1)\), yani başlangıç değerinin ve ilk gayri-trivial değerin garantili toplamıdır.
\(k=4\) için zincir
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41$$
ile başlar. En küçük olası üçüncü saklanan giriş
$$b_3=4\cdot 3\cdot 11-1=131>100$$
olduğundan, \(1\)'den büyük üç giriş içeren hiçbir dizi katkı yapamaz. Bu yüzden \(100\) altında görülen tek erişilebilir değerler
$$1,\ 3,\ 11,\ 41$$
olur ve
$$M_4(100)=1+3+11+41=56.$$
\(k=3\) katkısı da eklenince toplam kontrol değeri
$$S(4,100)=229$$
çıkar; bu da programın sanity check sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce quartic kesim \(\kappa_4\) bulunur; sonra \(3\) ile \(\min(K,\kappa_4)\) arasındaki her \(k\) için tam genişlik öncelikli arama yapılır. Bir kuyruk kanonik durumları tutar, bir ziyaret kümesi tekrarları engeller, ikinci bir küme ise görülen farklı tamsayıları toplayarak her değerin \(M_k(N)\) içinde yalnızca bir kez sayılmasını sağlar.
Her geçişte, bir sonraki değerin \(N\)'yi aşıp aşamayacağını anlamak için gereken üst sınıra kadar çarpım yapılır. Böylece gereksiz büyüklükte ara çarpımlar oluşmaz ve kesin olarak fazla büyük olduğu anlaşılan dallar erkenden budanır. Bir durumda eşit girişler varsa yalnızca bir temsilci değiştirilir; çünkü özdeş koordinatları değiştirmek aynı kanonik ardıl durumu verir.
Tam arama bölgesinden sonra uygulama zincir formüllerine geçer. Üç ayrı ikili arama ile \(\kappa_2\), \(\kappa_3\) ve \(\kappa_4\) bulunur. Geri kalan katkı \(k\) cinsinden parçalı polinom olduğu için
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
kapalı ön-toplam formülleriyle \(1405695061\) modunda biriktirilir. \(2\) ve \(6\)'nın modüler tersleri de bu standart ön-toplam formüllerini mod içinde değerlendirmek için kullanılır.
Sabit bir \(k\) için tam aramada ziyaret edilen kanonik durum sayısı \(T_k(N)\) olsun. O zaman tam aşamanın maliyeti
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right)$$
şeklindedir; burada \(c_k\), sınırlı çarpımlar, ardıl üretimi ve küme işlemleri için durum başına ortalama işi temsil eder. Bellek kullanımı aktif \(k\) başına \(O(T_k(N))\)'dir ve esas olarak ziyaret edilen durumlar ile farklı sayılar kümesinden gelir.
Yapısal olarak önemli nokta, \(\kappa_4\)'ün dördüncü dereceden bir eşitsizlikten gelmesidir; bu nedenle tam dış döngü yalnızca \(O(N^{1/4})\) tane \(k\) değeri kapsar. Büyük-\(k\) kuyruğu üç ikili arama ile \(O(\log N)\) zamanda, ardından kapalı aralık toplamlarıyla \(O(1)\) aritmetikle hesaplanır. Pratikte süreyi kesim civarındaki tam aramalar belirler; kuyruk kısmı ise çok ucuzdur.
El problema estudia la ecuación de tipo Markov con \(k\) variables
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
Un paso de Vieta reemplaza una coordenada por
$$x_i'=k\prod_{j\ne i}x_j-x_i,$$
y conserva la ecuación. Partiendo de \((1,1,\dots,1)\), sea \(\mathcal{V}_k(N)\) el conjunto de enteros distintos \(x\le N\) que aparecen en al menos una tupla positiva alcanzable. Entonces
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
La cantidad pedida es
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
La dificultad principal es que para \(k\) pequeños hay un grafo de estados ramificado, mientras que para \(k\) grandes todo se reduce a una cadena corta y determinista.
La implementación usa un argumento híbrido: exploración exacta mientras todavía pueden aparecer estados con verdadera ramificación, y una cola cerrada cuando la cota \(N\) ya impide cualquier tupla con tres entradas no triviales.
Si fijamos todas las coordenadas salvo \(x_i\), la ecuación queda como un cuadrático en una variable:
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
Si una raíz es \(X=x_i\), las fórmulas de Viète muestran que la otra raíz es
$$X'=k\prod_{j\ne i}x_j-x_i.$$
Por eso, reemplazar \(x_i\) por \(x_i'\) mantiene la tupla en la misma ecuación. La semilla \((1,\dots,1)\) es válida porque ambos lados valen \(k\). Todas las tuplas del tramo exacto se generan aplicando repetidamente este mismo movimiento invariante.
La ecuación y el movimiento son simétricos en las coordenadas, de modo que el orden no importa. Por eso solo se almacenan las entradas mayores que \(1\), ordenadas de menor a mayor. Un estado almacenado
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
representa la \(k\)-tupla completa con \(k-t\) unos ocultos. La compresión es exacta porque el producto vacío vale \(1\), y las transiciones quedan así:
Si se reemplaza un \(1\) oculto, el valor nuevo es
$$y=k\prod_{r=1}^{t}a_r-1.$$
Si se reemplaza la entrada almacenada \(a_i\), el valor nuevo es
$$y=k\prod_{r\ne i}a_r-a_i.$$
Si \(y=1\), esa coordenada simplemente desaparece del estado almacenado. Si \(y>1\), se vuelve a insertar y el estado se reordena. Así, el problema de \(k\)-tuplas se convierte en una búsqueda sobre multisets ordenados pequeños.
Para un \(k\) fijo, una búsqueda en anchura empieza en el estado vacío, que representa \((1,\dots,1)\). Cada estado alcanzable cuyas entradas no superan \(N\) se visita una sola vez, y todo valor distinto que aparezca en algún estado visitado se agrega a \(\mathcal{V}_k(N)\). Como los estados se guardan en forma canónica, como multisets ordenados, las permutaciones de coordenadas no crean duplicados.
Esta fase es exacta: no usa heurísticas, solo las fórmulas de transición anteriores y la restricción \(x\le N\). Por tanto, \(M_k(N)\) es la suma de los valores distintos alcanzables, no la suma sobre los estados.
Sea
$$a_0=1,\qquad a_1=k-1.$$
El estado más pequeño con una sola entrada almacenada es entonces \((a_1)\). Si reemplazamos otro \(1\) oculto, obtenemos el valor nuevo más pequeño posible para un estado con dos entradas:
$$a_2=ka_1-a_0=k^2-k-1.$$
Ahora buscamos el estado más pequeño con tres entradas almacenadas. La forma mínima de crearlo es partir del estado mínimo de dos entradas \((a_1,a_2)\) y reemplazar un tercer \(1\) oculto. Eso produce
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1.$$
Por tanto, si \(b_3>N\), ninguna tupla alcanzable que contribuya a \(M_k(N)\) puede contener tres coordenadas mayores que \(1\). Esto da el corte exacto
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}.$$
La implementación trata de forma exacta los \(k\le \kappa_4\) y usa fórmulas para \(k>\kappa_4\).
Una vez que tres entradas almacenadas son imposibles, todo estado relevante tiene como mucho dos coordenadas mayores que \(1\). En ese régimen los valores alcanzables siguen la recurrencia
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1.$$
Los primeros términos son
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1.$$
Para \(k\ge 3\), la sucesión crece estrictamente: si \(a_n>a_{n-1}\), entonces
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
El siguiente término es
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1,$$
y satisface
$$a_4-b_3=(k-2)(k^2-k-1)>0.$$
Así, si \(k>\kappa_4\), ya tenemos \(b_3>N\), por lo que también \(a_4>N\), y con más razón todos los términos posteriores. En la zona de \(k\) grande solo pueden contribuir \(1\), \(a_1\), \(a_2\) y \(a_3\).
Definimos los otros dos umbrales
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}.$$
Entonces, para todo \(k>\kappa_4\),
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
El término \(k\) no es más que \(1+(k-1)\), es decir, la contribución segura del valor semilla y del primer valor no trivial.
Para \(k=4\), la cadena empieza con
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41.$$
La tercera entrada almacenada mínima posible es
$$b_3=4\cdot 3\cdot 11-1=131>100.$$
Por tanto, ninguna tupla con tres entradas mayores que \(1\) puede contribuir. Los únicos valores alcanzables hasta \(100\) son
$$1,\ 3,\ 11,\ 41,$$
y de ahí
$$M_4(100)=1+3+11+41=56.$$
Si además se suma la contribución con \(k=3\), el valor total de comprobación es
$$S(4,100)=229,$$
exactamente el mismo que usa el programa para validarse.
Las implementaciones en C++, Python y Java comparten la misma estructura. Primero calculan el corte cuártico \(\kappa_4\) y ejecutan una búsqueda exacta en anchura para cada \(k\) desde \(3\) hasta \(\min(K,\kappa_4)\). Una cola guarda los estados canónicos, un conjunto de visitados evita repeticiones y un segundo conjunto registra los enteros distintos que han aparecido, para que cada valor se cuente una sola vez dentro de \(M_k(N)\).
En cada transición, la implementación solo multiplica hasta la cota necesaria para decidir si el siguiente valor aún podría ser \(\le N\). Eso evita productos intermedios gigantes y poda las ramas tan pronto como se sabe que ya son demasiado grandes. Si un estado contiene varias entradas iguales, basta probar un único reemplazo representativo, porque sustituir coordenadas idénticas lleva al mismo sucesor canónico.
Después del tramo exacto, la implementación pasa a las fórmulas de la cadena. Tres búsquedas binarias encuentran \(\kappa_2\), \(\kappa_3\) y \(\kappa_4\). La contribución restante se expresa como una función polinómica a trozos de \(k\), por lo que se acumula mediante fórmulas cerradas para
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
módulo \(1405695061\). Se usan inversos modulares de \(2\) y \(6\) para evaluar las fórmulas habituales de sumas prefijo dentro del módulo.
Sea \(T_k(N)\) el número de estados canónicos visitados por la búsqueda exacta para un \(k\) fijo. Entonces el coste de la fase exacta es
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right),$$
donde \(c_k\) representa el trabajo medio por estado para productos acotados, construcción de sucesores y operaciones sobre conjuntos. La memoria de esa fase es \(O(T_k(N))\) por cada \(k\) activo, dominada por los estados visitados y por el conjunto de valores distintos.
El hecho estructural importante es que \(\kappa_4\) proviene de una desigualdad cuártica, así que el bucle exterior exacto cubre solo \(O(N^{1/4})\) valores de \(k\). La cola de \(k\) grandes requiere únicamente tres búsquedas binarias, es decir \(O(\log N)\) tiempo, más aritmética \(O(1)\) para las sumas cerradas por intervalos. En la práctica, el tiempo lo domina la exploración exacta cerca del corte, y la cola cerrada cuesta muy poco.
这道题研究的是 \(k\) 变量的 Markov 型方程
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
一次 Vieta 型替换选择某个坐标，并把它改成
$$x_i'=k\prod_{j\ne i}x_j-x_i,$$
这个变换会保持方程不变。从初始点 \((1,1,\dots,1)\) 出发，记 \(\mathcal{V}_k(N)\) 为所有满足 \(x\le N\) 且在至少一个可达正整数元组中出现过的不同整数集合。于是
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
最终要求的是
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
真正的难点在于：当 \(k\) 较小时，可达状态图会发生明显分叉；当 \(k\) 足够大时，所有可达值会退化成一条很短的确定性链。
实现采用的是混合策略：只要还可能出现真正分叉，就做精确的宽度优先搜索；一旦上界 \(N\) 已经排除了“三个非平凡坐标同时存在”的情形，就改用闭式公式求大 \(k\) 的尾部贡献。
把除了 \(x_i\) 之外的坐标都固定，原方程就变成关于单个变量的二次方程：
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
如果其中一个根是 \(X=x_i\)，那么由 Viète 关系，另一个根一定是
$$X'=k\prod_{j\ne i}x_j-x_i.$$
所以把 \(x_i\) 替换成 \(x_i'\) 之后，新的元组仍然落在同一条方程上。初始元组 \((1,\dots,1)\) 显然合法，因为左右两边都等于 \(k\)。精确搜索中出现的所有元组，都是从这个起点通过重复应用同一个不变量变换得到的。
因为方程和替换规则对各个坐标完全对称，所以坐标顺序不重要。实现里只存储那些严格大于 \(1\) 的值，并按从小到大排序。一个存储状态
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
表示完整的 \(k\) 元组里还有 \(k-t\) 个隐藏的 \(1\)。这种压缩没有信息损失，因为空积等于 \(1\)，而替换公式可以改写成：
如果替换的是一个隐藏的 \(1\)，新值就是
$$y=k\prod_{r=1}^{t}a_r-1.$$
如果替换的是存储中的 \(a_i\)，新值就是
$$y=k\prod_{r\ne i}a_r-a_i.$$
如果 \(y=1\)，那么这个坐标就不再需要存储；如果 \(y>1\)，就把它重新插入并保持有序。这样一来，原来的 \(k\) 元组问题就变成了“对小型有序多重集做搜索”。
对固定的 \(k\)，宽度优先搜索从空状态开始，也就是从 \((1,\dots,1)\) 开始。所有元素都不超过 \(N\) 的可达状态都会被精确访问一次，任何出现在这些状态中的不同整数都会被加入 \(\mathcal{V}_k(N)\)。由于状态按“有序多重集”的规范形式存储，所以坐标置换不会产生重复状态。
这一阶段完全是精确计算，不依赖启发式猜测。它只使用上面推导出的替换公式和约束 \(x\le N\)。因此 \(M_k(N)\) 统计的是“所有不同可达值的和”，而不是“所有状态里数字的重复累计”。
设
$$a_0=1,\qquad a_1=k-1.$$
于是，只有一个存储值时的最小状态就是 \((a_1)\)。再替换一个隐藏的 \(1\)，就得到最小的双非平凡状态，新值为
$$a_2=ka_1-a_0=k^2-k-1.$$
接下来问：最小的三非平凡状态会长什么样？显然应该从最小的双非平凡状态 \((a_1,a_2)\) 出发，再替换一个隐藏的 \(1\)。这会产生
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1.$$
因此，只要 \(b_3>N\)，就说明任何能对 \(M_k(N)\) 作出贡献的可达元组，都不可能含有三个大于 \(1\) 的坐标。于是得到精确分界
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}.$$
程序对 \(k\le \kappa_4\) 做完整搜索，而对 \(k>\kappa_4\) 直接使用公式。
一旦三个非平凡坐标不可能出现，每个相关状态中就最多只有两个坐标大于 \(1\)。在这种情况下，可达值满足线性递推
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1.$$
前几个值是
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1.$$
对所有 \(k\ge 3\)，这个序列严格递增：如果 \(a_n>a_{n-1}\)，那么
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
再往后一个值是
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1,$$
并且满足
$$a_4-b_3=(k-2)(k^2-k-1)>0.$$
这意味着：如果 \(k>\kappa_4\)，那么必有 \(b_3>N\)，从而 \(a_4>N\)，更后面的所有链项也一定都大于 \(N\)。因此，在大 \(k\) 区间里，真正可能贡献的只有 \(1\)、\(a_1\)、\(a_2\)、\(a_3\) 这四项。
再定义另外两个阈值
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}.$$
那么对任意 \(k>\kappa_4\)，都有
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
这里的 \(k\) 其实就是 \(1+(k-1)\)，也就是种子值和第一个非平凡值的必然贡献。
当 \(k=4\) 时，这条链的开头是
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41.$$
最小可能的第三个非平凡值是
$$b_3=4\cdot 3\cdot 11-1=131>100.$$
所以任何含有三个大于 \(1\) 的坐标的元组都不可能落在界内。于是 \(100\) 以下能出现的值只有
$$1,\ 3,\ 11,\ 41,$$
从而
$$M_4(100)=1+3+11+41=56.$$
再加上 \(k=3\) 的贡献，就得到整体校验值
$$S(4,100)=229,$$
这与程序中的 sanity check 完全一致。
C++、Python 和 Java 三个实现采用的是同一套框架。首先计算四次阈值 \(\kappa_4\)，然后对每个 \(3\le k\le \min(K,\kappa_4)\) 分别执行一次精确宽搜。队列保存规范化后的状态，访问集合负责去重，另一个集合专门收集出现过的不同整数，确保同一个值在 \(M_k(N)\) 中只被计一次。
在生成后继状态时，实现只会把乘积算到足以判断“下一个值是否还可能 \(\le N\)”为止。这样可以避免构造不必要的大中间数，也能在确定分支超界时立刻剪枝。如果某个状态里有多个相等的值，只需要尝试其中一个代表性替换，因为替换相同坐标得到的规范化后继完全一样。
离开精确区间后，实现转入链式闭公式。三个二分搜索分别求出 \(\kappa_2\)、\(\kappa_3\)、\(\kappa_4\)。剩余部分的贡献是 \(k\) 的分段多项式，因此可以用
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
的前缀和公式在模 \(1405695061\) 下直接累计。实现中还使用了 \(2\) 和 \(6\) 的模逆元来写出这些标准求和公式。
记 \(T_k(N)\) 为固定 \(k\) 时精确搜索访问到的规范化状态数。则精确阶段的时间复杂度为
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right),$$
其中 \(c_k\) 表示每个状态平均需要的工作量，包括受限乘法、后继构造以及集合操作。该阶段的空间复杂度对每个活动 \(k\) 是 \(O(T_k(N))\)，主要由已访问状态和不同值集合决定。
结构上最关键的一点是：\(\kappa_4\) 来自一个四次不等式，所以精确外层循环只覆盖 \(O(N^{1/4})\) 个 \(k\)。而大 \(k\) 尾部只需要三次二分搜索，也就是 \(O(\log N)\) 时间，再加上 \(O(1)\) 的闭式区间求和。实际运行时，时间主要花在接近分界点的精确搜索上，尾部公式几乎可以忽略不计。
Задача рассматривает \(k\)-переменное уравнение марковского типа
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
Один шаг Виета заменяет выбранную координату на
$$x_i'=k\prod_{j\ne i}x_j-x_i,$$
и сохраняет уравнение. Начиная с \((1,1,\dots,1)\), обозначим через \(\mathcal{V}_k(N)\) множество различных целых чисел \(x\le N\), которые встречаются хотя бы в одном достижимом положительном кортеже. Тогда
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
Нужно вычислить
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
Главная трудность в том, что при малых \(k\) граф достижимых состояний ветвится, а при больших \(k\) вся структура сжимается до короткой детерминированной цепочки.
Реализация использует гибридную схему: точный поиск в ширину, пока возможны настоящие ветвления, и закрытую формулу для хвоста, когда ограничение \(N\) уже исключает состояния с тремя нетривиальными координатами.
Если зафиксировать все координаты, кроме \(x_i\), то определяющее уравнение становится квадратным уравнением относительно одной переменной:
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
Если один корень равен \(X=x_i\), то по формулам Виета второй корень равен
$$X'=k\prod_{j\ne i}x_j-x_i.$$
Значит, замена \(x_i\) на \(x_i'\) оставляет кортеж на той же поверхности. Начальный кортеж \((1,\dots,1)\) корректен, потому что обе части равны \(k\). Все кортежи, которые рассматриваются в точной части, получаются именно повторением этого инвариантного преобразования.
Уравнение и переход симметричны по координатам, поэтому порядок несущественен. Реализация хранит только значения, большие \(1\), в отсортированном виде. Состояние
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
обозначает полный \(k\)-кортеж с \(k-t\) скрытыми единицами. Такое сжатие абсолютно точное, поскольку пустое произведение равно \(1\), а формулы переходов становятся
Если заменяется скрытая \(1\), то новое значение равно
$$y=k\prod_{r=1}^{t}a_r-1.$$
Если заменяется сохранённое \(a_i\), то новое значение равно
$$y=k\prod_{r\ne i}a_r-a_i.$$
Если \(y=1\), то соответствующая координата просто исчезает из сохранённого состояния. Если \(y>1\), она вставляется обратно, и состояние снова сортируется. Так задача о \(k\)-кортежах превращается в поиск по малым отсортированным мультимножествам.
Для фиксированного \(k\) поиск в ширину начинается с пустого сохранённого состояния, то есть с \((1,\dots,1)\). Каждое достижимое состояние, все элементы которого не превосходят \(N\), посещается ровно один раз, а каждое различное число, появившееся хотя бы в одном посещённом состоянии, добавляется в \(\mathcal{V}_k(N)\). Поскольку состояния хранятся в каноническом виде как отсортированные мультимножества, перестановки координат не создают дубликатов.
Эта фаза полностью точна: в ней нет эвристик, только выведенные выше формулы переходов и ограничение \(x\le N\). Поэтому \(M_k(N)\) — это сумма различных достижимых значений, а не сумма по состояниям с повторами.
Положим
$$a_0=1,\qquad a_1=k-1.$$
Тогда минимальное состояние с одной сохранённой координатой — это \((a_1)\). Если заменить ещё одну скрытую единицу, получится минимально возможное состояние с двумя сохранёнными значениями и новым числом
$$a_2=ka_1-a_0=k^2-k-1.$$
Теперь спросим, каким будет минимальное состояние с тремя сохранёнными значениями. Наименьший вариант получается из минимального двухэлементного состояния \((a_1,a_2)\) заменой ещё одной скрытой единицы. Это даёт
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1.$$
Следовательно, если \(b_3>N\), ни один достижимый кортеж, вносящий вклад в \(M_k(N)\), не может содержать три координаты больше \(1\). Отсюда получается точный порог
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}.$$
Реализация считает точно все \(k\le \kappa_4\) и использует формулы для \(k>\kappa_4\).
Когда состояния с тремя сохранёнными значениями невозможны, в любом релевантном состоянии остаётся не более двух координат, больших \(1\). В этом режиме достижимые значения подчиняются рекуррентному соотношению
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1.$$
Первые члены равны
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1.$$
Для \(k\ge 3\) последовательность строго возрастает: если \(a_n>a_{n-1}\), то
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
Следующий член равен
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1,$$
и для него выполняется
$$a_4-b_3=(k-2)(k^2-k-1)>0.$$
Поэтому из \(k>\kappa_4\) следует \(b_3>N\), а значит, и \(a_4>N\), и тем более все более поздние члены цепочки. Значит, в области больших \(k\) вклад могут давать только \(1\), \(a_1\), \(a_2\) и \(a_3\).
Введём ещё два порога:
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}.$$
Тогда для любого \(k>\kappa_4\)
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
Член \(k\) — это просто \(1+(k-1)\), то есть гарантированный вклад начального значения и первого нетривиального значения.
При \(k=4\) цепочка начинается так:
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41.$$
Минимально возможное третье нетривиальное значение равно
$$b_3=4\cdot 3\cdot 11-1=131>100.$$
Значит, ни один кортеж с тремя координатами больше \(1\) уже не может участвовать. Поэтому все достижимые значения до \(100\) — это
$$1,\ 3,\ 11,\ 41,$$
и потому
$$M_4(100)=1+3+11+41=56.$$
Если добавить вклад случая \(k=3\), получится общий проверочный результат
$$S(4,100)=229,$$
который совпадает со встроенной проверкой программы.
Реализации на C++, Python и Java устроены одинаково. Сначала вычисляется квартовый порог \(\kappa_4\), затем для каждого \(k\) от \(3\) до \(\min(K,\kappa_4)\) запускается точный поиск в ширину. Очередь хранит канонические состояния, множество посещённых не допускает повторов, а второе множество собирает все различные встреченные числа, чтобы каждое значение учитывалось в \(M_k(N)\) ровно один раз.
При каждом переходе произведение вычисляется только до той границы, которая нужна для ответа на вопрос: может ли следующий элемент ещё быть не больше \(N\). Это предотвращает ненужные огромные промежуточные числа и обрезает ветви сразу, как только ясно, что они уже вышли за предел. Если в состоянии несколько одинаковых значений, достаточно попробовать замену только для одного представителя, потому что одинаковые координаты ведут к одному и тому же каноническому потомку.
После точного диапазона реализация переходит к формулам для цепочки. Три бинарных поиска находят \(\kappa_2\), \(\kappa_3\) и \(\kappa_4\). Оставшийся вклад выражается как кусочно-полиномиальная функция от \(k\), поэтому его можно суммировать по закрытым формулам для
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
по модулю \(1405695061\). Для стандартных формул префиксных сумм используются модульные обратные к \(2\) и \(6\).
Пусть \(T_k(N)\) — число канонических состояний, посещённых точным поиском при фиксированном \(k\). Тогда стоимость точной фазы равна
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right),$$
где \(c_k\) — средняя работа на одно состояние: ограниченные произведения, построение потомков и операции со множествами. Память этой фазы составляет \(O(T_k(N))\) на один активный \(k\); доминируют множество посещённых состояний и множество различных чисел.
Ключевой структурный факт состоит в том, что \(\kappa_4\) задаётся неравенством четвёртой степени, а значит, внешний точный цикл охватывает только \(O(N^{1/4})\) значений \(k\). Хвост для больших \(k\) требует лишь трёх бинарных поисков, то есть \(O(\log N)\) времени, плюс \(O(1)\) арифметики для закрытых сумм по интервалам. На практике время определяется точным поиском около порога, а хвост считается почти мгновенно.
تدرس المسألة المعادلة الماركوفيّة ذات \(k\) متغيرات
$$x_1^2+x_2^2+\cdots+x_k^2=kx_1x_2\cdots x_k.$$
وتبديل فييتا يستبدل أحد الإحداثيات بالقيمة
$$x_i'=k\prod_{j\ne i}x_j-x_i,$$
مع بقاء المعادلة صحيحة. انطلاقًا من \((1,1,\dots,1)\)، نرمز بـ \(\mathcal{V}_k(N)\) إلى مجموعة الأعداد الصحيحة المختلفة \(x\le N\) التي تظهر في حل موجب قابل للوصول واحد على الأقل. وعندئذٍ
$$M_k(N)=\sum_{x\in \mathcal{V}_k(N)}x.$$
والكمية المطلوبة هي
$$S(K,N)=\sum_{k=3}^{K} M_k(N)\pmod{1405695061}.$$
الصعوبة الأساسية أن القيم الصغيرة لـ \(k\) تعطي رسم حالات متشعبًا، بينما القيم الكبيرة لـ \(k\) تختزل البنية كلها إلى سلسلة قصيرة حتمية.
تستخدم الخوارزمية منهجًا هجينًا: بحثًا دقيقًا بعرض المستوى ما دام التشعب الحقيقي ممكنًا، ثم صيغة مغلقة للذيل عندما يصبح القيد \(N\) كافيًا لاستبعاد أي حالة فيها ثلاث إحداثيات غير تافهة.
إذا ثبتنا جميع الإحداثيات ما عدا \(x_i\)، فإن المعادلة الأصلية تصبح معادلة تربيعية في متغير واحد:
$$X^2-k\left(\prod_{j\ne i}x_j\right)X+\sum_{j\ne i}x_j^2=0.$$
إذا كان أحد الجذرين هو \(X=x_i\)، فإن علاقات فييتا تعطي الجذر الآخر على الصورة
$$X'=k\prod_{j\ne i}x_j-x_i.$$
لذلك فإن استبدال \(x_i\) بـ \(x_i'\) يبقي المتجه على نفس المعادلة. والبذرة \((1,\dots,1)\) صحيحة لأن طرفي المعادلة يساويان \(k\). وكل الحالات التي يفحصها الجزء الدقيق تتولد من هذه البذرة بتكرار نفس الحركة الثابتة.
بما أن المعادلة وقاعدة الانتقال متناظرتان بالنسبة إلى الإحداثيات، فإن ترتيبها لا يهم. لذلك تُخزَّن فقط القيم الأكبر من \(1\) بعد ترتيبها تصاعديًا. والحالة المخزنة
$$a_1\le a_2\le \cdots \le a_t,\qquad a_r>1,$$
تمثل المتجه الكامل ذي \(k-t\) من الواحدات المخفية. وهذا الضغط دقيق تمامًا لأن حاصل الضرب الفارغ يساوي \(1\)، وتصبح صيغ الانتقال
إذا استُبدلت \(1\) مخفية فإن القيمة الجديدة هي
$$y=k\prod_{r=1}^{t}a_r-1.$$
وإذا استُبدلت القيمة المخزنة \(a_i\) فإن القيمة الجديدة هي
$$y=k\prod_{r\ne i}a_r-a_i.$$
إذا كان \(y=1\) فإن هذه الإحداثية تختفي من الحالة المخزنة. وإذا كان \(y>1\) فإنها تُدرج من جديد مع إعادة الترتيب. بهذه الطريقة تتحول المسألة من \(k\)-متجهات إلى بحث على متعددات مجموعات مرتبة صغيرة.
لكل \(k\) ثابت، يبدأ بحث العرض من الحالة الفارغة، أي من \((1,\dots,1)\). وكل حالة يمكن الوصول إليها وتبقى عناصرها جميعًا \(\le N\) تُزار مرة واحدة فقط، وكل قيمة مختلفة تظهر في إحدى هذه الحالات تُضاف إلى \(\mathcal{V}_k(N)\). ولأن الحالات تُحفظ بصيغة قانونية كمتعدد مجموعة مرتب، فإن تبديل الإحداثيات لا يولد نسخًا مكررة.
هذه المرحلة دقيقة بالكامل؛ فهي لا تعتمد على تقريب أو تخمين، بل فقط على صيغ الانتقال السابقة وعلى القيد \(x\le N\). لذلك فإن \(M_k(N)\) هو مجموع القيم المختلفة القابلة للوصول، لا مجموع القيم عبر جميع الحالات مع التكرار.
لنضع
$$a_0=1,\qquad a_1=k-1.$$
إذن أصغر حالة ممكنة تحتوي قيمة مخزنة واحدة هي \((a_1)\). وإذا استبدلنا \(1\) مخفيًا آخر نحصل على أصغر حالة ممكنة ذات قيمتين مخزنتين، والقيمة الجديدة فيها هي
$$a_2=ka_1-a_0=k^2-k-1.$$
والآن نبحث عن أصغر حالة ممكنة فيها ثلاث قيم مخزنة. أصغر طريقة لبنائها هي الانطلاق من الحالة الدنيا ذات القيمتين \((a_1,a_2)\) ثم استبدال \(1\) مخفي ثالث. وهذا يعطي
$$b_3=ka_1a_2-1=k(k-1)(k^2-k-1)-1.$$
وعليه، إذا كان \(b_3>N\)، فلا توجد أي حالة قابلة للوصول وتساهم في \(M_k(N)\) يمكن أن تحتوي ثلاث إحداثيات أكبر من \(1\). ومن هنا نحصل على حد القطع الدقيق
$$\kappa_4=\max\left\{k\ge 3: k(k-1)(k^2-k-1)-1\le N\right\}.$$
تتعامل الخوارزمية تعاملاً دقيقًا مع جميع \(k\le \kappa_4\)، وتستخدم الصيغ المغلقة عندما يكون \(k>\kappa_4\).
بمجرد أن تصبح الحالات ذات الثلاث قيم المخزنة مستحيلة، فإن كل حالة ذات صلة تحتوي على أكثر تقدير قيمتين أكبر من \(1\). في هذا النظام تتبع القيم القابلة للوصول العلاقة التراجعية
$$a_{n+1}=ka_n-a_{n-1},\qquad a_0=1,\qquad a_1=k-1.$$
وأول حدودها هي
$$a_2=k^2-k-1,\qquad a_3=k^3-k^2-2k+1.$$
ولكل \(k\ge 3\) تكون هذه المتتالية متزايدة تمامًا: فإذا كان \(a_n>a_{n-1}\) فإن
$$a_{n+1}=ka_n-a_{n-1}>2a_n-a_{n-1}>a_n.$$
والحد التالي هو
$$a_4=ka_3-a_2=k^4-k^3-3k^2+2k+1,$$
ويحقق
$$a_4-b_3=(k-2)(k^2-k-1)>0.$$
إذن إذا كان \(k>\kappa_4\) فلدينا أصلًا \(b_3>N\)، ومن ثم \(a_4>N\)، وبالتبعية كل الحدود اللاحقة أيضًا. لذلك لا يمكن أن تسهم في مجال \(k\) الكبير إلا القيم \(1\) و\(a_1\) و\(a_2\) و\(a_3\).
ونعرّف الحدين الآخرين
$$\kappa_2=\max\left\{k\ge 3: k^2-k-1\le N\right\},$$
$$\kappa_3=\max\left\{k\ge 3: k^3-k^2-2k+1\le N\right\}.$$
وعندئذٍ لكل \(k>\kappa_4\)
$$M_k(N)=k+\begin{cases} k^2-k-1,&k\le \kappa_2,\\ 0,&k>\kappa_2, \end{cases} +\begin{cases} k^3-k^2-2k+1,&k\le \kappa_3,\\ 0,&k>\kappa_3. \end{cases}$$
والحد \(k\) هنا ليس إلا \(1+(k-1)\)، أي مساهمة القيمة الابتدائية والقيمة غير التافهة الأولى.
عند \(k=4\) تبدأ السلسلة بالقيم
$$a_0=1,\qquad a_1=3,\qquad a_2=11,\qquad a_3=41.$$
وأصغر قيمة ثالثة غير تافهة ممكنة هي
$$b_3=4\cdot 3\cdot 11-1=131>100.$$
إذًا لا يمكن لأي حالة فيها ثلاث قيم أكبر من \(1\) أن تسهم ضمن هذا الحد. وبالتالي فإن القيم الوحيدة القابلة للوصول حتى \(100\) هي
$$1,\ 3,\ 11,\ 41,$$
ومن ثم
$$M_4(100)=1+3+11+41=56.$$
وبإضافة مساهمة \(k=3\) نحصل على قيمة الفحص الكلية
$$S(4,100)=229,$$
وهي تمامًا نفس قيمة التحقق الموجودة في البرنامج.
تتبع تطبيقات C++ وPython وJava البنية نفسها. في البداية تُحسب العتبة الرباعية \(\kappa_4\)، ثم يُنفذ بحث عرضي دقيق لكل \(k\) من \(3\) حتى \(\min(K,\kappa_4)\). يحتفظ الطابور بالحالات القانونية، وتمنع مجموعة الزيارة التكرار، بينما تجمع مجموعة ثانية الأعداد المختلفة التي ظهرت بالفعل كي لا يُحسب أي عدد أكثر من مرة داخل \(M_k(N)\).
أثناء كل انتقال، لا تُحسب الضروب إلا حتى الحد اللازم لاتخاذ قرار ما إذا كانت القيمة التالية قد تبقى \(\le N\) أم لا. وهذا يمنع الأعداد الوسيطة الضخمة غير الضرورية ويقص الفروع فور التأكد من أنها تجاوزت الحد. وإذا احتوت الحالة على عدة قيم متساوية، فتكفي تجربة استبدال واحدة ممثلة، لأن استبدال إحداثيات متطابقة يؤدي إلى الخليفة القانوني نفسه.
بعد المنطقة الدقيقة تنتقل الشيفرة إلى صيغ السلسلة. ثلاث عمليات بحث ثنائي تحدد \(\kappa_2\) و\(\kappa_3\) و\(\kappa_4\). ثم تُكتب المساهمة الباقية على صورة دالة متعددة حدود مقطعية في \(k\)، فتُجمع باستخدام الصيغ المغلقة لـ
$$\sum k,\qquad \sum k^2,\qquad \sum k^3$$
بترديد \(1405695061\). كما تُستخدم المقلوبات الضربية لـ \(2\) و\(6\) داخل هذا الترديد من أجل صيغ المجاميع الابتدائية المعتادة.
لنرمز بـ \(T_k(N)\) إلى عدد الحالات القانونية التي يزورها البحث الدقيق عند قيمة ثابتة لـ \(k\). عندئذ تكون كلفة المرحلة الدقيقة
$$O\left(\sum_{k=3}^{\min(K,\kappa_4)} T_k(N)\cdot c_k\right),$$
حيث يمثّل \(c_k\) متوسط العمل لكل حالة من حيث الضروب المحدودة، وبناء الخلفاء، وعمليات المجموعات. أما الذاكرة في تلك المرحلة فهي \(O(T_k(N))\) لكل \(k\) نشط، وتُهيمن عليها مجموعة الحالات المزارة ومجموعة القيم المختلفة.
والحقيقة البنيوية الأهم هي أن \(\kappa_4\) تأتي من متراجحة رباعية الدرجة، ولذلك فإن الحلقة الخارجية الدقيقة لا تغطي إلا \(O(N^{1/4})\) من قيم \(k\). أما الذيل الكبير فيحتاج فقط إلى ثلاث عمليات بحث ثنائي، أي \(O(\log N)\) زمنًا، ثم \(O(1)\) حسابًا لصيغ المجاميع المغلقة على المجالات. عمليًا، يهيمن على الزمن الجزء الدقيق قرب العتبة، بينما يكون الذيل المغلق زهيد الكلفة.