For an \(n\times n\) binary matrix \(A\), let \(r(A)\) be the number of distinct rows and \(c(A)\) the number of distinct columns. The matrix complexity is
$$\kappa(A)=\max(r(A),c(A)).$$
For each integer \(k\in\{0,1,\dots,n^2\}\), define
$$m_n(k)=\min\{\kappa(A): A \text{ is an } n\times n \text{ binary matrix with exactly } k \text{ ones}\}.$$
The required quantity is
$$C(n)=\sum_{k=0}^{n^2} m_n(k).$$
The implementation does not search over matrices directly. Instead, it marks which values of \(k\) are achievable with complexity \(1\), \(2\), or \(3\), and then every unmarked value contributes \(4\).
The key idea is to treat the problem as a reachability problem on the interval \(0,1,\dots,n^2\). Each construction marks certain counts of ones, and the final sum only depends on how many counts fall into each complexity class.
Complexity \(1\) means every row is identical and every column is identical. For a binary square matrix that happens only for the all-zero matrix and the all-one matrix, so
$$m_n(0)=m_n(n^2)=1.$$
These two endpoints are the only values with complexity \(1\), and they account for the constant term in the final counting identity.
For the two-type constructions used by the implementations, the \(n\) indices are split into two groups of sizes \(a\) and \(b\) with
$$a+b=n.$$
The admissible block patterns reduce to three independent weights:
$$a^2,\qquad b^2,\qquad 2ab.$$
Hence, for each split \(a+b=n\), the implementation enumerates the seven nonempty subset sums
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2,$$
and then discards the endpoints \(0\) and \(n^2\), which were already handled in the complexity-1 case. The union over all \(a\) gives the full set of counts with complexity \(2\).
Before the full three-type analysis, the implementations mark the explicit product family
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
The second value follows from complementation: replacing every \(0\) by \(1\) preserves the numbers of distinct rows and columns, so achievable counts come in complementary pairs \(k\leftrightarrow n^2-k\). This inexpensive family already covers many values with complexity at most \(3\).
The main construction splits \(n\) into three parts
$$a+b+c=n,\qquad a\le b\le c.$$
A three-type pattern is encoded by a binary \(3\times3\) template. The implementations enumerate all \(2^9=512\) templates, keep only those whose three rows are pairwise distinct, whose three columns are pairwise distinct, and whose row-pattern multiset matches the column-pattern multiset. After deduplication, this leaves exactly \(46\) distinct coefficient tuples.
For every surviving template, the number of ones has the quadratic form
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
where each diagonal coefficient satisfies \(d_i\in\{0,1\}\) and each mixed coefficient satisfies \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\). The diagonal terms count within-type blocks, while the mixed terms count cross-type blocks. Evaluating all \(46\) forms over all ordered partitions \(a\le b\le c\) marks every value reached by this three-type construction.
Let
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$$
Since exactly two values have complexity \(1\), we obtain
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$$
Simplifying gives the identity used by the implementations:
$$C(n)=3T-4-N_2+N_4.$$
So the task is reduced to marking the complexity-2 set and the complexity-\(\le 3\) set, then counting how many integers lie in each.
For \(n=5\), we have \(T=5^2+1=26\). The complexity-2 construction marks exactly
$$\{1,4,8,9,12,13,16,17,21,24\},$$
so \(N_2=10\). The combined complexity-\(\le 3\) construction covers all values \(0,1,\dots,25\), hence \(N_4=0\).
Therefore
$$C(5)=3\cdot 26-4-10+0=64.$$
The same result can be read directly from the complexity classes:
$$1+1+10\cdot 2+14\cdot 3=64.$$
So only \(0\) and \(25\) have complexity \(1\), ten values have complexity \(2\), and the remaining fourteen values have complexity \(3\).
The C++, Python, and Java implementations use the same pipeline. First they generate the finite catalogue of \(46\) three-type coefficient tuples from the \(512\) binary \(3\times3\) templates. Next they allocate two reachability containers over the interval \(0\) through \(n^2\): one container for values with complexity at most \(3\), and one container for values with complexity \(2\). The C++ and Java implementations pack these states into bitsets, while the Python implementation stores them in byte arrays.
After that, the implementation marks the simple family \(ab\) and \(n^2-ab\), precomputes the squares \(0^2,1^2,\dots,n^2\), and loops over all ordered partitions \(a\le b\le c\) with \(a+b+c=n\). For each partition it evaluates the \(46\) quadratic forms and marks the resulting counts. A separate loop over all \(a+b=n\) marks the seven nonempty subset sums built from \(a^2\), \(b^2\), and \(2ab\), ignoring \(0\) and \(n^2\). Finally it counts the marked positions and applies
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr).$$
The C++ implementation also checks the known values \(C(5)=64\), \(C(10)=274\), and \(C(20)=1150\) before evaluating the full target input.
The template generation is constant work because the search space has only \(512\) patterns. Marking the product family costs \(O(n^2)\) time. The main partition loop has \(O(n^2)\) states, since \(a\le b\le c\) and \(a+b+c=n\), and each state evaluates only \(46\) constant-size quadratic forms. The complexity-2 loop is \(O(n)\). Therefore the overall running time is \(O(n^2)\).
Memory usage is dominated by the two reachability containers on \(0,\dots,n^2\). The packed C++ and Java versions use \(\Theta(n^2)\) bits, while the Python version uses \(\Theta(n^2)\) bytes for the same logical state space.
Für eine binäre \(n\times n\)-Matrix \(A\) sei \(r(A)\) die Anzahl verschiedener Zeilen und \(c(A)\) die Anzahl verschiedener Spalten. Die Komplexität der Matrix ist
$$\kappa(A)=\max(r(A),c(A)).$$
Für jedes \(k\in\{0,1,\dots,n^2\}\) definieren wir
$$m_n(k)=\min\{\kappa(A): A \text{ ist eine binäre } n\times n\text{-Matrix mit genau } k \text{ Einsen}\}.$$
Gesucht ist dann
$$C(n)=\sum_{k=0}^{n^2} m_n(k).$$
Die Lösung durchsucht nicht alle Matrizen. Stattdessen markiert sie, welche Werte \(k\) mit Komplexität \(1\), \(2\) oder \(3\) erreichbar sind; jeder übrige Wert trägt dann \(4\) zur Summe bei.
Der Kern der Methode ist eine Erreichbarkeitsklassifikation auf dem ganzzahligen Intervall \(0,1,\dots,n^2\). Jede Konstruktion markiert bestimmte Anzahlen von Einsen, und aus den Größen dieser Klassen ergibt sich direkt \(C(n)\).
Komplexität \(1\) bedeutet, dass alle Zeilen gleich und alle Spalten gleich sind. Bei einer binären quadratischen Matrix ist das nur bei der Nullmatrix und der Einsmatrix möglich. Daher gilt
$$m_n(0)=m_n(n^2)=1.$$
Diese beiden Randwerte sind die einzigen Fälle mit Komplexität \(1\) und liefern den konstanten Anteil der Endformel.
Für die in der Implementierung verwendeten Zwei-Typ-Konstruktionen werden die \(n\) Indizes in zwei Gruppen der Größen \(a\) und \(b\) aufgeteilt, mit
$$a+b=n.$$
Die zulässigen Blockmuster reduzieren sich auf drei unabhängige Gewichte:
$$a^2,\qquad b^2,\qquad 2ab.$$
Für jedes \(a+b=n\) werden daher die sieben nichtleeren Teilmengensummen
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2$$
gebildet; anschließend verwirft die Implementierung \(0\) und \(n^2\), weil diese schon zur Komplexität \(1\) gehören. Die Vereinigung über alle \(a\) ergibt genau die Werte mit Komplexität \(2\).
Vor der vollständigen Drei-Typ-Analyse markiert die Implementierung die explizite Produktfamilie
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
Der zweite Wert folgt aus der Komplementbildung: Ersetzt man jede \(0\) durch \(1\), bleiben die Anzahlen verschiedener Zeilen und Spalten unverändert. Erreichbare Werte treten also paarweise als \(k\) und \(n^2-k\) auf. Diese einfache Familie deckt bereits viele Fälle mit Komplexität höchstens \(3\) ab.
Die Hauptkonstruktion zerlegt \(n\) in drei Teile
$$a+b+c=n,\qquad a\le b\le c.$$
Ein Drei-Typ-Muster wird durch eine binäre \(3\times3\)-Schablone beschrieben. Die Implementierungen testen alle \(2^9=512\) Schablonen, behalten nur diejenigen mit paarweise verschiedenen Zeilen, paarweise verschiedenen Spalten und identischen Multimengen von Zeilen- und Spaltenmustern. Nach dem Entfernen von Duplikaten bleiben genau \(46\) verschiedene Koeffiziententupel übrig.
Für jede überlebende Schablone hat die Anzahl der Einsen die Form
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
wobei \(d_i\in\{0,1\}\) und \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\) gelten. Die Diagonalterme zählen Blöcke innerhalb eines Typs, die gemischten Terme zählen Kreuzblöcke. Durch Auswertung aller \(46\) Formen für alle geordneten Zerlegungen \(a\le b\le c\) markiert die Lösung alle Werte, die mit dieser Drei-Typ-Konstruktion erreichbar sind.
Setze
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$$
Da genau zwei Werte Komplexität \(1\) besitzen, folgt
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$$
Nach Vereinfachung erhält man die im Programm verwendete Identität
$$C(n)=3T-4-N_2+N_4.$$
Damit reduziert sich die Aufgabe auf das Markieren der Komplexität-2-Werte und der Werte mit Komplexität höchstens \(3\).
Für \(n=5\) ist \(T=5^2+1=26\). Die Komplexität-2-Konstruktion markiert genau
$$\{1,4,8,9,12,13,16,17,21,24\},$$
also \(N_2=10\). Die kombinierte Konstruktion für Komplexität höchstens \(3\) deckt bereits alle Werte \(0,1,\dots,25\) ab, daher ist \(N_4=0\).
Somit gilt
$$C(5)=3\cdot 26-4-10+0=64.$$
Man kann dasselbe Ergebnis auch direkt aus den Klassen lesen:
$$1+1+10\cdot 2+14\cdot 3=64.$$
Also haben nur \(0\) und \(25\) Komplexität \(1\), zehn Werte haben Komplexität \(2\), und die restlichen vierzehn Werte haben Komplexität \(3\).
Die Implementierungen in C++, Python und Java folgen demselben Ablauf. Zuerst erzeugen sie aus den \(512\) binären \(3\times3\)-Schablonen den endlichen Katalog der \(46\) Koeffiziententupel für Drei-Typ-Konstruktionen. Danach reservieren sie zwei Erreichbarkeitsstrukturen über dem Bereich \(0\) bis \(n^2\): eine für Werte mit Komplexität höchstens \(3\) und eine für Werte mit Komplexität \(2\). C++ und Java verwenden dafür gepackte Bitsets, Python ein Byte-Array.
Anschließend markiert die Implementierung die einfache Familie \(ab\) und \(n^2-ab\), berechnet die Quadrate \(0^2,1^2,\dots,n^2\) vor und durchläuft alle geordneten Zerlegungen \(a\le b\le c\) mit \(a+b+c=n\). Für jede Zerlegung werden die \(46\) quadratischen Formen ausgewertet und die entstehenden Werte markiert. Eine zweite Schleife über \(a+b=n\) markiert die sieben nichtleeren Teilmengensummen aus \(a^2\), \(b^2\) und \(2ab\), wobei \(0\) und \(n^2\) übersprungen werden. Zum Schluss werden die markierten Positionen gezählt und
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr)$$
ausgewertet. Die C++-Implementierung prüft zuvor zusätzlich die bekannten Werte \(C(5)=64\), \(C(10)=274\) und \(C(20)=1150\).
Die Schablonenerzeugung ist konstante Arbeit, weil nur \(512\) Muster betrachtet werden. Das Markieren der Produktfamilie kostet \(O(n^2)\) Zeit. Die Hauptschleife über die Zerlegungen hat \(O(n^2)\) Zustände, da \(a\le b\le c\) und \(a+b+c=n\), und pro Zustand werden nur \(46\) quadratische Formen konstanter Größe ausgewertet. Die Zwei-Typ-Schleife ist \(O(n)\). Insgesamt ergibt sich also eine Laufzeit von \(O(n^2)\).
Der Speicherbedarf wird von den beiden Erreichbarkeitsstrukturen für \(0,\dots,n^2\) dominiert. Die gepackten Versionen in C++ und Java benötigen \(\Theta(n^2)\) Bits, die Python-Version \(\Theta(n^2)\) Bytes für denselben logischen Zustandsraum.
Bir \(n\times n\) ikili matris \(A\) için \(r(A)\) farklı satır sayısını, \(c(A)\) ise farklı sütun sayısını göstersin. Matrisin karmaşıklığı
$$\kappa(A)=\max(r(A),c(A))$$
olarak tanımlanır. Her \(k\in\{0,1,\dots,n^2\}\) için
$$m_n(k)=\min\{\kappa(A): A \text{ tam olarak } k \text{ tane }1\text{ içeren } n\times n \text{ bir ikili matristir}\}$$
tanımını yapalım. İstenen büyüklük
$$C(n)=\sum_{k=0}^{n^2} m_n(k)$$
olur. Uygulama bütün matrisleri tek tek denemez; bunun yerine hangi \(k\) değerlerinin karmaşıklık \(1\), \(2\) veya \(3\) ile elde edilebildiğini işaretler ve geriye kalan her değeri \(4\) olarak sayar.
Ana fikir, problemi \(0,1,\dots,n^2\) aralığında bir erişilebilirlik problemine dönüştürmektir. Her yapı belirli bir \(1\) sayısı kümesini işaretler; son toplam da yalnızca bu kümelerin büyüklüklerine bağlıdır.
Karmaşıklık \(1\), bütün satırların aynı ve bütün sütunların aynı olması demektir. İkili kare matrislerde bu yalnızca tamamen sıfır ve tamamen bir olan iki matris için mümkündür. Dolayısıyla
$$m_n(0)=m_n(n^2)=1.$$
Karmaşıklığı \(1\) olan tek iki uç değer bunlardır ve nihai formüldeki sabit terim buradan gelir.
Çözümde kullanılan iki tipli yapıda \(n\) indisleri büyüklükleri \(a\) ve \(b\) olan iki gruba ayrılır:
$$a+b=n.$$
İzin verilen blok kalıpları üç bağımsız ağırlığa indirgenir:
$$a^2,\qquad b^2,\qquad 2ab.$$
Böylece her \(a+b=n\) ayrımı için uygulama şu yedi boş olmayan altküme toplamını üretir:
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2.$$
Daha sonra \(0\) ve \(n^2\) uç değerleri çıkarılır; çünkü bunlar zaten karmaşıklık \(1\) durumunda sayılmıştır. Tüm \(a\) değerleri üzerinde birleşim alındığında karmaşıklığı \(2\) olan tüm sayılar elde edilir.
Tam üç tipli analize geçmeden önce uygulama şu açık çarpım ailesini işaretler:
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
İkinci değer tüm bitleri ters çevirmekten gelir: her \(0\)'ı \(1\), her \(1\)'i \(0\) yapmak farklı satır ve sütun sayılarını değiştirmez. Bu yüzden erişilebilir sayılar \(k\) ve \(n^2-k\) biçiminde tamamlayıcı çiftler halinde ortaya çıkar. Bu ucuz aile bile karmaşıklığı en fazla \(3\) olan birçok değeri kapsar.
Ana yapı \(n\)'yi üç parçaya ayırır:
$$a+b+c=n,\qquad a\le b\le c.$$
Üç tipli bir desen, ikili bir \(3\times3\) şablon ile kodlanır. Uygulamalar tüm \(2^9=512\) şablonu dener; satırları ikişer ikişer farklı olan, sütunları ikişer ikişer farklı olan ve satır desenleri çoklu kümesi ile sütun desenleri çoklu kümesi aynı olanları tutar. Tekrarlı olanlar atıldıktan sonra geriye tam olarak \(46\) farklı katsayı altılısı kalır.
Bu şablonların her biri için \(1\) sayısı şu kuadratik form ile yazılır:
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
burada \(d_i\in\{0,1\}\) ve \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\) olur. Diyagonal terimler aynı tip içindeki blokları, karışık terimler ise tipler arası blokları sayar. Tüm sıralı bölmeler \(a\le b\le c\) üzerinde tüm \(46\) form değerlendirilince bu üç tipli yapı ile erişilebilen tüm sayılar işaretlenmiş olur.
Şimdi
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}$$
tanımlarını yapalım. Karmaşıklığı \(1\) olan tam iki değer bulunduğundan
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4$$
elde edilir. Sadeleştirince uygulamanın kullandığı kimlik çıkar:
$$C(n)=3T-4-N_2+N_4.$$
Yani problem, karmaşıklık-2 kümesini ve karmaşıklığı en fazla 3 olan kümesini işaretleyip bunların büyüklüklerini saymaya indirgenir.
\(n=5\) için \(T=5^2+1=26\) olur. Karmaşıklık-2 yapısı tam olarak
$$\{1,4,8,9,12,13,16,17,21,24\}$$
kümesini verir; dolayısıyla \(N_2=10\). Karmaşıklığı en fazla \(3\) olan birleşik yapı ise \(0,1,\dots,25\) değerlerinin tamamını kapsar, yani \(N_4=0\).
Böylece
$$C(5)=3\cdot 26-4-10+0=64$$
sonucu çıkar. Aynı sonuç sınıflardan doğrudan da okunabilir:
$$1+1+10\cdot 2+14\cdot 3=64.$$
Yani yalnızca \(0\) ve \(25\) karmaşıklık \(1\)'dir; on değer karmaşıklık \(2\), kalan on dört değer ise karmaşıklık \(3\) verir.
C++, Python ve Java uygulamalarının akışı aynıdır. Önce \(512\) adet ikili \(3\times3\) şablondan üç tipli yapılar için gerekli olan sonlu \(46\) katsayı altılısı üretilir. Ardından \(0\) ile \(n^2\) arasındaki aralık için iki erişilebilirlik yapısı ayrılır: biri karmaşıklığı en fazla \(3\) olan değerler için, diğeri karmaşıklığı \(2\) olan değerler için. C++ ve Java bu durumu bitset ile sıkıştırılmış tutar; Python ise bytearray kullanır.
Daha sonra uygulama önce \(ab\) ve \(n^2-ab\) ailesini işaretler, \(0^2,1^2,\dots,n^2\) karelerini önceden hesaplar ve \(a+b+c=n\) ile \(a\le b\le c\) koşullarını sağlayan tüm bölmeler üzerinde döner. Her bölme için \(46\) kuadratik form değerlendirilir ve çıkan \(k\) değerleri işaretlenir. Ayrı bir döngü de \(a+b=n\) için \(a^2\), \(b^2\) ve \(2ab\)'den oluşan yedi boş olmayan altküme toplamını üretir; \(0\) ve \(n^2\) atlanır. Son aşamada işaretli konumlar sayılır ve
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr)$$
formülü uygulanır. C++ sürümü ayrıca tam girdiye geçmeden önce \(C(5)=64\), \(C(10)=274\) ve \(C(20)=1150\) denetimlerini yapar.
Şablon üretimi sabit maliyetlidir; çünkü yalnızca \(512\) desen incelenir. Çarpım ailesini işaretlemek \(O(n^2)\) zaman alır. Ana bölme döngüsü de \(a\le b\le c\) ve \(a+b+c=n\) koşullarından dolayı \(O(n^2)\) sayıda durum içerir ve her durumda yalnızca \(46\) sabit boyutlu form hesaplanır. Karmaşıklık-2 döngüsü ise \(O(n)\) zamanlıdır. Sonuç olarak toplam süre \(O(n^2)\) olur.
Bellek maliyetini \(0,\dots,n^2\) aralığını tutan iki erişilebilirlik yapısı belirler. Sıkıştırılmış C++ ve Java sürümleri \(\Theta(n^2)\) bit, Python sürümü ise aynı mantıksal durum alanı için \(\Theta(n^2)\) bayt kullanır.
Para una matriz binaria \(n\times n\) \(A\), sea \(r(A)\) el número de filas distintas y \(c(A)\) el número de columnas distintas. La complejidad de la matriz es
$$\kappa(A)=\max(r(A),c(A)).$$
Para cada \(k\in\{0,1,\dots,n^2\}\), definimos
$$m_n(k)=\min\{\kappa(A): A \text{ es una matriz binaria } n\times n \text{ con exactamente } k \text{ unos}\}.$$
La cantidad pedida es
$$C(n)=\sum_{k=0}^{n^2} m_n(k).$$
La implementación no recorre matrices una por una. En cambio, marca qué valores de \(k\) pueden alcanzarse con complejidad \(1\), \(2\) o \(3\), y después asigna complejidad \(4\) a todo valor no marcado.
La idea central es convertir el problema en una cuestión de alcanzabilidad sobre el intervalo \(0,1,\dots,n^2\). Cada construcción marca ciertos números de unos, y el valor final depende solo del tamaño de esas clases.
La complejidad \(1\) significa que todas las filas son iguales y todas las columnas son iguales. En una matriz binaria cuadrada eso solo ocurre para la matriz nula y la matriz llena de unos. Por tanto,
$$m_n(0)=m_n(n^2)=1.$$
Esos dos extremos son los únicos casos de complejidad \(1\), y explican el término constante de la fórmula final.
En las construcciones de dos tipos que usan las implementaciones, los \(n\) índices se separan en dos grupos de tamaños \(a\) y \(b\), con
$$a+b=n.$$
Los patrones de bloques admisibles se reducen a tres pesos independientes:
$$a^2,\qquad b^2,\qquad 2ab.$$
Así, para cada partición \(a+b=n\), la implementación enumera las siete sumas no vacías de subconjuntos
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2,$$
y después descarta \(0\) y \(n^2\), ya tratados como complejidad \(1\). La unión sobre todos los valores de \(a\) produce exactamente el conjunto de valores con complejidad \(2\).
Antes del análisis completo con tres tipos, las implementaciones marcan la familia explícita
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
El segundo valor aparece por complementar la matriz: cambiar cada \(0\) por \(1\) no modifica el número de filas distintas ni el de columnas distintas. Por eso los valores alcanzables aparecen en pares complementarios \(k\leftrightarrow n^2-k\). Esta familia barata ya cubre muchos casos con complejidad como máximo \(3\).
La construcción principal divide \(n\) en tres partes:
$$a+b+c=n,\qquad a\le b\le c.$$
Un patrón de tres tipos queda codificado por una plantilla binaria \(3\times3\). Las implementaciones recorren las \(2^9=512\) plantillas posibles y conservan solo aquellas cuyas tres filas son distintas entre sí, cuyas tres columnas también lo son y cuyo multiconjunto de patrones de fila coincide con el multiconjunto de patrones de columna. Tras eliminar duplicados, quedan exactamente \(46\) tuplas distintas de coeficientes.
Para cada plantilla superviviente, el número de unos tiene la forma cuadrática
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
donde \(d_i\in\{0,1\}\) y \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\). Los términos diagonales cuentan bloques dentro de un mismo tipo y los términos mixtos cuentan bloques entre tipos distintos. Al evaluar las \(46\) formas sobre todas las particiones ordenadas \(a\le b\le c\), la implementación marca todos los valores alcanzables mediante esta construcción de tres tipos.
Definamos
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$$
Como exactamente dos valores tienen complejidad \(1\), se obtiene
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$$
Al simplificar aparece la identidad que usa la implementación:
$$C(n)=3T-4-N_2+N_4.$$
Por tanto, el problema queda reducido a marcar el conjunto de complejidad \(2\) y el conjunto de complejidad a lo sumo \(3\), y luego contar sus cardinalidades.
Para \(n=5\), tenemos \(T=5^2+1=26\). La construcción de complejidad \(2\) marca exactamente
$$\{1,4,8,9,12,13,16,17,21,24\},$$
de modo que \(N_2=10\). La construcción combinada de complejidad \(\le 3\) cubre todos los valores \(0,1,\dots,25\), así que \(N_4=0\).
Entonces
$$C(5)=3\cdot 26-4-10+0=64.$$
La misma cuenta puede leerse directamente por clases:
$$1+1+10\cdot 2+14\cdot 3=64.$$
Es decir, solo \(0\) y \(25\) tienen complejidad \(1\), diez valores tienen complejidad \(2\) y los catorce restantes tienen complejidad \(3\).
Las implementaciones en C++, Python y Java siguen la misma tubería. Primero generan el catálogo finito de \(46\) tuplas de coeficientes para tres tipos a partir de las \(512\) plantillas binarias \(3\times3\). Después reservan dos contenedores de alcanzabilidad sobre el intervalo \(0\) a \(n^2\): uno para los valores con complejidad a lo sumo \(3\) y otro para los valores con complejidad \(2\). Las versiones en C++ y Java usan bitsets empaquetados, mientras que la versión en Python usa arreglos de bytes.
Luego la implementación marca la familia simple \(ab\) y \(n^2-ab\), precalcula los cuadrados \(0^2,1^2,\dots,n^2\), y recorre todas las particiones ordenadas \(a\le b\le c\) con \(a+b+c=n\). Para cada partición evalúa las \(46\) formas cuadráticas y marca los valores obtenidos. Un segundo bucle sobre \(a+b=n\) marca las siete sumas no vacías construidas a partir de \(a^2\), \(b^2\) y \(2ab\), descartando \(0\) y \(n^2\). Al final cuenta las posiciones marcadas y aplica
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr).$$
La versión en C++ además comprueba los valores conocidos \(C(5)=64\), \(C(10)=274\) y \(C(20)=1150\) antes de evaluar la entrada completa.
La generación de plantillas es trabajo constante porque solo hay \(512\) patrones posibles. Marcar la familia de productos cuesta \(O(n^2)\) tiempo. El bucle principal sobre particiones tiene \(O(n^2)\) estados, ya que \(a\le b\le c\) y \(a+b+c=n\), y en cada estado solo se evalúan \(46\) formas cuadráticas de tamaño constante. El bucle de complejidad \(2\) es \(O(n)\). En conjunto, el tiempo total es \(O(n^2)\).
La memoria está dominada por los dos contenedores de alcanzabilidad sobre \(0,\dots,n^2\). Las versiones empaquetadas en C++ y Java usan \(\Theta(n^2)\) bits, mientras que la versión en Python usa \(\Theta(n^2)\) bytes para el mismo espacio lógico de estados.
对于一个 \(n\times n\) 的二进制矩阵 \(A\)，记 \(r(A)\) 为不同的行数，\(c(A)\) 为不同的列数。矩阵的复杂度定义为
$$\kappa(A)=\max(r(A),c(A)).$$
对每个 \(k\in\{0,1,\dots,n^2\}\)，定义
$$m_n(k)=\min\{\kappa(A): A \text{ 是一个恰好包含 } k \text{ 个 }1\text{ 的 } n\times n \text{ 二进制矩阵}\}.$$
题目要求计算
$$C(n)=\sum_{k=0}^{n^2} m_n(k).$$
实现并不直接枚举所有矩阵，而是判断每个 \(k\) 是否能用复杂度 \(1\)、\(2\) 或 \(3\) 构造出来；凡是没有被这些构造覆盖的值，都在最后按复杂度 \(4\) 处理。
核心思路是把原问题变成整数区间 \(0,1,\dots,n^2\) 上的“可达性标记”问题。不同的构造会标记出不同的 \(1\) 的个数，最后只需要统计各个复杂度层级分别覆盖了多少个整数即可。
复杂度为 \(1\) 表示所有行都相同，并且所有列也都相同。对二进制方阵来说，这只会发生在全零矩阵和全一矩阵上，因此
$$m_n(0)=m_n(n^2)=1.$$
也就是说，复杂度为 \(1\) 的只有两个端点 \(0\) 和 \(n^2\)，它们在最终公式里贡献出固定常数项。
在实现使用的二类型构造中，\(n\) 个指标被分成大小为 \(a\) 与 \(b\) 的两组，满足
$$a+b=n.$$
对应的可行块结构会压缩成三个独立权重：
$$a^2,\qquad b^2,\qquad 2ab.$$
因此，对每个分拆 \(a+b=n\)，实现都会枚举下面七个非空子集和：
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2.$$
随后再把端点 \(0\) 和 \(n^2\) 去掉，因为它们已经在复杂度为 \(1\) 的情形中处理过了。把所有 \(a\) 的结果取并集，就得到全部复杂度为 \(2\) 的 \(k\) 值。
在进入完整的三类型分析之前，实现先标记一个显式的乘积家族：
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
第二个值来自补矩阵对称性：把每个 \(0\) 变成 \(1\)、每个 \(1\) 变成 \(0\)，不会改变不同的行数和不同的列数，所以可达的 \(k\) 会和 \(n^2-k\) 成对出现。这个简单家族已经覆盖了大量复杂度不超过 \(3\) 的值。
主构造把 \(n\) 分成三部分：
$$a+b+c=n,\qquad a\le b\le c.$$
一个三类型结构可由一个二进制 \(3\times3\) 模板描述。实现会枚举全部 \(2^9=512\) 个模板，只保留满足下列条件的模板：三行两两不同，三列两两不同，并且“行模式的多重集合”与“列模式的多重集合”相同。去重之后，最终只剩下 \(46\) 个不同的系数六元组。
对每个保留下来的模板，\(1\) 的总数都可以写成如下二次型：
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
其中 \(d_i\in\{0,1\}\)，而 \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\)。对角项表示同类型内部的块，混合项表示不同类型之间的块。只要把全部 \(46\) 个二次型在所有满足 \(a\le b\le c\) 且 \(a+b+c=n\) 的分拆上都计算一遍，就能标记出所有通过三类型结构可达的 \(k\) 值。
记
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$$
由于复杂度为 \(1\) 的值恰好只有两个，所以
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$$
化简后得到实现直接使用的恒等式：
$$C(n)=3T-4-N_2+N_4.$$
这样一来，问题就变成了两件事：标记复杂度为 \(2\) 的集合，以及标记复杂度不超过 \(3\) 的集合，然后统计它们的大小。
当 \(n=5\) 时，
$$T=5^2+1=26.$$
复杂度为 \(2\) 的构造恰好标记出
$$\{1,4,8,9,12,13,16,17,21,24\},$$
因此 \(N_2=10\)。而复杂度 \(\le 3\) 的合并构造已经覆盖了全部 \(0,1,\dots,25\)，所以 \(N_4=0\)。
于是
$$C(5)=3\cdot 26-4-10+0=64.$$
也可以按复杂度分层直接求和：
$$1+1+10\cdot 2+14\cdot 3=64.$$
也就是说，只有 \(0\) 和 \(25\) 的复杂度为 \(1\)，有 \(10\) 个值的复杂度为 \(2\)，其余 \(14\) 个值的复杂度为 \(3\)。
C++、Python 和 Java 的实现流程完全一致。第一步是从 \(512\) 个二进制 \(3\times3\) 模板中生成那 \(46\) 个三类型系数六元组。第二步是在区间 \(0\) 到 \(n^2\) 上建立两个可达性容器：一个表示“复杂度不超过 \(3\) 的值”，另一个表示“复杂度恰好为 \(2\) 的值”。C++ 与 Java 使用压缩 bitset，Python 则用字节数组保存同样的逻辑状态。
随后，实现先标记简单家族 \(ab\) 与 \(n^2-ab\)，预先计算平方数 \(0^2,1^2,\dots,n^2\)，再遍历所有满足 \(a+b+c=n\) 且 \(a\le b\le c\) 的有序分拆。对每个分拆，程序都会计算那 \(46\) 个二次型并标记结果。另一条循环则遍历所有 \(a+b=n\)，标记由 \(a^2\)、\(b^2\)、\(2ab\) 组成的七个非空子集和，并排除 \(0\) 与 \(n^2\)。最后只需要统计已标记位置的数量，并代入
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr)$$
即可得到答案。C++ 版本还会先检查已知值 \(C(5)=64\)、\(C(10)=274\) 和 \(C(20)=1150\)，再处理最终输入。
模板预处理是常数时间工作，因为总共只有 \(512\) 个模板。标记乘积家族需要 \(O(n^2)\) 时间。主分拆循环的状态数也是 \(O(n^2)\)，因为满足 \(a\le b\le c\) 且 \(a+b+c=n\) 的有序三元组数量是二次级别，而每个状态只需计算 \(46\) 个常数规模的二次型。复杂度为 \(2\) 的循环只要 \(O(n)\) 时间。因此总时间复杂度为 \(O(n^2)\)。
内存由两个覆盖区间 \(0,\dots,n^2\) 的可达性容器主导。压缩版的 C++ 与 Java 实现使用 \(\Theta(n^2)\) 比特，而 Python 版本为同一逻辑状态空间使用 \(\Theta(n^2)\) 字节。
Для бинарной матрицы \(A\) размера \(n\times n\) обозначим через \(r(A)\) число различных строк, а через \(c(A)\) число различных столбцов. Сложность матрицы определяется как
$$\kappa(A)=\max(r(A),c(A)).$$
Для каждого \(k\in\{0,1,\dots,n^2\}\) введём
$$m_n(k)=\min\{\kappa(A): A \text{ — бинарная } n\times n \text{ матрица ровно с } k \text{ единицами}\}.$$
Требуется найти
$$C(n)=\sum_{k=0}^{n^2} m_n(k).$$
Реализация не перебирает матрицы напрямую. Вместо этого она отмечает, какие значения \(k\) достижимы при сложности \(1\), \(2\) или \(3\), а все неотмеченные значения в конце дают вклад \(4\).
Главная идея состоит в том, чтобы превратить задачу в задачу достижимости на отрезке \(0,1,\dots,n^2\). Каждая конструкция помечает некоторые количества единиц, а итоговая сумма зависит только от числа значений в каждом классе сложности.
Сложность \(1\) означает, что все строки одинаковы и все столбцы тоже одинаковы. Для бинарной квадратной матрицы это возможно только для нулевой матрицы и матрицы из одних единиц. Поэтому
$$m_n(0)=m_n(n^2)=1.$$
Это единственные два значения со сложностью \(1\), и именно они создают постоянный член в финальной формуле.
В двухтипных конструкциях, используемых реализацией, \(n\) индексов разбиваются на две группы размеров \(a\) и \(b\), где
$$a+b=n.$$
Допустимые блоковые шаблоны сводятся к трём независимым весам:
$$a^2,\qquad b^2,\qquad 2ab.$$
Значит, для каждого разбиения \(a+b=n\) реализация перебирает семь непустых сумм по подмножествам
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2,$$
после чего отбрасывает крайние значения \(0\) и \(n^2\), уже учтённые как сложность \(1\). Объединение по всем \(a\) даёт полный набор значений со сложностью \(2\).
До полного анализа трёх типов реализация помечает явное семейство
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
Второе значение получается дополнением матрицы: замена каждого \(0\) на \(1\) сохраняет число различных строк и столбцов. Поэтому достижимые значения естественно появляются парами \(k\leftrightarrow n^2-k\). Уже это простое семейство покрывает много случаев со сложностью не более \(3\).
Основная конструкция разбивает \(n\) на три части:
$$a+b+c=n,\qquad a\le b\le c.$$
Трёхтипный шаблон задаётся бинарной матрицей \(3\times3\). Реализация перебирает все \(2^9=512\) шаблонов и оставляет только те, у которых три строки попарно различны, три столбца попарно различны, а мультимножество строковых шаблонов совпадает с мультимножеством столбцовых шаблонов. После удаления дублей остаётся ровно \(46\) различных наборов коэффициентов.
Для каждого такого шаблона число единиц выражается квадратичной формой
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
где \(d_i\in\{0,1\}\), а \(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\). Диагональные члены отвечают за блоки внутри одного типа, смешанные члены — за блоки между разными типами. Если вычислить все \(46\) форм для всех упорядоченных разбиений \(a\le b\le c\), то будут отмечены все значения, достижимые этой трёхтипной конструкцией.
Положим
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$$
Поскольку значений со сложностью \(1\) ровно два, получаем
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$$
После упрощения имеем формулу, которую использует реализация:
$$C(n)=3T-4-N_2+N_4.$$
Значит, задача сводится к отметке множества значений сложности \(2\) и множества значений сложности не более \(3\), а затем к подсчёту их мощностей.
При \(n=5\) имеем \(T=5^2+1=26\). Конструкция сложности \(2\) отмечает ровно
$$\{1,4,8,9,12,13,16,17,21,24\},$$
поэтому \(N_2=10\). Объединённая конструкция для сложности \(\le 3\) покрывает все значения \(0,1,\dots,25\), так что \(N_4=0\).
Следовательно,
$$C(5)=3\cdot 26-4-10+0=64.$$
Тот же результат можно прочитать и по классам сложности:
$$1+1+10\cdot 2+14\cdot 3=64.$$
То есть только \(0\) и \(25\) имеют сложность \(1\), десять значений имеют сложность \(2\), а оставшиеся четырнадцать — сложность \(3\).
Реализации на C++, Python и Java следуют одному и тому же конвейеру. Сначала они строят конечный каталог из \(46\) коэффициентных шестёрок для трёхтипных конструкций, исходя из \(512\) бинарных шаблонов \(3\times3\). Затем они создают две структуры достижимости на интервале от \(0\) до \(n^2\): одну для значений со сложностью не более \(3\), вторую для значений со сложностью \(2\). В версиях на C++ и Java это упакованные bitset-структуры, а в Python — массивы байтов.
Далее реализация отмечает простое семейство \(ab\) и \(n^2-ab\), заранее вычисляет квадраты \(0^2,1^2,\dots,n^2\) и перебирает все упорядоченные разбиения \(a\le b\le c\) при условии \(a+b+c=n\). Для каждого разбиения вычисляются все \(46\) квадратичных форм, и соответствующие значения помечаются. Отдельный цикл по \(a+b=n\) помечает семь непустых сумм по подмножествам, построенных из \(a^2\), \(b^2\) и \(2ab\), пропуская \(0\) и \(n^2\). В конце остаётся подсчитать количество отмеченных позиций и применить
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr).$$
Версия на C++ дополнительно проверяет известные значения \(C(5)=64\), \(C(10)=274\) и \(C(20)=1150\), прежде чем считать полный вход.
Построение шаблонов требует постоянного времени, поскольку рассматриваются только \(512\) вариантов. Отметка семейства произведений занимает \(O(n^2)\) времени. Главный цикл по разбиениям имеет \(O(n^2)\) состояний, так как \(a\le b\le c\) и \(a+b+c=n\), и в каждом состоянии вычисляются лишь \(46\) квадратичных форм постоянного размера. Цикл для сложности \(2\) имеет стоимость \(O(n)\). Следовательно, общее время работы равно \(O(n^2)\).
Память определяется двумя структурами достижимости на диапазоне \(0,\dots,n^2\). Упакованные версии на C++ и Java используют \(\Theta(n^2)\) бит, а версия на Python — \(\Theta(n^2)\) байт для того же логического пространства состояний.
لأي مصفوفة ثنائية \(A\) من الحجم \(n\times n\)، نرمز بـ \(r(A)\) إلى عدد الصفوف المختلفة، وبـ \(c(A)\) إلى عدد الأعمدة المختلفة. ويُعرَّف تعقيد المصفوفة بالصيغة
$$\kappa(A)=\max(r(A),c(A)).$$
ولكل \(k\in\{0,1,\dots,n^2\}\) نعرّف
$$m_n(k)=\min\{\kappa(A): A \text{ is an } n\times n \text{ binary matrix with exactly } k \text{ ones}\}.$$
والكمية المطلوبة هي
$$C(n)=\sum_{k=0}^{n^2} m_n(k).$$
لا تعتمد الشيفرة على تعداد كل المصفوفات الممكنة، بل تحدد أي القيم \(k\) يمكن الوصول إليها بتعقيد \(1\) أو \(2\) أو \(3\)، ثم تعتبر كل قيمة غير معلَّمة ذات تعقيد \(4\).
الفكرة الأساسية هي تحويل المسألة إلى مسألة قابلية وصول على المجال \(0,1,\dots,n^2\). كل بناء رياضي يعلّم بعض أعداد الآحاد الممكنة، ثم تُستخرج القيمة النهائية من عدد القيم الموجودة في كل فئة من فئات التعقيد.
التعقيد \(1\) يعني أن جميع الصفوف متطابقة وجميع الأعمدة متطابقة أيضًا. وهذا لا يحدث في مصفوفة ثنائية مربعة إلا في حالتي المصفوفة الصفرية والمصفوفة المملوءة بالآحاد. لذلك
$$m_n(0)=m_n(n^2)=1.$$
وهاتان القيمتان الطرفيتان هما الوحيدتان ذواتا التعقيد \(1\)، ومنهما يأتي الحد الثابت في الهوية النهائية.
في البنى ثنائية الأنماط التي تستخدمها التطبيقات، تُقسَّم الفهارس \(n\) إلى مجموعتين بحجمين \(a\) و\(b\) بحيث
$$a+b=n.$$
وتختزل الأنماط المسموح بها إلى ثلاثة أوزان مستقلة:
$$a^2,\qquad b^2,\qquad 2ab.$$
ولهذا، من أجل كل تقسيم \(a+b=n\)، تُحصي الشيفرة المجاميع السبعة غير الفارغة التالية:
$$a^2,\ b^2,\ 2ab,\ a^2+b^2,\ a^2+2ab,\ b^2+2ab,\ a^2+b^2+2ab=n^2.$$
ثم تستبعد \(0\) و\(n^2\)، لأنهما عولجا أصلًا ضمن حالة التعقيد \(1\). واتحاد هذه القيم عبر جميع اختيارات \(a\) يعطي بالضبط مجموعة القيم ذات التعقيد \(2\).
قبل الانتقال إلى التحليل الكامل لثلاثة أنماط، تقوم التطبيقات بتعليم العائلة الصريحة
$$k=ab,\qquad k=n^2-ab,\qquad 0\le a,b\le n.$$
وتأتي القيمة الثانية من مبدأ المتممة: قلب كل \(0\) إلى \(1\) لا يغيّر عدد الصفوف المختلفة ولا عدد الأعمدة المختلفة. لذلك تظهر القيم القابلة للوصول على شكل أزواج متممة \(k\leftrightarrow n^2-k\). وهذه العائلة السهلة تغطي بالفعل عددًا كبيرًا من الحالات ذات التعقيد الذي لا يزيد على \(3\).
البناء الرئيسي يقسم \(n\) إلى ثلاثة أجزاء:
$$a+b+c=n,\qquad a\le b\le c.$$
ويُمثَّل كل بناء من ثلاثة أنماط بواسطة قالب ثنائي \(3\times3\). تقوم التطبيقات بتعداد جميع القوالب الممكنة وعددها \(2^9=512\)، ثم تُبقي فقط على القوالب التي تكون صفوفها الثلاثة مختلفة زوجيًا، وأعمدتها الثلاثة مختلفة زوجيًا، ويكون فيها متعدد أنماط الصفوف مساويًا لمتعدد أنماط الأعمدة. وبعد إزالة التكرارات يبقى بالضبط \(46\) سداسيًا مختلفًا من المعاملات.
ولكل قالب باقٍ، يُكتب عدد الآحاد على صورة الشكل التربيعي
$$k=d_1a^2+d_2b^2+d_3c^2+e_{ab}ab+e_{ac}ac+e_{bc}bc,$$
حيث \(d_i\in\{0,1\}\) و\(e_{ab},e_{ac},e_{bc}\in\{0,1,2\}\). تمثل الحدود القطرية الكتل الداخلية لكل نمط، بينما تمثل الحدود المختلطة الكتل الواقعة بين الأنماط المختلفة. وعند تقييم جميع الأشكال وعددها \(46\) على كل التقسيمات المرتبة التي تحقق \(a\le b\le c\) و\(a+b+c=n\)، نحصل على جميع القيم التي يمكن الوصول إليها بهذه البنية ثلاثية الأنماط.
لنعرّف
$$T=n^2+1,$$
$$N_2=\#\{k: m_n(k)=2\},\qquad N_{\le 3}=\#\{k: m_n(k)\le 3\},\qquad N_4=T-N_{\le 3}.$$
وبما أن هناك قيمتين فقط لهما تعقيد \(1\)، فإن
$$C(n)=2+2N_2+3(N_{\le 3}-N_2-2)+4N_4.$$
وبعد التبسيط نحصل على الهوية التي تعتمدها التطبيقات:
$$C(n)=3T-4-N_2+N_4.$$
وهكذا تصبح المهمة هي تعليم مجموعة التعقيد \(2\) ومجموعة التعقيد الذي لا يتجاوز \(3\)، ثم عدّ عناصر كل منهما.
عندما \(n=5\) يكون
$$T=5^2+1=26.$$
وتعلّم بنية التعقيد \(2\) المجموعة التالية بالضبط:
$$\{1,4,8,9,12,13,16,17,21,24\},$$
ومن ثم \(N_2=10\). أما البنية المجمعة للتعقيد \(\le 3\) فتغطي جميع القيم من \(0\) إلى \(25\)، ولذلك \(N_4=0\).
إذًا
$$C(5)=3\cdot 26-4-10+0=64.$$
ويمكن قراءة النتيجة نفسها مباشرة من طبقات التعقيد:
$$1+1+10\cdot 2+14\cdot 3=64.$$
أي إن \(0\) و\(25\) فقط لهما تعقيد \(1\)، وهناك عشر قيم ذات تعقيد \(2\)، أما القيم الأربع عشرة الباقية فلها تعقيد \(3\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا تُنشئ الكتالوج المنتهي الذي يحوي \(46\) سداسيًا من المعاملات الخاصة بالبنى ثلاثية الأنماط، وذلك انطلاقًا من \(512\) قالبًا ثنائيًا من نوع \(3\times3\). ثم تُخصَّص بنيتا وصول على المجال من \(0\) إلى \(n^2\): بنية للقيم ذات التعقيد الذي لا يتجاوز \(3\)، وبنية أخرى للقيم ذات التعقيد \(2\). تستعمل نسختا C++ وJava bitset مضغوطًا، بينما تستعمل نسخة Python مصفوفات بايت.
بعد ذلك تعلّم الشيفرة أولًا العائلة البسيطة \(ab\) و\(n^2-ab\)، وتحسب مسبقًا المربعات \(0^2,1^2,\dots,n^2\)، ثم تمر على جميع التقسيمات المرتبة \(a\le b\le c\) التي تحقق \(a+b+c=n\). ولكل تقسيم تُقيَّم الأشكال التربيعية الستة والأربعون وتُعلَّم القيم الناتجة. ثم توجد حلقة مستقلة على جميع \(a+b=n\) لتعليم المجاميع السبعة غير الفارغة المبنية من \(a^2\) و\(b^2\) و\(2ab\)، مع تجاهل \(0\) و\(n^2\). وفي النهاية يُحسب عدد المواقع المعلَّمة ثم تُطبَّق الصيغة
$$C(n)=3(n^2+1)-4-N_2+\bigl((n^2+1)-N_{\le 3}\bigr).$$
وتتحقق نسخة C++ أيضًا من القيم المعروفة \(C(5)=64\) و\(C(10)=274\) و\(C(20)=1150\) قبل معالجة المُدخل الكامل.
إن توليد القوالب عمل ثابت الحجم، لأن عدد الأنماط الممكنة لا يتجاوز \(512\). أما تعليم عائلة الجداء فيكلف \(O(n^2)\) زمنًا. وتحتوي الحلقة الرئيسية الخاصة بالتقسيمات على \(O(n^2)\) حالة، لأن الشروط \(a\le b\le c\) و\(a+b+c=n\) تعطي عددًا تربيعيًا من الحالات، وفي كل حالة لا تُحسب إلا \(46\) صيغة تربيعية ثابتة الحجم. أما حلقة التعقيد \(2\) فتكلف \(O(n)\) فقط. لذلك يكون الزمن الكلي \(O(n^2)\).
وتُهيمن على الذاكرة بنيتا الوصول الممتدتان على المجال \(0,\dots,n^2\). تستخدم النسختان المضغوطتان في C++ وJava مقدار \(\Theta(n^2)\) من البتات، بينما تستخدم نسخة Python مقدار \(\Theta(n^2)\) من البايتات للمجال المنطقي نفسه.