Let \(H(n)\) denote the number of regular hexagons whose six vertices lie on lattice points inside the triangular lattice region of size \(n\). In axial coordinates this region is
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}.$$
The task is not just to evaluate one \(H(n)\), but to compute the cumulative total
$$S(N)=\sum_{n=3}^{N} H(n).$$
A direct geometric search would be far too slow, so the solution turns the geometry into a one-parameter summation.
The key observation is that every lattice regular hexagon can be described by one side vector together with its \(60^\circ\) rotation, and that the boundary conditions depend only on one simple integer parameter.
Choose a nonzero lattice side vector
$$u=(a,b).$$
In axial coordinates, rotation by \(60^\circ\) sends this vector to
$$v=(-b,a+b).$$
If \(P\) is one vertex of the hexagon, then the six vertices are
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u.$$
This already determines a regular hexagon on the triangular lattice: consecutive edges are obtained by repeated \(60^\circ\) turns, so all sides have the same length and all interior angles are \(120^\circ\).
The same hexagon can be described from several sides, so we restrict to the canonical sector
$$a>0,\qquad b\ge 0.$$
Among the six side directions of a regular hexagon, exactly one lies in this sector, so this removes double counting.
Now define the parameter
$$k=a+b.$$
For a fixed \(k\), the admissible canonical pairs are
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0), $$
so there are exactly \(k\) such pairs. Different pairs may correspond to different lattice shapes, but they all consume the same amount of room against the boundary, and that is the quantity that matters for counting placements.
Write the base vertex as \(P=(x,y)\). We must force all six vertices to remain inside \(T_n\), meaning
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n$$
for every listed vertex.
The strongest lower bound on the \(x\)-coordinate comes from \(P+2v-u\), whose first coordinate is
$$x-a-2b,$$
so we need
$$x\ge a+2b.$$
The strongest upper bound on \(x+y\) comes from \(P+u+v\), whose coordinate sum is
$$x+y+2a+b,$$
so we also need
$$x+y\le n-2a-b.$$
The remaining inequalities are weaker once these are satisfied. Shift the base point by setting
$$x'=x-(a+2b).$$
Then the conditions become
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k.$$
This is again a triangular lattice region, now of size \(n-3k\). Therefore the number of valid placements for one fixed canonical pair with parameter \(k\) is
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2},$$
provided \(3k\le n\), and it is \(0\) otherwise.
Since there are exactly \(k\) canonical pairs with \(a+b=k\), we obtain
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}.$$
This already gives a fast \(O(n)\) formula for a single \(H(n)\).
For the cumulative total, swap the order of summation:
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$$
Let
$$t=n-3k+1,\qquad M=N-3k+1.$$
Then the inner sum becomes
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}.$$
So the final closed form used by the implementation is
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
Here \(\lfloor 6/3\rfloor=2\), so only \(k=1\) and \(k=2\) contribute.
For \(k=1\):
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$$
For \(k=2\):
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$$
Therefore
$$H(6)=10+2=12,$$
which matches the known checkpoint used by the C++ implementation.
The C++, Python, and Java implementations use the final cumulative formula directly. They iterate over every admissible \(k\) with \(3k\le N\), compute the remaining translation budget \(N-3k+1\), and add
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
to the running total.
The C++ implementation also evaluates the single-\(n\) formula on small checkpoints such as \(H(3)=1\), \(H(6)=12\), and \(H(20)=966\) before printing the final cumulative answer. The arithmetic uses sufficiently wide integer types because the intermediate cubic products are larger than a signed 64-bit multiplication can safely handle in C++.
The loop runs once for each integer \(k\) with \(1\le k\le \lfloor N/3\rfloor\). Hence the running time is \(O(N)\) and the extra memory usage is \(O(1)\). The method is efficient because all geometric complexity has been collapsed into a single summation parameter.
Sei \(H(n)\) die Anzahl regulärer Hexagone, deren sechs Ecken auf Gitterpunkten innerhalb eines dreieckigen Gitters der Größe \(n\) liegen. In axialen Koordinaten ist dieses Gebiet
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}.$$
Gesucht ist nicht nur ein einzelnes \(H(n)\), sondern die Gesamtsumme
$$S(N)=\sum_{n=3}^{N} H(n).$$
Direktes geometrisches Durchprobieren wäre viel zu langsam, daher wird die Aufgabe auf eine eindimensionale Summation zurückgeführt.
Der entscheidende Punkt ist, dass jedes reguläre Gitter-Hexagon durch einen Seitenvektor und dessen \(60^\circ\)-Drehung beschrieben werden kann und dass die Randbedingungen nur von einem einfachen ganzzahligen Parameter abhängen.
Wähle einen von null verschiedenen Seitenvektor
$$u=(a,b).$$
In axialen Koordinaten wird dieser Vektor durch eine Drehung um \(60^\circ\) zu
$$v=(-b,a+b).$$
Ist \(P\) ein Eckpunkt des Hexagons, dann lauten die sechs Ecken
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u.$$
Damit ist bereits ein reguläres Hexagon auf dem Dreiecksgitter festgelegt: aufeinanderfolgende Kanten entstehen durch wiederholte \(60^\circ\)-Drehungen, also sind alle Seiten gleich lang und alle Innenwinkel gleich \(120^\circ\).
Dasselbe Hexagon kann über mehrere Seiten beschrieben werden. Deshalb beschränken wir uns auf den Sektor
$$a>0,\qquad b\ge 0.$$
Unter den sechs Seitenrichtungen eines regulären Hexagons liegt genau eine in diesem Sektor, also verschwindet damit die Mehrfachzählung.
Nun definieren wir
$$k=a+b.$$
Für festes \(k\) sind die zulässigen kanonischen Paare
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0), $$
also genau \(k\) Stück. Verschiedene Paare können unterschiedliche Gitterformen beschreiben, verbrauchen am Rand aber denselben Platz, und genau das steuert die Zählung.
Schreibe den Basispunkt als \(P=(x,y)\). Alle sechs Ecken müssen in \(T_n\) bleiben, also muss für jede Ecke gelten
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n.$$
Die stärkste untere Schranke für die \(x\)-Koordinate kommt von \(P+2v-u\), dessen erste Koordinate
$$x-a-2b$$
ist. Daher braucht man
$$x\ge a+2b.$$
Die stärkste obere Schranke für \(x+y\) kommt von \(P+u+v\), denn dort ist die Koordinatensumme
$$x+y+2a+b,$$
also muss gelten
$$x+y\le n-2a-b.$$
Die übrigen Ungleichungen sind dann automatisch schwächer. Setze
$$x'=x-(a+2b).$$
Dann werden die Bedingungen zu
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k.$$
Das ist wieder ein Dreiecksgebiet, diesmal der Größe \(n-3k\). Folglich ist die Zahl der gültigen Verschiebungen für ein festes kanonisches Paar mit Parameter \(k\)
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2},$$
sofern \(3k\le n\); andernfalls ist sie \(0\).
Da es genau \(k\) kanonische Paare mit \(a+b=k\) gibt, folgt
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}.$$
Damit ist ein einzelnes \(H(n)\) bereits in \(O(n)\) berechenbar.
Für die kumulative Summe vertauschen wir die Reihenfolge der Summation:
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$$
Mit
$$t=n-3k+1,\qquad M=N-3k+1$$
wird die innere Summe zu
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}.$$
Damit erhält man die geschlossene Formel, die im Programm verwendet wird:
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
Hier ist \(\lfloor 6/3\rfloor=2\), also tragen nur \(k=1\) und \(k=2\) bei.
Für \(k=1\) erhält man
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$$
Für \(k=2\) erhält man
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$$
Also
$$H(6)=10+2=12,$$
genau der bekannte Kontrollwert aus der C++-Implementierung.
Die C++-, Python- und Java-Implementierungen benutzen direkt die geschlossene Summenformel für \(S(N)\). Sie laufen über alle zulässigen \(k\) mit \(3k\le N\), berechnen den verbleibenden Translationsspielraum \(N-3k+1\) und addieren
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
zur laufenden Summe.
Die C++-Implementierung wertet zusätzlich die Einzelwertformel an kleinen Kontrollpunkten wie \(H(3)=1\), \(H(6)=12\) und \(H(20)=966\) aus, bevor das kumulative Ergebnis ausgegeben wird. Verwendet werden ausreichend breite Ganzzahltypen, weil die kubischen Zwischenprodukte in C++ nicht sicher in einer vorzeichenbehafteten 64-Bit-Multiplikation liegen.
Die Schleife läuft einmal für jedes ganze \(k\) mit \(1\le k\le \lfloor N/3\rfloor\). Daher beträgt die Laufzeit \(O(N)\) und der zusätzliche Speicherbedarf \(O(1)\). Das Verfahren ist effizient, weil die gesamte Geometrie auf einen einzigen Summationsparameter reduziert wurde.
\(H(n)\), boyutu \(n\) olan üçgensel kafes bölgesi içinde, altı köşesi de kafes noktalarında bulunan düzgün altıgenlerin sayısı olsun. Eksenel koordinatlarla bu bölge
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}$$
şeklinde yazılır. İstenen şey tek bir \(H(n)\) değil, kümülatif toplamdır:
$$S(N)=\sum_{n=3}^{N} H(n).$$
Doğrudan geometrik tarama çok pahalı olacağı için çözüm, sayımı tek parametreli bir toplama dönüştürür.
Ana fikir şudur: kafes üzerindeki her düzgün altıgen bir kenar vektörü ve onun \(60^\circ\) döndürülmüş hali ile tanımlanabilir; sınır koşulları da yalnızca basit bir tamsayı parametresine bağlıdır.
Sıfır olmayan bir kenar vektörü seçelim:
$$u=(a,b).$$
Eksenel koordinatlarda bu vektörün \(60^\circ\) döndürülmüş hali
$$v=(-b,a+b)$$
olur. Eğer \(P\) altıgenin bir köşesiyse altı köşe
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u$$
şeklindedir. Art arda gelen kenarlar hep \(60^\circ\) döndürmeyle üretildiği için bütün kenarlar eşit uzunluktadır ve iç açılar \(120^\circ\) olur; yani gerçekten düzgün bir altıgendir.
Aynı altıgen birden fazla kenar üzerinden tanımlanabileceği için şu kanonik sektörü seçiyoruz:
$$a>0,\qquad b\ge 0.$$
Düzgün bir altıgenin altı kenar yönü içinde tam olarak biri bu sektöre düşer; böylece çift sayım ortadan kalkar.
Şimdi
$$k=a+b$$
parametresini tanımlayalım. Sabit bir \(k\) için mümkün kanonik çiftler
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0) $$
olduğundan tam \(k\) tane vardır. Bu çiftler farklı kafes biçimlerine karşılık gelebilir, ancak büyük üçgenin sınırlarından tükettikleri alan aynıdır; sayımı belirleyen de budur.
Başlangıç köşesini \(P=(x,y)\) yazalım. Tüm köşeler \(T_n\) içinde kalmalıdır; yani her köşe için
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n$$
olmalıdır.
\(x\) için en güçlü alt sınır, birinci koordinatı
$$x-a-2b$$
olan \(P+2v-u\) köşesinden gelir. Bu yüzden
$$x\ge a+2b$$
gereklidir.
\(x+y\) için en güçlü üst sınır ise toplamı
$$x+y+2a+b$$
olan \(P+u+v\) köşesinden gelir. Dolayısıyla
$$x+y\le n-2a-b$$
olmalıdır.
Bu koşullar sağlandığında öteki eşitsizlikler daha zayıf kalır. Şimdi
$$x'=x-(a+2b)$$
kaydırmasını yaparsak şartlar
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k$$
biçimine gelir. Bu da boyutu \(n-3k\) olan başka bir üçgensel kafes bölgesidir. Böylece sabit bir kanonik çift için yerleştirme sayısı
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2}$$
olur; tabii yalnızca \(3k\le n\) ise, aksi halde \(0\).
\(a+b=k\) koşulunu sağlayan tam \(k\) kanonik çift olduğu için
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}$$
elde edilir. Bu, tek bir \(H(n)\) değeri için zaten \(O(n)\) zamanlı bir formüldür.
Kümülatif toplam için toplamların yerini değiştiririz:
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$$
Şimdi
$$t=n-3k+1,\qquad M=N-3k+1$$
olsun. İç toplam
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}$$
olur. Böylece uygulamanın doğrudan kullandığı kapalı form
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
Burada \(\lfloor 6/3\rfloor=2\), yani yalnızca \(k=1\) ve \(k=2\) katkı verir.
\(k=1\) için
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$$
\(k=2\) için
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$$
Dolayısıyla
$$H(6)=10+2=12,$$
ki bu da C++ uygulamasındaki bilinen kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları doğrudan \(S(N)\) için elde edilen son kapalı formülü kullanır. \(3k\le N\) koşulunu sağlayan her \(k\) üzerinde dolaşılır, geriye kalan kaydırma payı \(N-3k+1\) olarak hesaplanır ve
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
terimi toplam cevaba eklenir.
C++ uygulaması son çıktıyı üretmeden önce tek-\(n\) formülünü \(H(3)=1\), \(H(6)=12\) ve \(H(20)=966\) gibi küçük kontrol noktalarında da dener. Ara çarpımlar kübik büyüdüğü için C++ tarafında 64 bit işaretli çarpım sınırını aşmayan kadar geniş tamsayı aritmetiği kullanılır.
Döngü, \(1\le k\le \lfloor N/3\rfloor\) aralığındaki her tamsayı için bir kez çalışır. Bu yüzden zaman karmaşıklığı \(O(N)\), ek bellek kullanımı \(O(1)\)'dir. Yöntem verimlidir; çünkü bütün geometrik ayrıntılar tek bir toplama parametresine indirgenmiştir.
Sea \(H(n)\) el número de hexágonos regulares cuyas seis esquinas están en puntos de la red dentro de la región triangular de tamaño \(n\). En coordenadas axiales, dicha región es
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}.$$
No basta con calcular un solo valor \(H(n)\); el objetivo es obtener la suma acumulada
$$S(N)=\sum_{n=3}^{N} H(n).$$
Una búsqueda geométrica directa sería demasiado costosa, así que la solución reduce todo a una suma con un único parámetro.
La observación central es que todo hexágono regular de la red queda determinado por un vector de lado y su rotación de \(60^\circ\), y que las restricciones del borde solo dependen de un parámetro entero muy simple.
Elegimos un vector de lado no nulo
$$u=(a,b).$$
En coordenadas axiales, la rotación de \(60^\circ\) de este vector es
$$v=(-b,a+b).$$
Si \(P\) es un vértice del hexágono, entonces los seis vértices son
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u.$$
Eso ya define un hexágono regular de la red: los lados consecutivos se obtienen por giros sucesivos de \(60^\circ\), así que todas las aristas tienen la misma longitud y todos los ángulos interiores miden \(120^\circ\).
El mismo hexágono puede describirse desde varios lados, por lo que restringimos la búsqueda al sector
$$a>0,\qquad b\ge 0.$$
Entre las seis direcciones de un hexágono regular, exactamente una cae en ese sector, de modo que así eliminamos el doble conteo.
Definimos ahora
$$k=a+b.$$
Para un \(k\) fijo, los pares canónicos posibles son
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0), $$
es decir, exactamente \(k\) pares. Distintos pares pueden producir distintas formas dentro de la red, pero todos consumen la misma cantidad de espacio respecto del borde, y ese es el dato relevante para contar.
Escribimos el vértice base como \(P=(x,y)\). Los seis vértices deben permanecer en \(T_n\), lo que exige
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n$$
para cada vértice listado.
La cota inferior más fuerte sobre \(x\) proviene de \(P+2v-u\), cuya primera coordenada es
$$x-a-2b,$$
de modo que necesitamos
$$x\ge a+2b.$$
La cota superior más fuerte sobre \(x+y\) proviene de \(P+u+v\), cuya suma de coordenadas es
$$x+y+2a+b,$$
y por tanto hace falta
$$x+y\le n-2a-b.$$
Las demás desigualdades resultan más débiles una vez que estas se cumplen. Si definimos
$$x'=x-(a+2b),$$
las condiciones se convierten en
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k.$$
Eso vuelve a ser una región triangular, ahora de tamaño \(n-3k\). Por lo tanto, el número de traslaciones válidas para un par canónico fijo con parámetro \(k\) es
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2},$$
siempre que \(3k\le n\), y \(0\) en caso contrario.
Como hay exactamente \(k\) pares canónicos con \(a+b=k\), obtenemos
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}.$$
Eso ya da una fórmula \(O(n)\) para un único valor \(H(n)\).
Para la suma acumulada, intercambiamos el orden de sumación:
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$$
Tomando
$$t=n-3k+1,\qquad M=N-3k+1,$$
la suma interior queda
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}.$$
Así llegamos a la fórmula cerrada que utiliza la implementación:
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
Aquí \(\lfloor 6/3\rfloor=2\), así que solo contribuyen \(k=1\) y \(k=2\).
Para \(k=1\):
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$$
Para \(k=2\):
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$$
Por tanto,
$$H(6)=10+2=12,$$
lo que coincide con el punto de control conocido de la implementación en C++.
Las implementaciones en C++, Python y Java aplican directamente la fórmula final para \(S(N)\). Recorren todos los valores admisibles de \(k\) con \(3k\le N\), calculan el margen restante \(N-3k+1\) y suman
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
al acumulador.
La implementación en C++ también evalúa la fórmula de un solo \(n\) en puntos pequeños como \(H(3)=1\), \(H(6)=12\) y \(H(20)=966\) antes de imprimir la respuesta acumulada. La aritmética necesita tipos lo bastante amplios porque los productos cúbicos intermedios superan lo que una multiplicación entera con signo de 64 bits puede manejar con seguridad en C++.
El bucle se ejecuta una vez por cada entero \(k\) con \(1\le k\le \lfloor N/3\rfloor\). Por ello, el tiempo total es \(O(N)\) y la memoria adicional es \(O(1)\). El método es eficiente porque toda la parte geométrica se ha condensado en un único parámetro de sumación.
设 \(H(n)\) 表示大小为 \(n\) 的三角晶格区域内、六个顶点都落在晶格点上的正六边形数量。用轴坐标表示，这个区域是
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}$$
题目并不是只要求某个单独的 \(H(n)\)，而是要求累计总和
$$S(N)=\sum_{n=3}^{N} H(n)$$
如果直接做几何枚举，代价会非常高；解法的核心是把几何约束压缩成一个单参数求和问题。
关键观察是：三角晶格上的每一个正六边形都可以由一条边向量以及它的 \(60^\circ\) 旋转来描述，而所有边界限制最终只依赖于一个很简单的整数参数。
取一个非零的晶格边向量
$$u=(a,b)$$
在轴坐标下，把它旋转 \(60^\circ\) 后得到
$$v=(-b,a+b)$$
如果 \(P\) 是六边形的一个顶点，那么六个顶点依次就是
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u$$
这已经唯一确定了一个晶格正六边形：相邻边是通过连续的 \(60^\circ\) 旋转得到的，所以六条边长度相等，内角全部都是 \(120^\circ\)。
同一个六边形可以从不同边开始描述，所以要先消除重复计数。做法是只保留处在下面扇区中的边向量：
$$a>0,\qquad b\ge 0$$
对于一个正六边形的六个边方向，恰好只有一个会落在这个扇区里，因此每个六边形只会被记一次。
接着定义参数
$$k=a+b$$
当 \(k\) 固定时，所有满足条件的规范向量恰好是
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0) $$
这 \(k\) 个。它们在欧几里得意义下可以对应不同的晶格形状，但它们对大三角边界“消耗”的空间是一样的，而计数只取决于这一点。
把基准顶点记作 \(P=(x,y)\)。为了让六个顶点都留在 \(T_n\) 中，所有顶点都必须满足
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n$$
对 \(x\) 的最强下界来自顶点 \(P+2v-u\)，它的第一坐标是
$$x-a-2b,$$
因此必须有
$$x\ge a+2b$$
对 \(x+y\) 的最强上界来自顶点 \(P+u+v\)，它的坐标和是
$$x+y+2a+b,$$
因此还必须满足
$$x+y\le n-2a-b$$
在这两个条件满足之后，其余几个顶点给出的不等式都会更宽松。现在做一个平移变量替换：
$$x'=x-(a+2b)$$
于是条件变成
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k$$
这又是一个大小为 \(n-3k\) 的三角晶格区域。因此，对一个固定的规范向量，其可放置位置数为
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2}$$
前提是 \(3k\le n\)；如果 \(3k>n\)，那么答案就是 \(0\)。
由于满足 \(a+b=k\) 的规范向量一共有 \(k\) 个，于是得到
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}$$
这已经给出了单个 \(H(n)\) 的 \(O(n)\) 计算公式。
接下来对累计和交换求和顺序：
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}$$
令
$$t=n-3k+1,\qquad M=N-3k+1$$
则内层求和变成
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}$$
于是实现中直接使用的最终闭式就是
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
此时 \(\lfloor 6/3\rfloor=2\)，所以只有 \(k=1\) 和 \(k=2\) 有贡献。
当 \(k=1\) 时：
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10$$
当 \(k=2\) 时：
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2$$
因此
$$H(6)=10+2=12$$
这和 C++ 实现中使用的已知校验值一致。
C++、Python 和 Java 三个实现都直接套用了 \(S(N)\) 的最终公式。它们遍历所有满足 \(3k\le N\) 的参数 \(k\)，计算剩余的平移余量 \(N-3k+1\)，再把
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
加入累计答案。
C++ 实现还会在输出最终累计结果前，用单个 \(H(n)\) 的公式检查若干小样例，例如 \(H(3)=1\)、\(H(6)=12\) 和 \(H(20)=966\)。由于中间会出现三次乘法，C++ 端必须使用足够宽的整数类型，避免在有符号 64 位乘法范围内发生溢出。
循环只会对每个满足 \(1\le k\le \lfloor N/3\rfloor\) 的整数执行一次，因此总时间复杂度为 \(O(N)\)，额外空间复杂度为 \(O(1)\)。之所以高效，是因为原本的几何问题已经被压缩成一个单参数求和。
Пусть \(H(n)\) обозначает число правильных шестиугольников, все шесть вершин которых лежат в узлах решетки внутри треугольной области размера \(n\). В аксиальных координатах эта область задается так:
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}.$$
Нужно найти не только отдельное значение \(H(n)\), но и суммарную величину
$$S(N)=\sum_{n=3}^{N} H(n).$$
Прямой геометрический перебор слишком дорог, поэтому решение сводит задачу к сумме по одному параметру.
Главное наблюдение состоит в том, что любой правильный шестиугольник на треугольной решетке задается одним вектором стороны и его поворотом на \(60^\circ\), а все ограничения от границы зависят только от одного простого целого параметра.
Выберем ненулевой вектор стороны
$$u=(a,b).$$
В аксиальных координатах его поворот на \(60^\circ\) равен
$$v=(-b,a+b).$$
Если \(P\) - одна из вершин шестиугольника, то шесть вершин имеют вид
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u.$$
Это действительно правильный шестиугольник: последовательные стороны получаются повторным поворотом на \(60^\circ\), поэтому все стороны равны, а внутренние углы равны \(120^\circ\).
Один и тот же шестиугольник можно описать через разные стороны, поэтому нужно убрать повторный подсчет. Для этого оставляем только сектор
$$a>0,\qquad b\ge 0.$$
Среди шести направлений сторон правильного шестиугольника ровно одно попадает в этот сектор, так что каждый шестиугольник учитывается ровно один раз.
Теперь введем параметр
$$k=a+b.$$
При фиксированном \(k\) все допустимые канонические пары имеют вид
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0), $$
и таких пар ровно \(k\). Они могут задавать разные формы в решетке, но одинаково расходуют место у границы, а именно это и определяет число размещений.
Пусть базовая вершина равна \(P=(x,y)\). Все шесть вершин должны оставаться в \(T_n\), то есть для каждой из них нужно
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n.$$
Самая сильная нижняя граница на \(x\) приходит от вершины \(P+2v-u\), у которой первая координата равна
$$x-a-2b.$$
Следовательно, необходимо
$$x\ge a+2b.$$
Самая сильная верхняя граница на \(x+y\) приходит от вершины \(P+u+v\), у которой сумма координат равна
$$x+y+2a+b,$$
поэтому нужно
$$x+y\le n-2a-b.$$
Когда эти условия выполнены, остальные неравенства оказываются слабее. Сделаем сдвиг
$$x'=x-(a+2b).$$
Тогда ограничения принимают вид
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k.$$
Это снова треугольная область, теперь размера \(n-3k\). Значит, число допустимых размещений для одной фиксированной канонической пары с параметром \(k\) равно
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2},$$
если \(3k\le n\), и равно \(0\) в противном случае.
Так как при условии \(a+b=k\) существует ровно \(k\) канонических пар, получаем
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}.$$
Это уже дает \(O(n)\)-формулу для одного значения \(H(n)\).
Для накопленной суммы меняем порядок суммирования:
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$$
Положим
$$t=n-3k+1,\qquad M=N-3k+1.$$
Тогда внутренняя сумма равна
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}.$$
Отсюда получаем итоговую формулу, которая и используется в программе:
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
Здесь \(\lfloor 6/3\rfloor=2\), так что ненулевой вклад дают только \(k=1\) и \(k=2\).
Для \(k=1\):
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$$
Для \(k=2\):
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$$
Следовательно,
$$H(6)=10+2=12,$$
что совпадает с известным контрольным значением из C++-реализации.
Реализации на C++, Python и Java напрямую используют окончательную формулу для \(S(N)\). Они перебирают все допустимые значения \(k\), для которых \(3k\le N\), вычисляют оставшийся запас для сдвигов \(N-3k+1\) и добавляют
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
к накопленной сумме.
C++-реализация дополнительно проверяет формулу для одного \(n\) на малых контрольных точках \(H(3)=1\), \(H(6)=12\) и \(H(20)=966\), а затем печатает итоговый накопленный ответ. Для арифметики нужны достаточно широкие целые типы, поскольку промежуточные кубические произведения в C++ выходят за безопасный диапазон обычного знакового 64-битного умножения.
Цикл выполняется один раз для каждого целого \(k\) из диапазона \(1\le k\le \lfloor N/3\rfloor\). Поэтому время работы равно \(O(N)\), а дополнительная память - \(O(1)\). Метод эффективен именно потому, что вся геометрия сведена к одному параметру суммирования.
ليكن \(H(n)\) عدد السداسيات المنتظمة التي تقع رؤوسها الستة على نقاط شبكة داخل المنطقة المثلثية ذات الحجم \(n\). في الإحداثيات المحورية تكتب هذه المنطقة على الصورة
$$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}.$$
المطلوب ليس حساب قيمة واحدة فقط، بل إيجاد المجموع التراكمي
$$S(N)=\sum_{n=3}^{N} H(n).$$
والتعداد الهندسي المباشر بطيء جدًا، لذلك يحول الحل المسألة إلى مجموع يعتمد على معامل واحد فقط.
الفكرة المحورية هي أن كل سداسي منتظم على الشبكة المثلثية يمكن وصفه بمتجه ضلع واحد ومعه دورانه بمقدار \(60^\circ\)، وأن قيود الحدود تعتمد في النهاية على معامل صحيح بسيط.
نختار متجه ضلع غير صفري
$$u=(a,b).$$
وفي الإحداثيات المحورية فإن دورانه بمقدار \(60^\circ\) هو
$$v=(-b,a+b).$$
إذا كانت \(P\) إحدى رؤوس السداسي، فإن الرؤوس الستة هي
$$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u.$$
وهذا يحدد سداسيًا منتظمًا فعلًا: فالأضلاع المتتالية تنتج من تكرار دوران \(60^\circ\)، لذا تكون جميع الأضلاع متساوية وجميع الزوايا الداخلية \(120^\circ\).
يمكن وصف السداسي نفسه انطلاقًا من أكثر من ضلع، لذلك نلغي التكرار بحصر المتجهات في القطاع
$$a>0,\qquad b\ge 0.$$
ومن بين الاتجاهات الستة لأضلاع أي سداسي منتظم يوجد اتجاه واحد فقط يقع في هذا القطاع، ولذلك يحسب كل سداسي مرة واحدة بالضبط.
بعد ذلك نعرف المعامل
$$k=a+b.$$
وعند تثبيت \(k\) تكون الأزواج القانونية الممكنة هي
$$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0) $$
وعددها يساوي بالضبط \(k\). وقد تعطي هذه الأزواج أشكالًا مختلفة داخل الشبكة، لكنها تستهلك المقدار نفسه من الحيز بالنسبة إلى حدود المثلث الكبير، وهذا هو ما يتحكم في العدّ.
لنكتب الرأس الأساسي على الصورة \(P=(x,y)\). يجب أن تبقى الرؤوس الستة كلها داخل \(T_n\)، أي يجب أن يتحقق لكل رأس
$$x\ge 0,\qquad y\ge 0,\qquad x+y\le n.$$
أقوى حد سفلي على \(x\) يأتي من الرأس \(P+2v-u\)، إذ إن إحداثيه الأول هو
$$x-a-2b,$$
ومن ثم يجب أن يكون
$$x\ge a+2b.$$
أما أقوى حد علوي على \(x+y\) فيأتي من الرأس \(P+u+v\)، لأن مجموع إحداثييه يساوي
$$x+y+2a+b,$$
ولذلك يلزم
$$x+y\le n-2a-b.$$
إذا تحققت هاتان العلاقتان أصبحت بقية القيود أضعف منهما. الآن نزيح نقطة البداية بتعريف
$$x'=x-(a+2b).$$
فتتحول الشروط إلى
$$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k.$$
وهذه منطقة مثلثية جديدة حجمها \(n-3k\). إذن عدد المواضع الصالحة لزوج قانوني ثابت ذي معامل \(k\) هو
$$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2},$$
بشرط أن يكون \(3k\le n\)، وإلا كان العدد صفرًا.
بما أن عدد الأزواج القانونية التي تحقق \(a+b=k\) يساوي \(k\)، نحصل على
$$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}.$$
وهذه بالفعل صيغة زمنها \(O(n)\) لحساب قيمة منفردة من \(H(n)\).
أما للمجموع التراكمي فنبدل ترتيب الجمع:
$$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$$
إذا وضعنا
$$t=n-3k+1,\qquad M=N-3k+1,$$
أصبح المجموع الداخلي
$$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}.$$
وعليه فإن الصيغة المغلقة النهائية التي يطبقها التنفيذ مباشرة هي
$$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$$
هنا \(\lfloor 6/3\rfloor=2\)، لذا يسهم فقط \(k=1\) و\(k=2\).
عند \(k=1\):
$$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$$
وعند \(k=2\):
$$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$$
إذًا
$$H(6)=10+2=12,$$
وهو نفس مقدار التحقق المعروف في تنفيذ C++.
تعتمد تطبيقات C++ وPython وJava مباشرة على الصيغة النهائية الخاصة بـ \(S(N)\). فهي تمر على كل قيمة مسموحة لـ \(k\) تحقق \(3k\le N\)، ثم تحسب هامش الإزاحة المتبقي \(N-3k+1\)، وتضيف
$$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$$
إلى المجموع الجاري.
كما أن تنفيذ C++ يفحص صيغة القيمة المنفردة عند نقاط صغيرة مثل \(H(3)=1\) و\(H(6)=12\) و\(H(20)=966\) قبل طباعة الجواب التراكمي النهائي. وتحتاج الحسابات إلى أنواع عددية عريضة بما يكفي، لأن الحدود التكعيبية الوسيطة تتجاوز في C++ ما يمكن ضربه بأمان داخل عدد صحيح موقّع من 64 بت.
تنفذ الحلقة مرة واحدة لكل عدد صحيح \(k\) يحقق \(1\le k\le \lfloor N/3\rfloor\). لذلك يكون الزمن الكلي \(O(N)\) والذاكرة الإضافية \(O(1)\). وكفاءة الطريقة تأتي من أن كل التعقيد الهندسي اختزل إلى معامل جمع واحد.