Let \(C(m,n)\) denote the number of spanning trees of the \(m \times n\) rectangular grid graph. The Project Euler instance asks for the value at \((m,n)=(100,500)\), but the exact integer has more than twenty-five thousand decimal digits, so the implementations return the answer in scientific notation instead of constructing the full integer explicitly.
The local solution files all exploit the same fact: for this particular graph family, the Matrix-Tree theorem converts the counting problem into a product over explicit Laplacian eigenvalues.
For any connected graph \(G\) with Laplacian eigenvalues
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1},$$
Kirchhoff's Matrix-Tree theorem gives the spanning-tree count as
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$$
In our case, the grid graph has \(mn\) vertices, so once the nonzero Laplacian eigenvalues are known, we immediately obtain \(C(m,n)\).
The \(m \times n\) rectangular grid is the Cartesian product of two path graphs, one of length \(m\) and one of length \(n\). For the path graph with \(m\) vertices, the Laplacian eigenvalues are
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
and similarly for the path graph with \(n\) vertices,
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$$
For a Cartesian product, Laplacian eigenvalues add, so the grid eigenvalues are
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$$
The pair \((i,j)=(0,0)\) gives the single zero eigenvalue corresponding to the constant vector. Every other pair gives a positive eigenvalue because the grid graph is connected.
Substituting the grid eigenvalues into Kirchhoff's formula yields
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$$
This is the exact formula implemented by all three solution files. The main difficulty is no longer graph theory but numerical scale: the product contains \(mn-1\) positive factors and becomes astronomically large even for moderate \(m\) and \(n\).
Instead of multiplying the eigenvalues directly, the programs sum their base-10 logarithms:
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$$
Once \(L\) is known, write
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$$
where \(1 \le \mu \lt 10\). The code rounds \(\mu\) to five significant digits. If rounding pushes the mantissa to \(10.0000\), it divides by \(10\) and increments the exponent, exactly as the local implementations do.
The C++ version uses Kahan summation for the logarithm sum, which is a small but worthwhile refinement when tens of thousands of floating-point terms are added. The Python and Java versions use the same formula without that extra compensation step.
The C++ file contains several checkpoints that are useful both mathematically and as implementation tests.
For \(m=n=1\), there is only one vertex and therefore exactly one spanning tree, so \(C(1,1)=1\).
For \(m=n=2\), the nonzero eigenvalues are \(2\), \(2\), and \(4\), hence
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
The next exact checkpoint used in code is
$$C(3,4)=2415,$$
and symmetry of the rectangular grid requires \(C(3,4)=C(4,3)\), which the C++ program checks numerically.
For a larger validation point, the code formats
$$C(9,12)\approx 2.5720 \times 10^{46},$$
and for the actual Project Euler target it prints
$$C(100,500)\approx 6.3202 \times 10^{25093}.$$
The C++ solution exposes optional arguments --m=, --n=, and --skip-checkpoints. It precomputes two cosine tables, loops over all \((i,j)\ne(0,0)\), forms the eigenvalue \(4-2c_i-2c_j\), accumulates \(\log_{10}\) with Kahan compensation, subtracts \(\log_{10}(mn)\), and finally reconstructs the scientific notation string. The Python solution follows the same mathematical pipeline and also caches cosine tables, but keeps the code minimal and does not include checkpoints. The Java solution uses the same formula and the same scientific-format rounding rule, but computes the cosine values directly inside the loops instead of storing arrays.
The dominant work is the double loop over the \(mn-1\) nonzero eigenvalue positions, so the running time is \(O(mn)\). The C++ and Python versions store cosine tables of lengths \(m\) and \(n\), so they use \(O(m+n)\) extra memory. The Java translation recomputes cosines and therefore only needs \(O(1)\) extra memory beyond a few scalars. In every version, this is vastly cheaper than forming a giant determinant or performing exact big-integer linear algebra.
Sei \(C(m,n)\) die Anzahl der Spannbäume des rechteckigen \(m \times n\)-Gittergraphen. Für die Project-Euler-Instanz \((m,n)=(100,500)\) ist die exakte Zahl so groß, dass die Implementierungen sie nicht als vollständige Ganzzahl ausgeben, sondern in wissenschaftlicher Schreibweise darstellen.
Alle lokalen Lösungsdateien nutzen dieselbe mathematische Idee: Das Matrix-Baum-Theorem reduziert das Problem auf ein Produkt explizit bekannter Laplace-Eigenwerte des Gitters.
Für einen zusammenhängenden Graphen \(G\) mit Laplace-Eigenwerten
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1}$$
liefert Kirchhoffs Matrix-Baum-Theorem
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$$
Der rechteckige Gittergraph besitzt \(mn\) Knoten. Kennt man also alle von Null verschiedenen Eigenwerte seiner Laplace-Matrix, erhält man \(C(m,n)\) unmittelbar.
Das \(m \times n\)-Gitter ist das kartesische Produkt zweier Pfadgraphen. Für den Pfadgraphen mit \(m\) Knoten lauten die Laplace-Eigenwerte
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
und für den Pfadgraphen mit \(n\) Knoten entsprechend
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$$
Beim kartesischen Produkt addieren sich die Laplace-Eigenwerte, also
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$$
Nur \((i,j)=(0,0)\) liefert den Null-Eigenwert; alle anderen Paare liefern positive Werte, weil der Gittergraph zusammenhängend ist.
Einsetzen in Kirchhoffs Formel ergibt
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$$
Genau diese Formel wird in allen drei Lösungsdateien ausgewertet. Das kombinatorische Problem ist damit gelöst; übrig bleibt die numerische Herausforderung eines Produkts mit \(mn-1\) positiven Faktoren.
Direktes Multiplizieren würde sofort zu riesigen Zahlen führen. Deshalb berechnen die Programme
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$$
Ist \(L\) bekannt, dann gilt
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$$
wobei \(1 \le \mu \lt 10\). Die Mantisse \(\mu\) wird auf fünf signifikante Stellen gerundet. Falls daraus \(10.0000\) würde, teilen die Programme durch \(10\) und erhöhen den Exponenten um eins.
Die C++-Version verwendet zusätzlich Kahan-Summation, um den Rundungsfehler bei der Summe vieler Logarithmen klein zu halten. Python und Java benutzen dieselbe Formel ohne diesen Zusatzschritt.
Die C++-Datei enthält mehrere Kontrollpunkte, die sowohl mathematisch sinnvoll als auch praktisch zum Testen sind.
Für \(m=n=1\) gibt es nur einen Knoten, also genau einen Spannbaum: \(C(1,1)=1\).
Für \(m=n=2\) sind die nichtnull Eigenwerte \(2\), \(2\) und \(4\). Daher
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
Ein weiterer exakter Prüfwert ist
$$C(3,4)=2415,$$
und wegen der Symmetrie des Rechtecks muss auch \(C(4,3)=2415\) gelten.
Für einen größeren numerischen Test liefert die Formatierung
$$C(9,12)\approx 2.5720 \times 10^{46},$$
und für die eigentliche Zielinstanz gibt das Programm aus
$$C(100,500)\approx 6.3202 \times 10^{25093}.$$
Die C++-Lösung akzeptiert optional --m=, --n= und --skip-checkpoints. Sie berechnet zwei Kosinustabellen vor, iteriert über alle \((i,j)\ne(0,0)\), bildet den Eigenwert \(4-2c_i-2c_j\), summiert dessen \(\log_{10}\) per Kahan-Kompensation, subtrahiert \(\log_{10}(mn)\) und rekonstruiert anschließend die wissenschaftliche Schreibweise. Die Python-Version folgt demselben Schema und speichert ebenfalls Kosinuswerte vor, bleibt aber bewusst kurz und enthält keine Checkpoints. Die Java-Version verwendet dieselbe Formel und dieselbe Rundungslogik für die Ausgabe, berechnet die Kosinuswerte jedoch direkt in den Schleifen statt sie in Arrays zu speichern.
Die Hauptarbeit ist die Doppelschleife über \(mn-1\) nichtnull Eigenwerte, also beträgt die Laufzeit \(O(mn)\). C++ und Python benötigen \(O(m+n)\) Zusatzspeicher für die Kosinustabellen. Java berechnet die Kosinuswerte bei Bedarf neu und kommt daher mit \(O(1)\) Zusatzspeicher aus. In allen Fällen ist dieser Ansatz deutlich günstiger als eine riesige Determinante oder exakte Big-Integer-Lineare Algebra.
\(C(m,n)\), \(m \times n\) dikdörtgen ızgara grafının kapsayan ağaç sayısı olsun. Project Euler örneğinde \((m,n)=(100,500)\) istenir; fakat tam sayı değeri on binlerce basamaklı olduğu için yerel çözümler sonucu tam sayı olarak değil, bilimsel gösterimde üretir.
Üç çözüm dosyasının ortak noktası aynıdır: Matrix-Tree teoremi sayesinde problem, Laplasyen matrisin açık biçimde yazılabilen özdeğerlerinin çarpımına indirgenir.
Bağlantılı bir \(G\) grafının Laplasyen özdeğerleri
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1}$$
ise Kirchhoff'un Matrix-Tree teoremi
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k$$
sonucunu verir. Bizim dikdörtgen ızgara grafımızda düğüm sayısı \(mn\) olduğundan, sıfır dışındaki Laplasyen özdeğerlerini bulmak doğrudan \(C(m,n)\)'yi verir.
\(m \times n\) ızgarası, iki yol grafının Kartezyen çarpımıdır. \(m\) düğümlü yol grafı için Laplasyen özdeğerleri
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
\(n\) düğümlü yol grafı için de
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1$$
şeklindedir. Kartezyen çarpımda Laplasyen özdeğerleri toplandığı için ızgara grafında
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}$$
elde edilir. \((i,j)=(0,0)\) tek sıfır özdeğeri verir; diğer tüm çiftler pozitiftir çünkü grafik bağlantılıdır.
Bu özdeğerleri Kirchhoff formülüne koyunca
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)}$$
elde edilir. Üç çözüm dosyası da tam olarak bu formülü kullanır. Dolayısıyla asıl zorluk artık kombinatorik değil, \(mn-1\) pozitif terimli dev bir çarpımı sayısal olarak güvenli biçimde toplamaktır.
Doğrudan çarpma yapmak taşmaya ve büyük hassasiyet kaybına yol açar. Bu nedenle programlar
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn)$$
değerini hesaplar. Sonra
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e$$
yazılır; burada \(1 \le \mu \lt 10\). Kod, \(\mu\)'yu beş anlamlı basamağa yuvarlar. Eğer yuvarlama sonucu \(10.0000\) çıkarsa mantisayı \(10\)'a böler ve üssü bir artırır; çözüm dosyalarındaki mantık tam olarak budur.
C++ sürümü, çok sayıda logaritma toplandığında kayan nokta hatasını azaltmak için Kahan toplamı kullanır. Python ve Java sürümleri aynı matematiksel formülü daha sade bir doğrudan toplamla uygular.
C++ dosyasındaki kontrol noktaları hem teoriyi hem de implementasyonu doğrular.
\(m=n=1\) için yalnızca tek bir düğüm vardır; bu yüzden \(C(1,1)=1\).
\(m=n=2\) için sıfır dışı özdeğerler \(2\), \(2\) ve \(4\) olur. Dolayısıyla
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
Koddaki bir sonraki tam kontrol değeri
$$C(3,4)=2415$$
olup simetri gereği \(C(4,3)\) ile aynıdır.
Daha büyük bir sayısal doğrulama için program
$$C(9,12)\approx 2.5720 \times 10^{46}$$
değerini üretir. Asıl hedef örnek için çıktı
$$C(100,500)\approx 6.3202 \times 10^{25093}$$
şeklindedir.
C++ çözümü isteğe bağlı --m=, --n= ve --skip-checkpoints argümanlarını kabul eder. İki kosinüs tablosu oluşturur, tüm \((i,j)\ne(0,0)\) çiftlerini gezer, \(4-2c_i-2c_j\) özdeğerini hesaplar, \(\log_{10}\) toplamını Kahan düzeltmesiyle biriktirir, sonra \(\log_{10}(mn)\) çıkarır ve bilimsel gösterim dizesini oluşturur. Python çözümü aynı hattı izler ve kosinüsleri önceden hesaplar, ancak özellikle kısa tutulmuştur ve kontrol testleri içermez. Java çözümü de aynı formülü ve aynı yuvarlama kuralını kullanır; yalnız kosinüsleri dizilerde saklamak yerine döngü içinde doğrudan hesaplar.
Baskın maliyet, \(mn-1\) sıfır dışı özdeğer konumu üzerinde çalışan çift döngüdür; süre karmaşıklığı \(O(mn)\)'dir. C++ ve Python, uzunlukları \(m\) ve \(n\) olan kosinüs tabloları tuttuğu için \(O(m+n)\) ek bellek kullanır. Java sürümü kosinüsleri yeniden hesapladığından yalnızca \(O(1)\) ek belleğe ihtiyaç duyar. Her durumda bu yöntem, dev bir determinantı veya tam duyarlıklı büyük tamsayı lineer cebrini kurmaktan çok daha verimlidir.
Sea \(C(m,n)\) el número de árboles generadores del grafo de rejilla rectangular \(m \times n\). En el caso de Project Euler se pide \((m,n)=(100,500)\), pero el entero exacto tiene más de veinticinco mil cifras, así que las implementaciones locales devuelven la respuesta en notación científica.
Las tres soluciones usan la misma idea central: el teorema Matrix-Tree transforma el conteo de árboles generadores en un producto de autovalores explícitos del laplaciano de la rejilla.
Para cualquier grafo conexo \(G\) con autovalores laplacianos
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1},$$
el teorema de Kirchhoff afirma que
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$$
La rejilla rectangular tiene \(mn\) vértices. Por tanto, si conocemos todos los autovalores no nulos de su laplaciano, obtenemos \(C(m,n)\) de forma inmediata.
La rejilla \(m \times n\) es el producto cartesiano de dos grafos camino. Para el camino con \(m\) vértices, los autovalores del laplaciano son
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
y para el camino con \(n\) vértices,
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$$
En un producto cartesiano, los autovalores laplacianos se suman, de modo que en la rejilla obtenemos
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$$
El único par que produce el autovalor cero es \((i,j)=(0,0)\); todos los demás son positivos porque la rejilla es conexa.
Sustituyendo en la fórmula de Kirchhoff se obtiene
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$$
Esa es exactamente la expresión evaluada por los archivos C++, Python y Java. La teoría combinatoria queda resuelta aquí; lo difícil pasa a ser manejar numéricamente un producto de \(mn-1\) factores positivos.
Multiplicar directamente provocaría números gigantescos y pérdida de estabilidad numérica. Por eso los programas calculan
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$$
Una vez conocido \(L\), se escribe
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$$
con \(1 \le \mu \lt 10\). Después se redondea \(\mu\) a cinco cifras significativas. Si el redondeo produjera \(10.0000\), la mantisa se divide entre \(10\) y el exponente aumenta en una unidad.
La versión en C++ añade suma de Kahan para reducir el error de redondeo acumulado al sumar miles de logaritmos. Las versiones en Python y Java usan la misma fórmula, pero sin esa corrección adicional.
El archivo C++ incorpora varios checkpoints que también sirven para entender la fórmula.
Para \(m=n=1\), el grafo tiene un solo vértice, así que \(C(1,1)=1\).
Para \(m=n=2\), los autovalores no nulos son \(2\), \(2\) y \(4\), luego
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
Otro valor exacto usado por el código es
$$C(3,4)=2415,$$
y por simetría también debe cumplirse \(C(4,3)=2415\).
Para una validación numérica mayor, el programa formatea
$$C(9,12)\approx 2.5720 \times 10^{46},$$
y para la instancia real de Euler imprime
$$C(100,500)\approx 6.3202 \times 10^{25093}.$$
La solución en C++ admite los argumentos opcionales --m=, --n= y --skip-checkpoints. Precarga dos tablas de cosenos, recorre todos los pares \((i,j)\ne(0,0)\), calcula el autovalor \(4-2c_i-2c_j\), acumula \(\log_{10}\) con compensación de Kahan, resta \(\log_{10}(mn)\) y reconstruye la cadena en notación científica. La versión en Python sigue exactamente el mismo flujo matemático y también guarda los cosenos, aunque en una forma más breve y sin pruebas integradas. La versión en Java usa la misma fórmula y la misma lógica de redondeo de la salida, pero recalcula los cosenos dentro de los bucles en vez de almacenarlos en arreglos.
El trabajo dominante es el doble bucle sobre \(mn-1\) posiciones con autovalor no nulo, así que el tiempo es \(O(mn)\). C++ y Python usan \(O(m+n)\) memoria extra por las tablas de cosenos. Java recalcula los cosenos y por eso sólo necesita \(O(1)\) memoria adicional. En cualquier caso, este método es muy superior a formar un determinante gigantesco o a usar álgebra lineal exacta con enteros enormes.
记 \(C(m,n)\) 为 \(m \times n\) 矩形网格图的生成树个数。Project Euler 要求的是 \((m,n)=(100,500)\)，但这个整数本身有两万五千多位，因此本地解法都不直接构造完整整数，而是输出科学计数法。
三份解答代码依赖同一条核心思路：矩阵树定理把“数生成树”转化为“把拉普拉斯矩阵的非零特征值相乘”。对于矩形网格，这些特征值可以显式写出。
设连通图 \(G\) 的拉普拉斯特征值为
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1},$$
则 Kirchhoff 的矩阵树定理给出
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$$
这里网格图共有 \(mn\) 个顶点，所以只要找出全部非零拉普拉斯特征值，就能立刻得到 \(C(m,n)\)。
\(m \times n\) 网格图可以看成两个路径图的笛卡尔积。对有 \(m\) 个顶点的路径图，其拉普拉斯特征值为
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
对有 \(n\) 个顶点的路径图，其特征值为
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$$
笛卡尔积图的拉普拉斯特征值会相加，因此网格图的特征值是
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$$
只有 \((i,j)=(0,0)\) 对应零特征值；其余全部为正，因为网格图是连通的。
代入矩阵树定理可得
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$$
这正是三份本地解法真正计算的公式。图论部分到这里已经结束，剩下的问题只是数值规模太大，因为这个乘积包含 \(mn-1\) 个正因子。
如果直接相乘，很快就会溢出，也难以控制精度。因此程序先求
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$$
得到 \(L\) 后，再写成
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$$
其中 \(1 \le \mu \lt 10\)。代码把 \(\mu\) 保留为 5 位有效数字。如果四舍五入后出现 \(10.0000\)，就把尾数除以 \(10\)，同时把指数加一。
C++ 版本还加入了 Kahan 求和，以减少上万项对数相加时的浮点累计误差。Python 和 Java 版本则采用同样的公式，但实现更直接。
C++ 文件里包含几个非常有用的 checkpoint。
当 \(m=n=1\) 时，图中只有一个顶点，所以 \(C(1,1)=1\)。
当 \(m=n=2\) 时，非零特征值是 \(2\)、\(2\)、\(4\)，于是
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
代码还验证了精确值
$$C(3,4)=2415,$$
并检查对称性 \(C(3,4)=C(4,3)\)。
再大的一个格式化测试点是
$$C(9,12)\approx 2.5720 \times 10^{46},$$
而真正目标实例的输出为
$$C(100,500)\approx 6.3202 \times 10^{25093}.$$
C++ 解法支持可选参数 --m=、--n= 和 --skip-checkpoints。它先预计算两张余弦表，再遍历所有 \((i,j)\ne(0,0)\)，形成特征值 \(4-2c_i-2c_j\)，用 Kahan 补偿求和累计 \(\log_{10}\)，减去 \(\log_{10}(mn)\)，最后重建科学计数法字符串。Python 解法沿用完全相同的数学流程，也缓存了余弦表，只是代码更短且没有内置校验。Java 解法使用相同的公式和相同的输出舍入规则，但它不保存数组，而是在循环中直接调用余弦函数。
主成本来自对 \(mn-1\) 个非零特征值位置的双重循环，因此时间复杂度是 \(O(mn)\)。C++ 和 Python 因为缓存两张余弦表，所以额外空间为 \(O(m+n)\)。Java 版本实时重算余弦，因此额外空间只有 \(O(1)\)。无论哪种写法，都远比直接构造巨大行列式或做大整数精确线性代数更合适。
Обозначим через \(C(m,n)\) число остовных деревьев прямоугольного решетчатого графа \(m \times n\). В задаче Project Euler требуется случай \((m,n)=(100,500)\), но точное целое число имеет более двадцати пяти тысяч десятичных цифр, поэтому локальные решения выводят ответ в научной записи.
Во всех трёх файлах используется одна и та же идея: теорема Кирхгофа сводит подсчёт остовных деревьев к произведению явно выписываемых ненулевых собственных значений лапласиана решётки.
Пусть у связного графа \(G\) лапласиан имеет спектр
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1}.$$
Тогда теорема Matrix-Tree утверждает, что
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$$
У прямоугольной решётки \(mn\) вершин. Значит, задача сводится к нахождению всех ненулевых собственных значений её лапласиана.
Граф \(m \times n\) можно рассматривать как декартово произведение двух путевых графов. Для пути из \(m\) вершин лапласиан имеет собственные значения
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
а для пути из \(n\) вершин
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$$
При декартовом произведении лапласианные собственные значения складываются, поэтому для решётки получаем
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$$
Пара \((i,j)=(0,0)\) даёт единственное нулевое значение, а все остальные положительны, поскольку граф связный.
Подставляя этот спектр в формулу Кирхгофа, получаем
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$$
Именно это выражение вычисляют локальные решения на C++, Python и Java. После этого графовая часть задачи уже закончена; остаётся только аккуратно посчитать огромное произведение из \(mn-1\) положительных множителей.
Прямое перемножение быстро выходит за разумные пределы чисел с плавающей точкой. Поэтому программы суммируют
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$$
Затем число восстанавливается в виде
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$$
где \(1 \le \mu \lt 10\). Мантисса \(\mu\) округляется до пяти значащих цифр. Если после округления возникает \(10.0000\), мантисса делится на \(10\), а показатель увеличивается на единицу.
Версия на C++ дополнительно применяет суммирование Кэхэна, чтобы уменьшить накопление ошибки при сложении большого числа логарифмов. В версиях на Python и Java используется та же формула, но без этой компенсации.
Файл C++ содержит несколько контрольных точек, которые одновременно объясняют математику и проверяют код.
При \(m=n=1\) граф состоит из одной вершины, поэтому \(C(1,1)=1\).
При \(m=n=2\) ненулевые собственные значения равны \(2\), \(2\) и \(4\), значит
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
Следующий точный тест из кода:
$$C(3,4)=2415,$$
и по симметрии прямоугольника должно выполняться \(C(4,3)=2415\).
Более крупная численная проверка даёт
$$C(9,12)\approx 2.5720 \times 10^{46},$$
а для основной задачи программа печатает
$$C(100,500)\approx 6.3202 \times 10^{25093}.$$
Решение на C++ поддерживает аргументы --m=, --n= и --skip-checkpoints. Оно заранее строит две таблицы косинусов, затем перебирает все пары \((i,j)\ne(0,0)\), вычисляет собственное значение \(4-2c_i-2c_j\), добавляет его \(\log_{10}\) с компенсацией Кэхэна, вычитает \(\log_{10}(mn)\) и формирует строку в научной записи. Решение на Python повторяет ту же математическую схему и тоже кэширует косинусы, но написано более компактно и без встроенных проверок. Решение на Java использует ту же формулу и ту же логику округления, однако косинусы там вычисляются прямо внутри циклов, без дополнительных массивов.
Основная стоимость определяется двойным циклом по \(mn-1\) ненулевым собственным значениям, поэтому время работы равно \(O(mn)\). Версии на C++ и Python используют \(O(m+n)\) дополнительной памяти для таблиц косинусов. Версия на Java пересчитывает косинусы на месте и требует лишь \(O(1)\) дополнительной памяти. В любом случае это намного дешевле, чем вычислять огромный детерминант или выполнять точную линейную алгебру над гигантскими целыми числами.
لنرمز بـ \(C(m,n)\) إلى عدد الأشجار الممتدة في الرسم الشبكي المستطيلي \(m \times n\). في مسألة Project Euler المطلوبة تكون القيمتان \((m,n)=(100,500)\)، لكن العدد الصحيح الناتج يملك أكثر من خمسة وعشرين ألف رقم عشري، لذلك لا تبني الحلول المحلية العدد الكامل، بل تطبع النتيجة بالصيغة العلمية.
الفكرة المشتركة بين ملفات الحل الثلاثة هي نفسها: مبرهنة Matrix-Tree تحوّل مسألة العد إلى حاصل ضرب القيم الذاتية غير الصفرية لمصفوفة لابلاسيان الخاصة بالشبكة، وهذه القيم يمكن كتابتها بصيغة مغلقة.
إذا كان \(G\) رسماً بيانياً متصلاً وله قيم ذاتية للابلاسيان على الصورة
$$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1},$$
فإن مبرهنة كيرشوف تعطي
$$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$$
وبما أن الشبكة المستطيلة تملك \(mn\) رأساً، فإن معرفة جميع القيم الذاتية غير الصفرية تكفي مباشرة لحساب \(C(m,n)\).
يمكن النظر إلى شبكة \(m \times n\) على أنها حاصل الضرب الديكارتي لرسمي مسار. بالنسبة إلى المسار ذي \(m\) رؤوس، تكون قيم لابلاسيان الذاتية
$$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$$
وبالنسبة إلى المسار ذي \(n\) رؤوس، تكون
$$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$$
في حاصل الضرب الديكارتي تتجمع القيم الذاتية جمعاً، ولذلك نحصل في الشبكة على
$$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$$
الزوج \((i,j)=(0,0)\) فقط يعطي القيمة الصفرية، أما بقية الأزواج فتعطي قيماً موجبة لأن الرسم البياني متصل.
بالتعويض في مبرهنة كيرشوف نحصل على
$$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$$
وهذه هي الصيغة التي تطبقها الحلول الثلاثة حرفياً. بعد هذه الخطوة تنتهي الفكرة التوافقية، ويبقى التحدي العددي فقط: حاصل ضرب يضم \(mn-1\) عاملاً موجباً ويصبح ضخماً جداً.
الضرب المباشر غير مناسب لأنه يسبب تضخماً هائلاً وفقداناً في الاستقرار العددي. لذلك تحسب البرامج
$$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$$
ثم نكتب
$$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$$
حيث \(1 \le \mu \lt 10\). بعد ذلك تُقرب \(\mu\) إلى خمس خانات معنوية. وإذا أدى التقريب إلى \(10.0000\)، تُقسم المانتيسا على \(10\) ويزداد الأس بمقدار واحد.
نسخة C++ تضيف جمع Kahan لتقليل خطأ التقريب عند جمع عدد كبير من اللوغاريتمات. أما نسختا Python وJava فتستخدمان الصيغة نفسها ولكن من دون خطوة التعويض هذه.
ملف C++ يحتوي على نقاط تحقق مفيدة لفهم الرياضيات والتأكد من صحة التنفيذ.
عندما \(m=n=1\) يوجد رأس واحد فقط، لذلك \(C(1,1)=1\).
وعندما \(m=n=2\) تكون القيم الذاتية غير الصفرية هي \(2\) و\(2\) و\(4\)، ومن ثم
$$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$$
وتوجد أيضاً قيمة تحقق دقيقة هي
$$C(3,4)=2415,$$
وبفعل التناظر يجب أن يكون \(C(4,3)=2415\) كذلك.
ولفحص عددي أكبر، يطبع البرنامج
$$C(9,12)\approx 2.5720 \times 10^{46},$$
أما في المثال المطلوب في Project Euler فينتج
$$C(100,500)\approx 6.3202 \times 10^{25093}.$$
حل C++ يدعم الوسائط الاختيارية --m= و--n= و--skip-checkpoints. يقوم أولاً ببناء جدولين لقيم جيب التمام، ثم يمر على جميع الأزواج \((i,j)\ne(0,0)\)، ويحسِب القيمة الذاتية \(4-2c_i-2c_j\)، ويجمع \(\log_{10}\) باستخدام تعويض Kahan، ثم يطرح \(\log_{10}(mn)\)، وأخيراً يعيد بناء السلسلة بالصيغة العلمية. حل Python يتبع المسار الرياضي نفسه ويخزن القيم المسبقة أيضاً، لكنه أبسط ولا يحتوي على اختبارات مدمجة. أما حل Java فيستخدم الصيغة نفسها وقاعدة التقريب نفسها، لكنه يعيد حساب جيب التمام داخل الحلقات بدلاً من تخزينه في مصفوفات.
العمل الأساسي هو الحلقة الثنائية فوق \(mn-1\) موضعاً ذا قيمة ذاتية غير صفرية، ولذلك يكون الزمن \(O(mn)\). نسختا C++ وPython تحتاجان إلى \(O(m+n)\) من الذاكرة الإضافية لتخزين جداول جيب التمام. أما نسخة Java فتعيد الحساب مباشرة وتحتاج فقط إلى \(O(1)\) من الذاكرة الإضافية. وفي كل الأحوال فهذا النهج أرخص بكثير من تكوين محدد هائل أو تنفيذ جبر خطي دقيق على أعداد صحيحة ضخمة.