Problem 949 assigns a recursive left-versus-right position to every binary word \(w\) of length \(n\). The one-bit words are the starting numbers \(0\mapsto +1\) and \(1\mapsto -1\). For longer words, the recurrence treats proper suffixes as options on one side of the game and proper prefixes as options on the other. The implementations do not keep the full game tree; instead, they compute a signed score \(u(w)\) together with a cold/non-cold classification.
The target quantity is \(G(20,7)\bmod 1001001011\). Direct enumeration is impossible: there are \(2^{20}\) words of length 20 and therefore \((2^{20})^7\) ordered 7-tuples. The successful strategy is to evaluate each single word once, compress equal scores into histograms, and then count tuples by convolving those histograms.
All three implementations follow the same two-stage plan. First they solve the single-word recurrence for every binary string up to length \(n\). Then they turn the multiset of resulting scores into a counting problem on discrete distributions.
For a word \(w\) of length \(\ell\ge 2\), let \(\mathrm{Suf}(w)\) be the set of proper suffixes of \(w\), and let \(\mathrm{Pre}(w)\) be the set of proper prefixes. Every such option is shorter than \(w\), so a bottom-up dynamic program by increasing length is valid.
Each shorter word \(t\) carries two stored endpoints \(u(t)\) and \(d(t)\). The new raw bounds are
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$
The one-bit layer is initialized as
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$
after a global scaling that will be described next. Those formulas are the real core of the problem: every later value is forced by the best suffix-side bound and the best prefix-side bound coming from shorter words.
The solutions represent every value on the dyadic grid with denominator dividing \(2^n\). Instead of storing a rational number directly, they multiply everything by \(2^n\) and store integers. A dyadic number \(p/2^m\) is therefore encoded as \(p\,2^{\,n-m}\).
This choice makes all comparisons exact and keeps the recurrence purely integer-based. The floor and ceiling operations that appear when searching for a new value become simple divisions by powers of two. Because the recursion depth is at most \(n\), this dyadic representation is sufficient for every value created by the algorithm.
If the raw bounds satisfy
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$
then the word falls into the cold bucket. In that case the implementations choose a single canonical dyadic number \(x\) strictly between those two bounds and set
$$u(w)=d(w)=x.$$
The chosen \(x\) is the simplest dyadic in the open interval \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\): the search tries coarse denominators first, so the first successful scale gives the smallest denominator; within that scale it prefers \(0\) if available, otherwise the admissible numerator closest to \(0\); and for non-integer dyadics it keeps the numerator odd so the representation is already reduced.
If there is no strict gap, the state is kept as non-cold and the implementations simply store
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$
This distinction matters later: only the cold states collapse to one exact number, while the non-cold states retain only their left-end score \(u(w)\) for the final count.
Once all words of length \(n\) have been processed, only two pieces of information are needed for each word: its stored score \(u(w)\) and whether it was cold. The implementations therefore compress the full layer into two histograms,
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\text{ and }w\text{ is cold}\}.$$
This is the step that removes the exponential blow-up in \(k\). Many different words share the same score, so the tuple problem can be solved on score frequencies instead of on individual words.
For odd \(k\), set
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$
Let \(D_a\) and \(D_b\) be the \(a\)-fold and \(b\)-fold convolutions of \(H_{\mathrm{all}}\), and let \(C_a\) and \(C_b\) be the corresponding convolution powers of \(H_{\mathrm{cold}}\). Thus \(D_a(s)\) is the number of ordered \(a\)-tuples of length-\(n\) words whose stored scores sum to \(s\), and similarly for the other distributions.
The answer is then
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$
The first term counts all ordered \(k\)-tuples whose total stored score is negative. The second term adds the exact-zero cases, but only when every component comes from the cold histogram. Splitting the tuple into an \(a\)-part and a \(b\)-part is only a counting device; it preserves the total sum because \(a+b=k\).
For \(n=2\), the global scale is \(2^2=4\). The four binary words are \(00,01,10,11\).
For \(00\), both the only proper suffix and the only proper prefix are \(0\), so the stored score is \(+4\). For \(11\), the same reasoning gives \(-4\). For \(01\), the suffix contributes \(-4\) and the prefix contributes \(+4\), so there is a strict gap and the simplest dyadic between them is \(0\); this word is cold. For \(10\), the raw bounds are reversed, so the word is non-cold and keeps stored score \(+4\).
After dividing by the common scale, the multiset of scores is therefore
$$\{1,0,1,-1\},$$
and the only cold word has score \(0\). Now count ordered triples. Negative totals occur in exactly four patterns:
$$(-1,-1,-1)\quad\text{gives }1,$$
$$(-1,-1,0)\quad\text{gives }3,$$
$$(-1,0,0)\quad\text{gives }3,$$
$$(-1,-1,+1)\quad\text{gives }3\cdot 2=6,$$
because the \(+1\) entry can be chosen from two distinct words. Altogether this gives \(1+3+3+6=13\) negative triples. The only cold zero-sum triple is \((01,01,01)\), contributing one more case, so
$$G(2,3)=13+1=14,$$
which matches the built-in check used by the C++ implementation.
The implementations enumerate all non-empty binary words of lengths \(1,2,\dots,n\) level by level. For each final-layer word they inspect every proper suffix length and every proper prefix length, form the two raw bounds, and either collapse the state to one canonical dyadic number or keep the raw endpoints. The C++ version can parallelize the loop over words of a fixed length with OpenMP; the Python and Java versions execute the same recurrence serially.
After the layer of length \(n\) is complete, the implementations no longer need the full prefix/suffix structure. They sweep once over the final scores, count how often each score appears, and separately count how often it appears among cold words. This produces the all-words histogram and the cold-only histogram described above.
Because \(k=7\) is small, the implementations build the required convolution powers by repeated hash-map convolution rather than by FFT-style machinery. To count negative totals, one of the two resulting supports is sorted and prefix-summed, so every score from the other side can add all compatible partners with a single binary search. Exact-zero cold totals are even simpler: they are found by matching a score with its negation in the opposite cold distribution.
The dynamic program processes every binary word of length at most \(n\), so it visits \((2^{n+1}-2)\) states in total. For each state it scans all proper suffix lengths and all proper prefix lengths, and in the cold case it may search through up to \(n\) dyadic scales. This gives overall time \(O(n2^n)\) and memory \(O(2^n)\) for the recurrence phase.
If \(M\) is the largest support size among the intermediate score distributions, each hash-map convolution costs \(O(M^2)\) in the naive representation, so the convolution phase is \(O(kM^2)\). The negative-total count adds a sorting step \(O(M\log M)\). The crucial point is that the algorithm depends on the number of distinct reachable scores, not on the full tuple space \((2^n)^k\).
Problem 949 ordnet jedem Binärwort \(w\) der Länge \(n\) eine rekursive Links-gegen-Rechts-Position zu. Die Wörter der Länge 1 sind die Anfangszahlen \(0\mapsto +1\) und \(1\mapsto -1\). Für längere Wörter verwendet die Rekursion die echten Suffixe auf der einen Spielseite und die echten Präfixe auf der anderen. Die Implementierungen speichern nicht den vollständigen Spielbaum, sondern einen Vorzeichenwert \(u(w)\) zusammen mit einer Einteilung in cold und nicht-cold.
Gesucht ist \(G(20,7)\bmod 1001001011\). Vollständiges Durchzählen ist ausgeschlossen: Es gibt \(2^{20}\) Wörter der Länge 20 und damit \((2^{20})^7\) geordnete 7-Tupel. Die Lösung bewertet deshalb jedes einzelne Wort genau einmal, fasst gleiche Werte in Histogrammen zusammen und zählt Tupel anschließend über Faltungen dieser Histogramme.
Alle drei Implementierungen folgen demselben Zweistufenplan. Zuerst wird die Einwort-Rekursion für alle Binärwörter bis Länge \(n\) ausgewertet. Danach wird die Menge der entstehenden Werte in ein Problem über diskrete Verteilungen umgeformt.
Für ein Wort \(w\) der Länge \(\ell\ge 2\) sei \(\mathrm{Suf}(w)\) die Menge der echten Suffixe und \(\mathrm{Pre}(w)\) die Menge der echten Präfixe. Jede dieser Optionen ist kürzer als \(w\), daher funktioniert eine dynamische Programmierung nach wachsender Wortlänge.
Jedes kürzere Wort \(t\) trägt zwei gespeicherte Endpunkte \(u(t)\) und \(d(t)\). Die neuen Rohgrenzen lauten
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$
Die Ebene der Wörter mit Länge 1 wird initialisiert durch
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$
nach einer globalen Skalierung, die gleich erklärt wird. Genau diese Formeln sind der eigentliche Kern des Problems: Jeder spätere Wert wird vom besten Suffix-Beitrag und vom besten Präfix-Beitrag kürzerer Wörter erzwungen.
Die Lösungen repräsentieren jeden Wert auf einem dyadischen Gitter, dessen Nenner ein Teiler von \(2^n\) ist. Statt rationale Zahlen direkt zu speichern, wird alles mit \(2^n\) multipliziert und als ganze Zahl abgelegt. Eine dyadische Zahl \(p/2^m\) wird also als \(p\,2^{\,n-m}\) kodiert.
Dadurch bleiben alle Vergleiche exakt und die gesamte Rekursion rein ganzzahlig. Die Floor- und Ceiling-Operationen, die bei der Suche nach einem neuen Wert auftreten, werden damit zu einfachen Divisionen durch Zweierpotenzen. Weil die Rekursion höchstens Tiefe \(n\) hat, reicht diese Darstellung für alle vom Algorithmus erzeugten Werte aus.
Gilt für die Rohgrenzen
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$
dann kommt das Wort in den cold-Topf. In diesem Fall wählen die Implementierungen eine einzige kanonische dyadische Zahl \(x\), die strikt zwischen den beiden Grenzen liegt, und setzen
$$u(w)=d(w)=x.$$
Gewählt wird die einfachste dyadische Zahl im offenen Intervall \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\): Zuerst werden grobe Nenner ausprobiert, also liefert die erste erfolgreiche Skala den kleinsten Nenner; innerhalb dieser Skala wird \(0\) bevorzugt, falls möglich, sonst der zulässige Zähler mit dem kleinsten Betrag; und bei nicht-ganzzahligen Dyadischen bleibt der Zähler ungerade, damit die Darstellung bereits gekürzt ist.
Existiert keine echte Lücke, dann bleibt der Zustand nicht-cold und die Implementierungen speichern schlicht
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$
Diese Trennung ist später entscheidend: Nur cold-Zustände kollabieren zu genau einer Zahl, während die anderen Zustände für die Endzählung nur ihren linken Endwert \(u(w)\) behalten.
Nachdem alle Wörter der Länge \(n\) verarbeitet wurden, werden pro Wort nur noch zwei Informationen benötigt: der gespeicherte Wert \(u(w)\) und die Frage, ob das Wort cold war. Deshalb komprimieren die Implementierungen die gesamte letzte Ebene zu zwei Histogrammen,
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x,\ w\text{ cold}\}.$$
Hier verschwindet die Explosion in \(k\). Viele verschiedene Wörter besitzen denselben Wert, daher kann das Tupelproblem über Wert-Häufigkeiten statt über einzelne Wörter gelöst werden.
Für ungerades \(k\) setze
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$
Seien \(D_a\) und \(D_b\) die \(a\)- bzw. \(b\)-fache Faltung von \(H_{\mathrm{all}}\), und \(C_a\), \(C_b\) die entsprechenden Faltungspotenzen von \(H_{\mathrm{cold}}\). Dann zählt \(D_a(s)\) die geordneten \(a\)-Tupel von Wörtern der Länge \(n\), deren gespeicherte Werte Summe \(s\) haben, und analog für die anderen Verteilungen.
Die Antwort ist
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$
Der erste Term zählt alle geordneten \(k\)-Tupel mit negativer Gesamtsumme der gespeicherten Werte. Der zweite Term ergänzt die exakten Nullsummen, aber nur dann, wenn jede Komponente aus dem cold-Histogramm stammt. Die Aufspaltung in einen \(a\)-Teil und einen \(b\)-Teil ist lediglich ein Zähltrick; sie verändert die Gesamtsumme nicht, weil \(a+b=k\) gilt.
Für \(n=2\) ist die globale Skalierung \(2^2=4\). Die vier Binärwörter sind \(00,01,10,11\).
Bei \(00\) sind der einzige echte Suffix und das einzige echte Präfix jeweils \(0\), also ist der gespeicherte Wert \(+4\). Für \(11\) ergibt dieselbe Überlegung \(-4\). Bei \(01\) liefert das Suffix \(-4\) und das Präfix \(+4\); es gibt also eine echte Lücke und die einfachste dyadische Zahl dazwischen ist \(0\), daher ist dieses Wort cold. Bei \(10\) liegen die Rohgrenzen in umgekehrter Reihenfolge, also bleibt das Wort nicht-cold und behält den gespeicherten Wert \(+4\).
Nach Division durch die gemeinsame Skalierung lautet das Wertmultiset somit
$$\{1,0,1,-1\},$$
und nur das Wort mit Wert \(0\) ist cold. Nun zählen wir geordnete Tripel. Negative Gesamtsummen treten in genau vier Mustern auf:
$$(-1,-1,-1)=1,$$
$$(-1,-1,0)=3,$$
$$(-1,0,0)=3,$$
$$(-1,-1,+1)=3\cdot 2=6,$$
denn der Eintrag \(+1\) kann aus zwei verschiedenen Wörtern stammen. Insgesamt sind das \(1+3+3+6=13\) negative Tripel. Das einzige cold-Nulltripel ist \((01,01,01)\), also kommt noch 1 dazu und damit
$$G(2,3)=13+1=14,$$
genau wie im eingebauten Test der C++-Implementierung.
Die Implementierungen erzeugen alle nichtleeren Binärwörter der Längen \(1,2,\dots,n\) Ebene für Ebene. Für jedes Wort der letzten Ebene prüfen sie alle echten Suffixlängen und alle echten Präfixlängen, bilden daraus die beiden Rohgrenzen und kollabieren den Zustand entweder zu einer kanonischen dyadischen Zahl oder behalten die Rohendpunkte. Die C++-Version kann die Schleife über die Wörter einer festen Länge mit OpenMP parallelisieren; Python und Java führen dieselbe Rekursion seriell aus.
Sobald die Ebene der Länge \(n\) vollständig ist, wird die gesamte Präfix-/Suffix-Struktur nicht mehr benötigt. Die Implementierungen laufen einmal über die Endwerte, zählen die Häufigkeit jedes gespeicherten Werts und zählen separat, wie oft derselbe Wert unter den cold-Wörtern vorkommt. So entstehen das All-Words-Histogramm und das Cold-Only-Histogramm.
Weil \(k=7\) klein ist, werden die benötigten Faltungspotenzen nicht mit FFT-Technik, sondern durch wiederholte Hash-Map-Faltungen aufgebaut. Um negative Gesamtsummen zu zählen, wird eine der beiden resultierenden Trägermengen sortiert und mit Präfixsummen versehen; so kann jeder Wert der anderen Seite alle passenden Partner per Binärsuche in einem Schritt addieren. Die exakten cold-Nullsummen sind noch einfacher: Dafür wird ein Wert nur mit seinem Negativen in der anderen cold-Verteilung abgeglichen.
Das dynamische Programm verarbeitet jedes Binärwort der Länge höchstens \(n\), also insgesamt \((2^{n+1}-2)\) Zustände. Pro Zustand werden alle echten Suffixlängen und alle echten Präfixlängen durchlaufen, und im cold-Fall kann zusätzlich über bis zu \(n\) dyadische Skalen gesucht werden. Daraus ergibt sich für die Rekursionsphase eine Gesamtlaufzeit von \(O(n2^n)\) und ein Speicherbedarf von \(O(2^n)\).
Ist \(M\) die größte Trägergröße einer Zwischenverteilung, dann kostet jede Hash-Map-Faltung in der naiven Darstellung \(O(M^2)\), also insgesamt \(O(kM^2)\) für die Faltungsphase. Für die Zählung negativer Summen kommt noch ein Sortierschritt \(O(M\log M)\) hinzu. Entscheidend ist, dass der Algorithmus von der Anzahl erreichbarer Werte abhängt und nicht vom vollständigen Tupelraum \((2^n)^k\).
Problem 949, uzunluğu \(n\) olan her ikili kelime \(w\) için özyinelemeli bir sol-sağ oyunu tanımlar. Tek bitlik kelimeler başlangıç sayılarıdır: \(0\mapsto +1\) ve \(1\mapsto -1\). Daha uzun kelimelerde özyineleme, uygun sonekleri oyunun bir tarafının hamleleri, uygun önekleri ise diğer tarafın hamleleri olarak kullanır. Uygulamalar tam oyun ağacını tutmaz; bunun yerine bir işaretli skor \(u(w)\) ve cold / non-cold ayrımı hesaplar.
Hedef nicelik \(G(20,7)\bmod 1001001011\) değeridir. Doğrudan sayım imkansızdır: uzunluğu 20 olan \(2^{20}\) kelime ve dolayısıyla \((2^{20})^7\) sıralı 7-li vardır. Başarılı yöntem, her tek kelimeyi yalnızca bir kez değerlendirmek, eşit skorları histogramlarda toplamak ve ardından tuple sayılarını bu histogramların konvolüsyonlarıyla bulmaktır.
Üç uygulamanın da omurgası aynıdır. Önce uzunluğu \(n\)'ye kadar olan bütün ikili kelimeler için tek-kelime özyinelemesi çözülür. Sonra ortaya çıkan skor çokluğu, ayrık dağılımlar üzerinde bir sayım problemine dönüştürülür.
Uzunluğu \(\ell\ge 2\) olan bir \(w\) kelimesi için \(\mathrm{Suf}(w)\) uygun sonekler, \(\mathrm{Pre}(w)\) ise uygun önekler kümesi olsun. Bu seçeneklerin hepsi \(w\)'den daha kısa olduğundan, uzunluğa göre artan sırada dinamik programlama yapılabilir.
Her kısa \(t\) kelimesi iki uç değer taşır: \(u(t)\) ve \(d(t)\). Yeni ham sınırlar
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t)$$
şeklindedir. Uzunluğu 1 olan katman ise
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1$$
olarak başlatılır; bu, birazdan açıklanacak ortak ölçekleme sonrası yazımdır. Problemin gerçek çekirdeği bu formüllerdir: her yeni değer, kısa kelimelerden gelen en güçlü sonek katkısı ile en güçlü önek katkısı tarafından belirlenir.
Çözümler bütün değerleri paydası \(2^n\)'i bölen dyadik ızgarada temsil eder. Rasyonel sayı doğrudan saklanmaz; onun yerine her şey \(2^n\) ile çarpılıp tamsayı olarak tutulur. Böylece \(p/2^m\) biçimindeki bir dyadik sayı \(p\,2^{\,n-m}\) olarak kodlanır.
Bu seçim, karşılaştırmaları tamamen kesin kılar ve tüm özyinelemeyi tamsayı aritmetiğine indirger. Yeni bir değer aranırken gereken floor ve ceiling işlemleri basit iki kuvvetine bölmelere dönüşür. Özyineleme derinliği en fazla \(n\) olduğu için, algoritmanın ürettiği bütün değerler bu temsil içinde kayıpsızdır.
Eğer ham sınırlar
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w)$$
koşulunu sağlıyorsa, kelime cold kovasına girer. Bu durumda uygulamalar iki sınırın arasında kalan tek bir kanonik dyadik sayı \(x\) seçip
$$u(w)=d(w)=x$$
atar. Seçilen \(x\), açık aralık \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\) içindeki en basit dyadik sayıdır: önce kaba paydalar denenir, dolayısıyla ilk bulunan ölçek en küçük paydayı verir; o ölçekte mümkünse \(0\) seçilir, değilse mutlak değeri en küçük uygun pay tercih edilir; sayı tam sayı değilse pay tek tutulur ki gösterim zaten sade olsun.
Sıkı bir aralık yoksa durum non-cold kalır ve uygulamalar sadece
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w)$$
değerlerini saklar. Bu ayrım son aşamada kritiktir: yalnızca cold durumları tek bir sayıya çöker, diğerleri ise nihai sayımda sadece sol uç skoru \(u(w)\) ile temsil edilir.
Uzunluğu \(n\) olan bütün kelimeler işlendiğinde, her kelime için yalnızca iki bilgi gerekir: saklanan skor \(u(w)\) ve kelimenin cold olup olmadığı. Bu yüzden uygulamalar son katmanı şu iki histogramla özetler:
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x,\ w\text{ cold}\}.$$
\(k\) yönünden üstel patlamayı ortadan kaldıran adım budur. Çünkü birçok farklı kelime aynı skoru paylaşır; dolayısıyla tuple problemi tek tek kelimeler yerine skor frekansları üzerinde çözülebilir.
Tek \(k\) için
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a$$
tanımlarını yapalım. \(D_a\) ve \(D_b\), \(H_{\mathrm{all}}\) histogramının sırasıyla \(a\) ve \(b\) kez konvolüsyon kuvvetleri; \(C_a\) ve \(C_b\) ise \(H_{\mathrm{cold}}\) için aynı işlemlerdir. Böylece \(D_a(s)\), saklanan skorları toplamı \(s\) olan sıralı \(a\)-li kelime sayısını verir.
Cevap
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}$$
şeklindedir. İlk terim toplam saklanan skoru negatif olan bütün sıralı \(k\)-lileri sayar. İkinci terim ise tam sıfır toplamları ekler, fakat yalnızca her bileşen cold histogramından geliyorsa. Tuple'ı \(a\)-parça ve \(b\)-parça olarak ayırmak sadece hesaplama kolaylığıdır; \(a+b=k\) olduğundan toplam skoru değiştirmez.
\(n=2\) için ortak ölçek \(2^2=4\)'tür. Dört ikili kelime \(00,01,10,11\) olur.
\(00\) için tek uygun sonek ve tek uygun önek hep \(0\) olduğundan saklanan skor \(+4\)'tür. \(11\) için aynı mantık \(-4\) verir. \(01\) için sonek \(-4\), önek \(+4\) üretir; arada sıkı bir boşluk vardır ve bu boşluktaki en basit dyadik sayı \(0\) olduğundan bu kelime cold olur. \(10\) için ham sınırlar ters sıradadır; dolayısıyla kelime non-cold kalır ve saklanan skor \(+4\) olur.
Ortak ölçeğe bölersek skor çokluğu
$$\{1,0,1,-1\}$$
şeklindedir ve yalnızca \(0\) skorlu kelime cold'dur. Şimdi sıralı üçlüleri sayalım. Negatif toplam veren dört desen vardır:
$$(-1,-1,-1)=1,$$
$$(-1,-1,0)=3,$$
$$(-1,0,0)=3,$$
$$(-1,-1,+1)=3\cdot 2=6,$$
çünkü \(+1\) girişi iki farklı kelimeden seçilebilir. Toplamda \(1+3+3+6=13\) negatif üçlü elde edilir. Cold ve sıfır toplamlı tek üçlü \((01,01,01)\) olduğundan bir tane daha eklenir ve
$$G(2,3)=13+1=14$$
sonucu çıkar. Bu, C++ çözümündeki yerleşik doğrulama ile aynıdır.
Uygulamalar, uzunlukları \(1,2,\dots,n\) olan bütün boş olmayan ikili kelimeleri katman katman işler. Son katmandaki her kelime için bütün uygun sonek uzunlukları ve bütün uygun önek uzunlukları taranır, iki ham sınır elde edilir ve durum ya kanonik bir dyadik sayıya çöker ya da ham uç değerler korunur. C++ sürümü sabit bir uzunluktaki kelimeler üzerindeki döngüyü OpenMP ile paralelleştirebilir; Python ve Java aynı özyinelemeyi tek iş parçacığında yürütür.
Uzunluğu \(n\) olan katman tamamlandığında tam önek/sonek yapısı artık gerekmez. Uygulamalar son skorların üzerinden bir kez geçer, her skorun kaç kez göründüğünü sayar ve aynı işlemi cold kelimeler için ayrı bir sayaçta tekrarlar. Böylece tüm-kelimeler histogramı ile yalnızca-cold histogramı elde edilir.
\(k=7\) küçük olduğu için gerekli konvolüsyon kuvvetleri FFT benzeri tekniklerle değil, hash map tabanlı tekrar tekrar katlama ile kurulur. Negatif toplamları saymak için dağılımlardan birinin desteği sıralanır ve prefix toplamları alınır; sonra diğer dağılımdaki her skor, ikili arama ile bütün uygun partnerlerini tek adımda ekler. Cold sıfır-toplam durumları daha basittir: bir skoru diğer cold dağılımındaki eksi değeriyle eşleştirmek yeterlidir.
Dinamik program, uzunluğu en çok \(n\) olan her ikili kelimeyi işler; toplam durum sayısı \((2^{n+1}-2)\)'dir. Her durumda bütün uygun sonek uzunlukları ve bütün uygun önek uzunlukları taranır; cold ise en fazla \(n\) farklı dyadik ölçek denenebilir. Bu yüzden özyineleme fazının toplam zamanı \(O(n2^n)\), bellek maliyeti ise \(O(2^n)\)'dir.
Ara dağılımların en büyük destek boyutuna \(M\) dersek, saf hash-map gösteriminde her konvolüsyon \(O(M^2)\) maliyetlidir; dolayısıyla konvolüsyon aşaması \(O(kM^2)\) olur. Negatif toplam sayımı için ayrıca \(O(M\log M)\) sıralama gerekir. Kritik nokta şudur: algoritma \((2^n)^k\) tuple uzayına değil, erişilebilen farklı skor sayısına bağlıdır.
El problema 949 asigna a cada palabra binaria \(w\) de longitud \(n\) una posicion recursiva de izquierda contra derecha. Las palabras de un solo bit son los valores iniciales \(0\mapsto +1\) y \(1\mapsto -1\). Para palabras mas largas, la recurrencia usa los sufijos propios como opciones de un lado del juego y los prefijos propios como opciones del otro. Las implementaciones no guardan el arbol completo, sino una puntuacion con signo \(u(w)\) y una clasificacion cold / no-cold.
La cantidad buscada es \(G(20,7)\bmod 1001001011\). El recuento directo es imposible: hay \(2^{20}\) palabras de longitud 20 y, por tanto, \((2^{20})^7\) 7-tuplas ordenadas. La idea ganadora es evaluar cada palabra una sola vez, agrupar los valores iguales en histogramas y contar las tuplas mediante convoluciones de esos histogramas.
Las tres implementaciones siguen el mismo esquema en dos etapas. Primero resuelven la recurrencia de una sola palabra para todas las cadenas binarias hasta longitud \(n\). Despues convierten el multiconjunto de valores finales en un problema de distribuciones discretas.
Para una palabra \(w\) de longitud \(\ell\ge 2\), sea \(\mathrm{Suf}(w)\) el conjunto de sus sufijos propios y \(\mathrm{Pre}(w)\) el conjunto de sus prefijos propios. Todas esas opciones son mas cortas que \(w\), asi que una programacion dinamica por longitud creciente es natural.
Cada palabra mas corta \(t\) lleva dos extremos almacenados, \(u(t)\) y \(d(t)\). Las cotas brutas nuevas son
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$
La capa de longitud 1 se inicia con
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$
despues de la escala global que se describe enseguida. Estas formulas son el verdadero nucleo matematico del problema: cada valor nuevo queda determinado por la mejor contribucion procedente de los sufijos y por la mejor contribucion procedente de los prefijos.
Las soluciones representan todos los valores en una malla diadica cuyo denominador divide \(2^n\). En lugar de guardar un racional, multiplican todo por \(2^n\) y almacenan enteros. Asi, un numero diadico \(p/2^m\) se codifica como \(p\,2^{\,n-m}\).
Eso vuelve exactas todas las comparaciones y mantiene la recurrencia completamente en aritmetica entera. Las operaciones de piso y techo necesarias al buscar un nuevo valor pasan a ser simples divisiones por potencias de dos. Como la profundidad de la recurrencia es a lo sumo \(n\), esta representacion alcanza para todos los valores que produce el algoritmo.
Si las cotas brutas cumplen
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$
la palabra entra en la categoria cold. En ese caso las implementaciones eligen un unico numero diadico canonico \(x\) estrictamente entre ambas cotas y fijan
$$u(w)=d(w)=x.$$
El \(x\) elegido es el diadico mas simple del intervalo abierto \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\): primero se prueban denominadores gruesos, de modo que la primera escala valida da el menor denominador; dentro de esa escala se prefiere \(0\) si esta disponible y, si no, el numerador admisible con menor valor absoluto; para diadicos no enteros se mantiene numerador impar, de forma que la representacion ya queda reducida.
Si no hay hueco estricto, el estado permanece no-cold y las implementaciones almacenan simplemente
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$
La diferencia es esencial en la ultima fase: solo los estados cold colapsan a un unico numero, mientras que los demas conservan unicamente su puntuacion izquierda \(u(w)\) para el conteo final.
Una vez procesadas todas las palabras de longitud \(n\), solo hacen falta dos datos por palabra: su puntuacion almacenada \(u(w)\) y si era cold o no. Por eso las implementaciones comprimen la capa final en dos histogramas,
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x,\ w\text{ cold}\}.$$
Este es el paso que elimina la explosion exponencial en \(k\). Muchas palabras distintas comparten el mismo valor, asi que el problema de tuplas puede resolverse sobre frecuencias de puntuaciones en lugar de sobre palabras individuales.
Para \(k\) impar, definimos
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$
Sean \(D_a\) y \(D_b\) las convoluciones de orden \(a\) y \(b\) de \(H_{\mathrm{all}}\), y \(C_a\), \(C_b\) las potencias de convolucion correspondientes de \(H_{\mathrm{cold}}\). Entonces \(D_a(s)\) cuenta cuantas \(a\)-tuplas ordenadas de palabras de longitud \(n\) tienen suma \(s\) de puntuaciones almacenadas.
La respuesta es
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$
El primer termino cuenta todas las \(k\)-tuplas ordenadas cuya suma total de puntuaciones es negativa. El segundo agrega los casos de suma exactamente cero, pero solo cuando cada componente proviene del histograma cold. Partir la tupla en una parte de tamano \(a\) y otra de tamano \(b\) es solo un truco de conteo; no altera la suma total porque \(a+b=k\).
Para \(n=2\), la escala global es \(2^2=4\). Las cuatro palabras binarias son \(00,01,10,11\).
En \(00\), el unico sufijo propio y el unico prefijo propio son ambos \(0\), asi que la puntuacion almacenada es \(+4\). En \(11\), el mismo razonamiento da \(-4\). En \(01\), el sufijo aporta \(-4\) y el prefijo aporta \(+4\), de modo que hay un hueco estricto y el diadico mas simple entre ambos es \(0\); esa palabra es cold. En \(10\), las cotas quedan invertidas, asi que la palabra es no-cold y conserva puntuacion \(+4\).
Dividiendo por la escala comun, el multiconjunto de puntuaciones es
$$\{1,0,1,-1\},$$
y la unica palabra cold tiene puntuacion \(0\). Ahora contamos ternas ordenadas. Las sumas negativas aparecen en cuatro patrones:
$$(-1,-1,-1)=1,$$
$$(-1,-1,0)=3,$$
$$(-1,0,0)=3,$$
$$(-1,-1,+1)=3\cdot 2=6,$$
porque la entrada \(+1\) puede elegirse entre dos palabras distintas. En total hay \(1+3+3+6=13\) ternas negativas. La unica terna cold con suma cero es \((01,01,01)\), que aporta un caso mas, y por tanto
$$G(2,3)=13+1=14,$$
exactamente el valor de comprobacion incluido en la version C++.
Las implementaciones recorren todas las palabras binarias no vacias de longitudes \(1,2,\dots,n\) capa por capa. Para cada palabra de la capa final inspeccionan todas las longitudes posibles de sufijo propio y prefijo propio, construyen las dos cotas brutas y luego colapsan el estado a un numero diadico canonico o conservan los extremos brutos. La version en C++ puede paralelizar el bucle sobre palabras de una misma longitud con OpenMP; Python y Java realizan exactamente la misma recurrencia en serie.
Una vez completada la longitud \(n\), la estructura detallada de prefijos y sufijos ya no hace falta. Las implementaciones recorren una vez la capa final, cuentan cuantas veces aparece cada puntuacion y repiten el conteo solo para las palabras cold. Asi obtienen el histograma total y el histograma restringido a cold.
Como \(k=7\) es pequeno, las potencias de convolucion necesarias se construyen mediante convoluciones repetidas sobre tablas hash y no mediante tecnicas tipo FFT. Para contar las sumas negativas, se ordena el soporte de una de las distribuciones y se le agregan sumas prefijas; luego cada puntuacion del otro lado recupera con una sola busqueda binaria todos los companeros compatibles. Los casos cold de suma cero son mas simples: basta emparejar una puntuacion con su opuesta en la otra distribucion cold.
La programacion dinamica procesa toda palabra binaria de longitud a lo sumo \(n\), es decir, \((2^{n+1}-2)\) estados en total. En cada estado se recorren todas las longitudes de sufijo propio y todas las longitudes de prefijo propio, y en el caso cold puede explorarse hasta \(n\) escalas diadicas. Por tanto, la fase recursiva cuesta \(O(n2^n)\) tiempo y \(O(2^n)\) memoria.
Si \(M\) es el mayor tamano de soporte entre las distribuciones intermedias, cada convolucion sobre tablas hash cuesta \(O(M^2)\) en la representacion ingenua, de modo que la fase de convolucion es \(O(kM^2)\). El recuento de sumas negativas anade un paso de ordenacion \(O(M\log M)\). Lo importante es que el algoritmo depende del numero de puntuaciones alcanzables, no del espacio completo de tuplas \((2^n)^k\).
第 949 题把每个长度为 \(n\) 的二进制串 \(w\) 解释成一个递归定义的左右对抗位置。长度为 1 的两个串是起始数值：\(0\mapsto +1\)，\(1\mapsto -1\)。对于更长的串，递推把真后缀作为一侧可走的选项，把真前缀作为另一侧可走的选项。实现并不保存完整博弈树，而是只计算一个带符号的分数 \(u(w)\)，再记录该状态是否属于 cold 类。
题目要求的是 \(G(20,7)\bmod 1001001011\)。如果直接枚举，长度为 20 的二进制串有 \(2^{20}\) 个，而有序 7 元组多达 \((2^{20})^7\) 个，完全不可行。真正可行的方法是：先把每个单独的串求值一次，再把相同分数压缩成频数直方图，最后用这些直方图的卷积来统计元组数量。
三份实现的骨架完全一致。第一步是对所有长度不超过 \(n\) 的二进制串做单串递推。第二步是把最终得到的分数多重集转化为离散分布上的计数问题。
设 \(w\) 的长度为 \(\ell\ge 2\)。记 \(\mathrm{Suf}(w)\) 为 \(w\) 的所有真后缀，\(\mathrm{Pre}(w)\) 为 \(w\) 的所有真前缀。它们都比 \(w\) 更短，因此按长度递增进行动态规划是自然且正确的。
每个较短字符串 \(t\) 都带有两个已存储的端点 \(u(t)\) 与 \(d(t)\)。对当前字符串 \(w\)，新的原始边界定义为
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$
长度为 1 的初始层写成
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$
这里已经默认经过后文要说明的统一缩放。这几个式子就是本题最核心的数学对象：每个更长串的状态，都由其较短真后缀给出的最好下界和较短真前缀给出的最好上界共同决定。
实现把所有数值都放在分母整除 \(2^n\) 的 dyadic 网格上表示。它不直接保存有理数，而是统一乘上 \(2^n\) 后保存为整数。于是一个 dyadic 有理数 \(p/2^m\) 会被编码成 \(p\,2^{\,n-m}\)。
这样做的好处是所有比较都完全精确，而且整个递推过程都能用整数算术完成。寻找新数值时出现的 floor 与 ceiling 操作，也都退化成对 2 的幂进行整除。由于递推深度最多只有 \(n\)，因此这个 dyadic 表示足以覆盖算法中可能出现的全部数值。
如果原始边界满足
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$
那么这个字符串就进入 cold 桶。在这种情况下，实现会在这两个边界之间选出一个唯一的规范 dyadic 数 \(x\)，并令
$$u(w)=d(w)=x.$$
这里选择的是开区间 \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\) 中“最简单”的 dyadic 数：先尝试较粗的分母，因此第一次成功的尺度就给出最小分母；在该尺度上如果 \(0\) 可用就优先取 \(0\)，否则取绝对值最小的合法分子；若结果不是整数，则保持分子为奇数，使这个 dyadic 表示已经是最简形式。
如果不存在严格间隔，那么状态就保留为 non-cold，并直接存储
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$
这个区分在最后一步非常关键：只有 cold 状态会塌缩成一个精确数值，而其余状态在最终计数中只保留左端分数 \(u(w)\)。
当所有长度为 \(n\) 的字符串都处理完以后，每个字符串只剩下两项关键信息：存储分数 \(u(w)\) 以及它是否为 cold。因此实现把整层压缩成两个直方图：
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x,\ w\text{ cold}\}.$$
这一步正是消除关于 \(k\) 的指数爆炸的关键。因为大量不同的字符串会落到同一个分数上，所以元组问题可以转化为“分数频率”的问题，而不必逐个处理具体字符串。
当 \(k\) 为奇数时，设
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$
记 \(D_a\) 与 \(D_b\) 为 \(H_{\mathrm{all}}\) 的 \(a\) 次和 \(b\) 次卷积幂，\(C_a\) 与 \(C_b\) 为 \(H_{\mathrm{cold}}\) 的对应卷积幂。于是 \(D_a(s)\) 表示长度为 \(n\) 的有序 \(a\) 元组中，存储分数之和等于 \(s\) 的个数，其余分布含义相同。
最终答案是
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$
第一项统计总分数为负的所有有序 \(k\) 元组。第二项补上总分数恰好为零的情形，但只在每个分量都来自 cold 直方图时才计入。把一个 \(k\) 元组拆成前 \(a\) 个与后 \(b\) 个只是计算技巧，并不会改变总和，因为始终有 \(a+b=k\)。
当 \(n=2\) 时，统一缩放因子是 \(2^2=4\)。四个二进制串分别是 \(00,01,10,11\)。
对 \(00\) 而言，唯一的真后缀和唯一的真前缀都是 \(0\)，所以存储分数为 \(+4\)。对 \(11\) 同理得到 \(-4\)。对 \(01\)，后缀贡献 \(-4\)，前缀贡献 \(+4\)，两者之间存在严格间隔，因此其中最简单的 dyadic 数是 \(0\)，这个串属于 cold。对 \(10\)，原始边界次序相反，所以它是 non-cold，并保留存储分数 \(+4\)。
除以公共缩放因子以后，分数多重集就是
$$\{1,0,1,-1\},$$
而且只有分数为 \(0\) 的那个串属于 cold。现在来数有序三元组。总和为负的情况恰好有四类：
$$(-1,-1,-1)=1,$$
$$(-1,-1,0)=3,$$
$$(-1,0,0)=3,$$
$$(-1,-1,+1)=3\cdot 2=6,$$
因为其中的 \(+1\) 可以来自两个不同的字符串。合计得到 \(1+3+3+6=13\) 个负和三元组。唯一的 cold 且总和为零的三元组是 \((01,01,01)\)，再加 1，于是
$$G(2,3)=13+1=14,$$
这与 C++ 实现中的内置校验完全一致。
三份实现都会按层枚举长度 \(1,2,\dots,n\) 的所有非空二进制串。对每个目标层字符串，它们遍历所有可能的真后缀长度与真前缀长度，构造两条原始边界，然后要么把状态压缩成一个规范 dyadic 数，要么保留原始端点。C++ 版本在固定长度这一层上可以用 OpenMP 并行处理不同字符串；Python 与 Java 则按同样的递推串行执行。
当长度 \(n\) 的层求完后，详细的前缀/后缀结构已经不再需要。实现只需再扫描最终层一次，统计每个分数出现的次数，并额外统计这些分数在 cold 字符串中出现的次数。这样就得到了后续卷积阶段所需的两个频数表。
由于这里的 \(k=7\) 很小，实现没有引入 FFT 一类的重型工具，而是直接用哈希表做重复卷积。为了统计负和，先把其中一个分布的支撑排序并做前缀和，然后另一个分布中的每个分数只需一次二分查找，就能把所有满足阈值的配对全部加进去。至于 cold 的零和情况，更直接：只要在另一侧 cold 分布中查找相反数即可。
动态规划会处理长度不超过 \(n\) 的每个二进制串，总状态数是 \((2^{n+1}-2)\)。每个状态都要扫描全部真后缀长度与全部真前缀长度，若该状态为 cold，还可能再尝试多达 \(n\) 个 dyadic 尺度。因此递推阶段的总时间复杂度为 \(O(n2^n)\)，空间复杂度为 \(O(2^n)\)。
若中间分布的最大支撑大小记为 \(M\)，那么朴素哈希卷积每次需要 \(O(M^2)\)，卷积阶段总计为 \(O(kM^2)\)。统计负和还需要一次 \(O(M\log M)\) 的排序。最关键的结论是：算法的代价取决于“可达到的不同分数个数”，而不是完整的元组空间 \((2^n)^k\)。
В задаче 949 каждому двоичному слову \(w\) длины \(n\) сопоставляется рекурсивная позиция игры левого против правого. Слова длины 1 служат начальными числами: \(0\mapsto +1\) и \(1\mapsto -1\). Для более длинных слов рекурсия использует собственные суффиксы как ходы одной стороны, а собственные префиксы как ходы другой. Реализации не хранят все дерево игры, а вычисляют только знаковую величину \(u(w)\) и признак cold / non-cold.
Нужно найти \(G(20,7)\bmod 1001001011\). Полный перебор невозможен: имеется \(2^{20}\) слов длины 20, а значит \((2^{20})^7\) упорядоченных 7-кортежей. Рабочий подход состоит в том, чтобы один раз оценить каждое отдельное слово, затем сжать одинаковые оценки в гистограммы и уже по этим гистограммам считать кортежи через свертки.
Во всех трех реализациях используется одна и та же двухступенчатая схема. Сначала решается рекурсия для одного слова на всех двоичных строках длины не больше \(n\). Затем мультимножество финальных значений превращается в задачу о дискретных распределениях.
Пусть слово \(w\) имеет длину \(\ell\ge 2\). Обозначим через \(\mathrm{Suf}(w)\) множество его собственных суффиксов, а через \(\mathrm{Pre}(w)\) множество его собственных префиксов. Все такие варианты короче \(w\), поэтому динамика по возрастанию длины работает напрямую.
Каждому более короткому слову \(t\) соответствуют два сохраненных конца \(u(t)\) и \(d(t)\). Новые сырые границы задаются формулами
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$
Начальный слой длины 1 задается как
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$
после общей масштабной нормировки, которая будет объяснена ниже. Именно эти соотношения и составляют математическое ядро задачи: каждое новое значение определяется лучшим вкладом от суффиксной стороны и лучшим вкладом от префиксной стороны среди более коротких слов.
Решения представляют все значения на диадической сетке, знаменатель которой делит \(2^n\). Вместо хранения рациональных чисел напрямую все умножается на \(2^n\) и сохраняется как целое. Поэтому диадическое число \(p/2^m\) кодируется как \(p\,2^{\,n-m}\).
Такой выбор делает все сравнения точными и оставляет рекурсию целочисленной. Операции floor и ceiling, возникающие при поиске нового значения, превращаются в простые деления на степени двойки. Поскольку глубина рекурсии не превосходит \(n\), этого представления хватает для всех чисел, которые вообще может породить алгоритм.
Если сырые границы удовлетворяют условию
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$
то слово попадает в cold-класс. Тогда реализации выбирают единственное каноническое диадическое число \(x\), лежащее строго между границами, и присваивают
$$u(w)=d(w)=x.$$
Число \(x\) выбирается как самый простой диадический элемент открытого интервала \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\): сначала проверяются грубые знаменатели, поэтому первый успешный масштаб дает минимальный знаменатель; внутри этого масштаба предпочитается \(0\), если он допустим, иначе допустимый числитель с минимальным модулем; а для нецелых диадических чисел числитель сохраняется нечетным, чтобы запись уже была несократимой.
Если строгого промежутка нет, состояние остается non-cold, и реализации просто сохраняют
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$
Это различие критично на финальном этапе: только cold-состояния сводятся к одному точному числу, тогда как остальные дают для окончательного подсчета лишь левый конец \(u(w)\).
После обработки всех слов длины \(n\) для каждого слова важны только две вещи: сохраненное значение \(u(w)\) и то, было ли слово cold. Поэтому реализации сжимают весь слой в две гистограммы,
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x,\ w\text{ cold}\}.$$
Именно здесь исчезает экспоненциальный рост по \(k\). Много разных слов дают один и тот же результат, поэтому задача о кортежах решается по частотам значений, а не по самим словам.
Для нечетного \(k\) положим
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$
Пусть \(D_a\) и \(D_b\) обозначают \(a\)- и \(b\)-кратные свертки \(H_{\mathrm{all}}\), а \(C_a\), \(C_b\) - соответствующие степени свертки для \(H_{\mathrm{cold}}\). Тогда \(D_a(s)\) равно числу упорядоченных \(a\)-кортежей слов длины \(n\), у которых сумма сохраненных оценок равна \(s\).
Искомое значение выражается формулой
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$
Первый член считает все упорядоченные \(k\)-кортежи, у которых суммарная сохраненная оценка отрицательна. Второй добавляет случаи точного нуля, но только если каждый компонент взят из cold-гистограммы. Разбиение кортежа на часть размера \(a\) и часть размера \(b\) - это лишь прием подсчета; общую сумму оно не меняет, поскольку \(a+b=k\).
При \(n=2\) общий масштаб равен \(2^2=4\). Четыре двоичных слова: \(00,01,10,11\).
Для \(00\) единственный собственный суффикс и единственный собственный префикс равны \(0\), поэтому сохраненная оценка равна \(+4\). Для \(11\) тем же рассуждением получаем \(-4\). Для \(01\) суффикс дает \(-4\), а префикс дает \(+4\), между ними есть строгий промежуток, и самым простым диадическим числом внутри него является \(0\); это слово cold. Для \(10\) сырые границы идут в обратном порядке, поэтому слово остается non-cold и сохраняет оценку \(+4\).
После деления на общий масштаб мультимножество оценок имеет вид
$$\{1,0,1,-1\},$$
и только слово со значением \(0\) является cold. Теперь считаем упорядоченные тройки. Отрицательная сумма возникает ровно в четырех схемах:
$$(-1,-1,-1)=1,$$
$$(-1,-1,0)=3,$$
$$(-1,0,0)=3,$$
$$(-1,-1,+1)=3\cdot 2=6,$$
потому что значение \(+1\) можно взять из двух разных слов. Итого получается \(1+3+3+6=13\) отрицательных троек. Единственная cold-тройка с нулевой суммой - это \((01,01,01)\), она дает еще один случай, значит
$$G(2,3)=13+1=14,$$
что в точности совпадает с встроенной проверкой в C++ версии.
Реализации перебирают все непустые двоичные слова длины \(1,2,\dots,n\) послойно. Для каждого слова целевого слоя они просматривают все возможные длины собственных суффиксов и собственных префиксов, строят две сырые границы, а затем либо схлопывают состояние в одно каноническое диадическое число, либо сохраняют сырые концы. В C++ цикл по словам фиксированной длины может распараллеливаться через OpenMP; версии на Python и Java выполняют ту же рекурсию последовательно.
Когда слой длины \(n\) готов, подробная структура префиксов и суффиксов больше не нужна. Реализации один раз проходят по финальному слою, считают число появлений каждого значения и отдельно считают те же появления среди cold-слов. Так формируются полная гистограмма и гистограмма только для cold.
Поскольку здесь \(k=7\) мало, нужные степени свертки строятся не через FFT, а обычными повторными свертками над хеш-таблицами. Чтобы посчитать отрицательные суммы, опору одного распределения сортируют и снабжают префиксными суммами; после этого каждое значение из другого распределения добавляет все допустимые пары одной бинарной поисковой операцией. Случаи cold и нулевой суммы еще проще: достаточно искать противоположное значение во второй cold-гистограмме.
Динамика обрабатывает каждое двоичное слово длины не больше \(n\), то есть всего \((2^{n+1}-2)\) состояний. В каждом состоянии просматриваются все длины собственных суффиксов и все длины собственных префиксов, а для cold-состояний дополнительно может потребоваться перебор до \(n\) диадических масштабов. Поэтому рекурсивная фаза работает за \(O(n2^n)\) времени и требует \(O(2^n)\) памяти.
Если \(M\) обозначает максимальный размер носителя среди промежуточных распределений, то каждая наивная свертка на хеш-таблицах стоит \(O(M^2)\), а вся фаза сверток - \(O(kM^2)\). Подсчет отрицательных сумм добавляет еще сортировку \(O(M\log M)\). Главное преимущество состоит в том, что стоимость определяется числом достижимых различных оценок, а не всем пространством кортежей \((2^n)^k\).
تعطي المسألة 949 لكل كلمة ثنائية \(w\) طولها \(n\) وضعيةً عوديةً من نوع يسار مقابل يمين. الكلمات ذات البت الواحد هي القيم الابتدائية \(0\mapsto +1\) و\(1\mapsto -1\). أما الكلمات الأطول فتُبنى من علاقة عودية تستعمل اللواحق الصحيحة كخيارات لأحد الطرفين، والبوادئ الصحيحة كخيارات للطرف الآخر. التطبيقات لا تحتفظ بشجرة اللعبة كاملة، بل تحسب فقط درجة موقعة \(u(w)\) مع تصنيف يحدد هل الحالة من النوع cold أم لا.
المطلوب هو \(G(20,7)\bmod 1001001011\). التعداد المباشر غير ممكن: فعدد الكلمات بطول 20 هو \(2^{20}\)، وبالتالي عدد الترتيبات المرتبة ذات الطول 7 يساوي \((2^{20})^7\). الفكرة الفعالة هي تقييم كل كلمة مرة واحدة، ثم ضغط القيم المتساوية في توزيعات تكرارية، وبعد ذلك عد الترتيبات باستعمال التفاف هذه التوزيعات.
الهيكل الرياضي واحد في حلول ++C وPython وJava. أولًا تُحل العلاقة العودية لكل كلمة منفردة حتى الطول \(n\). ثم تتحول مجموعة القيم النهائية إلى مسألة على توزيعات متقطعة.
لتكن \(w\) كلمة طولها \(\ell\ge 2\). نرمز بـ \(\mathrm{Suf}(w)\) إلى مجموعة اللواحق الصحيحة، وبـ \(\mathrm{Pre}(w)\) إلى مجموعة البوادئ الصحيحة. كل هذه الخيارات أقصر من \(w\)، لذلك فإن البرمجة الديناميكية حسب زيادة الطول مناسبة مباشرة.
كل كلمة أقصر \(t\) تحمل حدين مخزنين هما \(u(t)\) و\(d(t)\). وعند الانتقال إلى \(w\) نحصل على الحدين الخامين
$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$
أما طبقة الطول 1 فتبدأ بالقيم
$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$
بعد تطبيق مقياس عام سنشرحه بعد قليل. هذه الصيغ هي جوهر المسألة الفعلي: فكل قيمة جديدة تتحدد من أفضل مساهمة قادمة من جهة اللواحق وأفضل مساهمة قادمة من جهة البوادئ بين الكلمات الأقصر.
الحلول تمثل جميع القيم على شبكة dyadic يكون مقامها قاسمًا لـ \(2^n\). بدل تخزين عدد نسبي مباشرة، تُضرب كل القيم في \(2^n\) وتُخزن كأعداد صحيحة. لذلك فإن العدد dyadic من الشكل \(p/2^m\) يُمثَّل بالعدد \(p\,2^{\,n-m}\).
هذا يجعل جميع المقارنات دقيقة تمامًا، ويحصر العودية كلها في حسابات صحيحة. كما أن عمليتي floor وceiling اللازمتين أثناء البحث عن قيمة جديدة تصبحان مجرد قسمة على قوى العدد 2. وبما أن عمق العودية لا يتجاوز \(n\)، فإن هذا التمثيل يكفي لكل القيم التي قد يظهرها الخوارزم.
إذا حقق الحدّان الخامان
$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$
فإن الكلمة تدخل فئة cold. عندها تختار التطبيقات عددًا dyadic قانونيًا وحيدًا \(x\) يقع بدقة بين الحدين، ثم تضع
$$u(w)=d(w)=x.$$
وهذه القيمة \(x\) هي أبسط عدد dyadic داخل المجال المفتوح \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\): تبدأ الخوارزمية بتجربة المقامات الخشنة أولًا، وبالتالي فإن أول مقياس ناجح يعطي أصغر مقام؛ وداخل ذلك المقياس تُفضَّل القيمة \(0\) إن كانت متاحة، وإلا يُختار البسط المسموح الأقرب إلى الصفر؛ وإذا لم تكن القيمة عددًا صحيحًا فيُحافظ على كون البسط فرديًا حتى تبقى الكتابة في أبسط صورة.
أما إذا لم توجد فجوة صارمة، فتبقى الحالة non-cold وتحتفظ التطبيقات فقط بـ
$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$
هذا التفريق مهم جدًا لاحقًا: فالحالات cold فقط تنهار إلى قيمة عددية واحدة، بينما الحالات الأخرى تستعمل في العد النهائي عبر الطرف الأيسر المخزن \(u(w)\) فقط.
بعد إنهاء جميع الكلمات بطول \(n\)، لا يبقى مهمًا لكل كلمة إلا معلومتان: الدرجة المخزنة \(u(w)\) وهل كانت الكلمة cold أم لا. لذلك تضغط التطبيقات الطبقة النهائية في توزيعين:
$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$
$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x,\ w\text{ cold}\}.$$
هذه هي الخطوة التي تزيل الانفجار الأسي بالنسبة إلى \(k\). فكثير من الكلمات المختلفة تشترك في الدرجة نفسها، ولذلك يمكن حل مسألة الترتيبات على تكرارات الدرجات بدلًا من الكلمات الفردية نفسها.
عندما يكون \(k\) فرديًا نضع
$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$
ولتكن \(D_a\) و\(D_b\) قوى الالتفاف من الرتبتين \(a\) و\(b\) للتوزيع \(H_{\mathrm{all}}\)، ولتكن \(C_a\) و\(C_b\) النظيرتين للتوزيع \(H_{\mathrm{cold}}\). عندئذٍ تمثل \(D_a(s)\) عدد الترتيبات المرتبة ذات الطول \(a\) من كلمات طولها \(n\) التي يكون مجموع درجاتها المخزنة مساويًا لـ \(s\).
وعندها تصبح الإجابة
$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$
الحد الأول يعد جميع الترتيبات المرتبة التي يكون مجموع درجاتها الكلي سالبًا. أما الحد الثاني فيضيف حالات المجموع الصفري تمامًا، لكن فقط عندما تأتي كل مركبة من التوزيع cold. تقسيم الترتيب إلى جزء طوله \(a\) وجزء طوله \(b\) ليس إلا حيلة حسابية؛ فهو لا يغير المجموع لأن \(a+b=k\).
عندما \(n=2\) يكون المقياس العام \(2^2=4\). والكلمات الثنائية الأربع هي \(00,01,10,11\).
في الحالة \(00\)، اللحق الصحيح الوحيد والبادئة الصحيحة الوحيدة كلاهما يساوي \(0\)، لذلك تكون الدرجة المخزنة \(+4\). وفي الحالة \(11\) يعطي المنطق نفسه القيمة \(-4\). أما \(01\) فيعطي اللحق \(-4\) وتعطي البادئة \(+4\)، فتوجد فجوة صارمة، وأبسط عدد dyadic داخلها هو \(0\)، لذا تكون هذه الكلمة cold. وفي \(10\) ينعكس ترتيب الحدين الخامين، ولذلك تبقى الكلمة non-cold وتحمل الدرجة \(+4\).
بعد القسمة على المقياس المشترك نحصل على مجموعة الدرجات
$$\{1,0,1,-1\},$$
والكلمة الوحيدة من النوع cold هي صاحبة الدرجة \(0\). الآن نعد الثلاثيات المرتبة. تظهر المجاميع السالبة في أربعة أنماط فقط:
$$(-1,-1,-1)=1,$$
$$(-1,-1,0)=3,$$
$$(-1,0,0)=3,$$
$$(-1,-1,+1)=3\cdot 2=6,$$
لأن العنصر \(+1\) يمكن اختياره من كلمتين مختلفتين. إذن مجموع الثلاثيات السالبة هو \(1+3+3+6=13\). والثلاثية الوحيدة cold ذات المجموع الصفري هي \((01,01,01)\)، فتضيف حالة واحدة، وبالتالي
$$G(2,3)=13+1=14,$$
وهو بالضبط مقدار التحقق الصغير الموجود في تنفيذ ++C.
التطبيقات تمر على جميع الكلمات الثنائية غير الفارغة ذات الأطوال \(1,2,\dots,n\) طبقةً بعد طبقة. ولكل كلمة في الطبقة الهدف تُفحَص كل أطوال اللواحق الصحيحة وكل أطوال البوادئ الصحيحة، ثم تُبنى الحدود الخام وتُختزل الحالة إما إلى عدد dyadic قانوني واحد أو تُترك مع حدّيها الخامين. يمكن لنسخة ++C أن توازي الحلقة الخاصة بكلمات طول ثابت عبر OpenMP، بينما تنفذ نسختا Python وJava العلاقة نفسها بصورة تسلسلية.
بعد اكتمال طبقة الطول \(n\)، لا تعود بنية البوادئ واللواحق التفصيلية مطلوبة. تمر التطبيقات مرة واحدة على القيم النهائية، فتعد عدد مرات ظهور كل درجة، ثم تكرر العد نفسه للكلمات cold فقط. بهذه الطريقة يتكون التوزيع الكامل وتوزيع cold فقط.
بما أن \(k=7\) صغير، فلا حاجة إلى أدوات ثقيلة مثل FFT. بدلًا من ذلك تُبنى قوى الالتفاف المطلوبة عبر التفاف متكرر على جداول تجزئة. ولعد المجاميع السالبة يُرتب دعم أحد التوزيعين وتُحسب مجاميعه السابقة، ثم تستعمل كل درجة في التوزيع الآخر بحثًا ثنائيًا واحدًا لإضافة كل الشركاء المقبولين دفعة واحدة. أما حالات الصفر داخل فئة cold فهي أبسط: يكفي البحث عن الدرجة المعاكسة في التوزيع cold المقابل.
تعالج البرمجة الديناميكية كل كلمة ثنائية طولها لا يتجاوز \(n\)، أي ما مجموعه \((2^{n+1}-2)\) حالة. وفي كل حالة تُفحص جميع أطوال اللواحق الصحيحة وجميع أطوال البوادئ الصحيحة، وقد تُجرَّب حتى \(n\) درجات dyadic إذا كانت الحالة cold. لذلك فإن زمن المرحلة العودية يساوي \(O(n2^n)\) والذاكرة المطلوبة \(O(2^n)\).
إذا رمزنا إلى أكبر حجم دعم بين التوزيعات الوسيطة بالرمز \(M\)، فإن كل التفاف في التمثيل الساذج المعتمد على جداول التجزئة يكلف \(O(M^2)\)، وبذلك تصبح مرحلة الالتفاف \(O(kM^2)\). كما أن عد المجاميع السالبة يضيف خطوة ترتيب \(O(M\log M)\). النقطة الحاسمة هي أن الخوارزمية تعتمد على عدد الدرجات المختلفة الممكنة، لا على فضاء الترتيبات الكامل \((2^n)^k\).