Let \(f(n)\) denote the tiling count defined by the problem. The key fact used by the implementation is that this counting sequence already has an exact closed form, so the task is no longer to enumerate tilings but to evaluate that formula at an enormous index. The program is written in terms of \(f(10^k)\), and the actual Project Euler instance uses \(k=10^{18}\), so the target quantity is \(f(10^{10^{18}})\bmod 17^7\).
The C++, Python, and Java implementations all begin with the identity
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
This means the original tiling combinatorics have been compressed into three exponential terms and a constant. Once this formula is known, the whole problem becomes modular arithmetic with very large exponents.
Although the expression contains fractions, the result is always an integer. Multiply both sides by \(15\):
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
The right-hand side is divisible by \(3\) and by \(5\). Modulo \(3\), we use \(2\equiv -1\pmod 3\), so
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
Modulo \(5\), we use \(4\equiv -1\pmod 5\), so
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
Hence the numerator is always divisible by \(15\), which explains why the sequence values are integers even though the closed form is written with rational coefficients.
Let
$$M=17^7=410338673.$$
Because \(3\), \(5\), and \(15\) are all coprime to \(M\), they have modular inverses. Therefore the same formula can be evaluated modulo \(M\) as
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M.$$
This is the exact form used by the implementation: the fractions are replaced by modular inverses, and every multiplication is reduced modulo \(M\).
The hard part is that \(n\) itself is huge. In the actual instance, \(n=10^{10^{18}}\). Since \(2\) and \(4\) are both coprime to \(17\), Euler's theorem applies. For a prime power \(17^7\),
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
Hence
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
so exponents may be reduced modulo \(\varphi(M)\):
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M.$$
For the parameterized form \(n=10^k\), we therefore compute
$$e\equiv 10^k\pmod{\varphi(M)}$$
and then evaluate only \(2^e\) and \(4^e\) modulo \(M\). For the actual input \(k=10^{18}\), this reduction gives
$$10^{10^{18}}\equiv 152370032\pmod{386201104}.$$
So the astronomically large exponents collapse to ordinary modular powers with exponent \(152370032\).
The sign term is even simpler. If \(k\ge 1\), then \(10^k\) is even, so
$$(-1)^{10^k}=1.$$
Only the degenerate case \(k=0\) gives \(n=1\), where the sign is negative. Therefore, for every real problem instance with \(k\ge 1\), the formula simplifies to
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M,$$
with \(e\equiv 10^k\pmod{\varphi(M)}\).
A small exact check is \(n=4\). Then
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
Putting everything over denominator \(15\),
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82.$$
This matches the checkpoint used in the implementation. Another useful consistency check is
$$f(10^9)\equiv 126897180\pmod{17^7}.$$
The implementation performs only a constant number of fast modular exponentiations. First it computes \(\varphi(17^7)\). Next it finds \(10^k \bmod \varphi(17^7)\) by binary exponentiation, which is enough to recover the needed powers of \(2\) and \(4\). The rational coefficients are converted into modular inverses using Euler's theorem in the form \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\) for \(a\in\{3,5,15\}\). Finally the four terms of the closed form are assembled with modular addition and subtraction.
So the program never constructs \(10^{10^{18}}\) as an ordinary integer, never enumerates tilings, and never performs any dynamic programming over the combinatorial objects. Everything is reduced to a tiny number of modular operations.
Binary exponentiation takes logarithmic time in the exponent. Therefore the full method costs
$$O(\log k+\log M)$$
time and \(O(1)\) memory. Since the modulus \(M=17^7\) is fixed in this problem, the practical cost is essentially \(O(\log k)\) with constant auxiliary space.
Sei \(f(n)\) die im Problem definierte Anzahl rechteckiger Pflasterungen. Die Implementierung zählt diese Pflasterungen nicht direkt aus, sondern nutzt eine bereits bekannte geschlossene Formel für die Folge. Das Programm ist in der Form \(f(10^k)\) geschrieben; im eigentlichen Project-Euler-Fall ist \(k=10^{18}\), also wird \(f(10^{10^{18}})\bmod 17^7\) gesucht.
Alle drei Implementierungen verwenden die Identität
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
Damit ist die eigentliche Kombinatorik der Pflasterungen bereits in eine Summe aus drei Exponentialtermen und einer Konstanten verdichtet. Rechnerisch bleibt nur noch übrig, diesen Ausdruck für einen riesigen Index modulo \(17^7\) auszuwerten.
Obwohl die Formel rationale Koeffizienten enthält, ist \(f(n)\) für jedes \(n\) ganzzahlig. Multipliziert man mit \(15\), so erhält man
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
Die rechte Seite ist durch \(3\) und durch \(5\) teilbar. Modulo \(3\) gilt \(2\equiv -1\pmod 3\), also
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
Modulo \(5\) gilt \(4\equiv -1\pmod 5\), also
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
Damit ist der Zähler immer durch \(15\) teilbar. Genau deshalb liefert die geschlossene Form trotz der Brüche ganzzahlige Folgenglieder.
Setze
$$M=17^7=410338673.$$
Da \(3\), \(5\) und \(15\) teilerfremd zu \(M\) sind, besitzen sie modulare Inversen. Also kann man modulo \(M\) schreiben
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M.$$
Genau so rechnet die Implementierung: Die Brüche werden durch modulare Inverse ersetzt, und jede Operation wird sofort modulo \(M\) reduziert.
Die Schwierigkeit liegt darin, dass \(n\) selbst enorm groß ist. Im eigentlichen Fall gilt \(n=10^{10^{18}}\). Weil \(2\) und \(4\) zu \(17^7\) teilerfremd sind, darf man den Exponenten mit dem Satz von Euler reduzieren. Für die Primzahlpotenz \(17^7\) ist
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
Daher folgt
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
und damit
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M.$$
Für die parametrische Schreibweise \(n=10^k\) berechnet man also zuerst
$$e\equiv 10^k\pmod{\varphi(M)}$$
und braucht danach nur noch \(2^e\) und \(4^e\) modulo \(M\). Für den realen Eingabewert \(k=10^{18}\) ergibt sich
$$10^{10^{18}}\equiv 152370032\pmod{386201104}.$$
Der gigantische Exponent schrumpft somit auf eine normale modulare Potenz mit Exponent \(152370032\).
Der Vorzeichen-Term ist noch einfacher. Für \(k\ge 1\) ist \(10^k\) gerade, also
$$(-1)^{10^k}=1.$$
Nur der Sonderfall \(k=0\) liefert \(n=1\) und damit ein negatives Vorzeichen. Für alle echten Problemfälle mit \(k\ge 1\) vereinfacht sich die Formel also zu
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M,$$
wobei \(e\equiv 10^k\pmod{\varphi(M)}\).
Ein kleiner exakter Test ist \(n=4\). Dann gilt
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
Auf Nenner \(15\) gebracht ergibt das
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82.$$
Das stimmt mit dem Kontrollwert der Implementierung überein. Ein weiterer modularer Kontrollwert lautet
$$f(10^9)\equiv 126897180\pmod{17^7}.$$
Die Implementierung benötigt nur eine konstante Anzahl schneller modularer Potenzierungen. Zuerst wird \(\varphi(17^7)\) bestimmt. Dann wird per binärer Exponentiation \(10^k\bmod \varphi(17^7)\) berechnet; daraus folgen sofort die benötigten Potenzen von \(2\) und \(4\). Die rationalen Koeffizienten werden über den Satz von Euler in modulare Inverse umgewandelt, also \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\) für \(a\in\{3,5,15\}\). Anschließend werden die vier Terme der geschlossenen Formel modular zusammengesetzt.
Weder \(10^{10^{18}}\) noch die Menge aller Pflasterungen werden jemals explizit konstruiert. Der gesamte Rechenaufwand wird auf wenige modulare Operationen reduziert.
Binäre Exponentiation benötigt logarithmische Zeit in der Größe des Exponenten. Insgesamt kostet das Verfahren daher
$$O(\log k+\log M)$$
Zeit und \(O(1)\) Speicher. Da \(M=17^7\) in dieser Aufgabe fest ist, ist die praktische Laufzeit im Wesentlichen \(O(\log k)\) bei konstantem Speicherbedarf.
\(f(n)\), problemde tanımlanan dikdortgensel doseme sayisini gostersin. Uygulama bu dosemeleri dogrudan saymiyor; bunun yerine dizi icin zaten bilinen kapali formu kullaniyor. Program \(f(10^k)\) biciminde yazilmis durumda ve gercek Project Euler orneginde \(k=10^{18}\) oldugu icin hedeflenen nicelik \(f(10^{10^{18}})\bmod 17^7\) oluyor.
C++, Python ve Java uygulamalarinin ortak cikis noktasi su ozdesliktir:
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
Boylece asil kombinatorik yapi uc ussel terim ve bir sabite sikistirilmis olur. Bu formul elde olduktan sonra problem, buyuk bir indeks icin moduler hesap yapma problemine donusur.
Formulde kesirler gorunse de \(f(n)\) her zaman tam sayidir. Her iki tarafi \(15\) ile carpalim:
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
Sag taraf hem \(3\)'e hem \(5\)'e bolunur. Modulo \(3\) icin \(2\equiv -1\pmod 3\) oldugundan
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
Modulo \(5\) icin \(4\equiv -1\pmod 5\) oldugundan
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
Demek ki pay her zaman \(15\)'e bolunur. Kapali formdaki rasyonel katsayilarin tam sayi deger uretmesinin nedeni budur.
Su modulu tanimlayalim:
$$M=17^7=410338673.$$
\(3\), \(5\) ve \(15\), \(M\) ile aralarinda asal oldugu icin moduler tersleri vardir. Bu nedenle formul mod \(M\) altinda
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M$$
seklinde yazilir. Uygulamanin yaptigi sey tam olarak budur: kesirler moduler terslerle temsil edilir ve her ara adimda \(M\) ile indirgeme yapilir.
Zorluk, \(n\)'nin kendisinin cok buyuk olmasidir. Gercek ornekte \(n=10^{10^{18}}\). \(2\) ve \(4\), \(17^7\) ile aralarinda asal oldugundan Euler teoremi uygulanabilir. \(17^7\) icin
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
Dolayisiyla
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
ve bu da
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M$$
demektir. \(n=10^k\) seklindeki parametrik durumda once
$$e\equiv 10^k\pmod{\varphi(M)}$$
hesaplanir, sonra yalnizca \(2^e\) ve \(4^e\) mod \(M\) bulunur. Gercek girdi \(k=10^{18}\) icin
$$10^{10^{18}}\equiv 152370032\pmod{386201104}$$
oldugundan, astronomik buyuklukteki usler normal boyutta moduler uslere iner.
\(k\ge 1\) oldugunda \(10^k\) cifttir; dolayisiyla
$$(-1)^{10^k}=1.$$
Yalnizca \(k=0\) durumunda \(n=1\) olur ve isaret terimi farkli kalir. Bu nedenle gercek problem icin formul
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M$$
sekline sadeleşir; burada \(e\equiv 10^k\pmod{\varphi(M)}\).
Kucuk bir dogrulama ornegi \(n=4\)'tur. Bu durumda
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
Payda \(15\)'te birlestirilirse
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82$$
elde edilir. Bu, uygulamadaki kontrol degeriyle uyumludur. Daha buyuk bir moduler kontrol degeri de
$$f(10^9)\equiv 126897180\pmod{17^7}$$
seklindedir.
Uygulama yalnizca sabit sayida hizli moduler us alma islemi yapar. Once \(\varphi(17^7)\) hesaplanir. Sonra binary exponentiation ile \(10^k\bmod \varphi(17^7)\) bulunur; bu deger, gerekli \(2\) ve \(4\) kuvvetleri icin yeterlidir. Rasyonel katsayilar, \(a\in\{3,5,15\}\) icin \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\) formuluyle moduler terse cevrilir. Son adimda kapali formun dort terimi moduler toplama ve cikarma ile birlestirilir.
Boylece program ne \(10^{10^{18}}\) sayisini acikca olusturur ne de dosemeleri tek tek sayar. Tum islem, cok az sayida moduler operasyona indirgenir.
Binary exponentiation, ustun buyuklugunde logaritmik zamanda calisir. Bu nedenle toplam maliyet
$$O(\log k+\log M)$$
zaman ve \(O(1)\) bellek olur. Bu problemde \(M=17^7\) sabit oldugu icin pratikte maliyet esasen \(O(\log k)\) ve sabit ek bellek seviyesindedir.
Sea \(f(n)\) el numero de teselaciones rectangulares definido por el problema. La implementacion no enumera directamente esas teselaciones; parte de una formula cerrada exacta para la sucesion. El programa esta planteado como \(f(10^k)\), y en la instancia real de Project Euler se usa \(k=10^{18}\), de modo que la cantidad buscada es \(f(10^{10^{18}})\bmod 17^7\).
Las implementaciones en C++, Python y Java utilizan la identidad
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
Eso significa que toda la parte combinatoria del recubrimiento ya esta condensada en tres terminos exponenciales y una constante. Una vez conocida esta identidad, el problema computacional es solo evaluar la expresion modulo \(17^7\) para un indice gigantesco.
Aunque aparecen fracciones, el valor de \(f(n)\) siempre es entero. Multiplicando por \(15\), obtenemos
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
El numerador es divisible por \(3\) y por \(5\). Modulo \(3\), como \(2\equiv -1\pmod 3\), se tiene
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
Modulo \(5\), como \(4\equiv -1\pmod 5\), se obtiene
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
Por lo tanto, el numerador siempre es multiplo de \(15\), y la formula cerrada produce enteros pese a sus coeficientes racionales.
Tomemos
$$M=17^7=410338673.$$
Puesto que \(3\), \(5\) y \(15\) son coprimos con \(M\), existen inversos modulares. La formula se puede evaluar entonces como
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M.$$
Esta es precisamente la forma operativa del programa: reemplazar divisiones por inversos modulares y reducir cada operacion modulo \(M\).
La dificultad real es que \(n\) es descomunal. En la instancia del problema, \(n=10^{10^{18}}\). Como \(2\) y \(4\) son coprimos con \(17^7\), se aplica el teorema de Euler. Para la potencia prima \(17^7\),
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
En consecuencia,
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
y por ello
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M.$$
Si escribimos \(n=10^k\), basta calcular
$$e\equiv 10^k\pmod{\varphi(M)}$$
y luego usar solo \(2^e\) y \(4^e\) modulo \(M\). Para el valor real \(k=10^{18}\), se obtiene
$$10^{10^{18}}\equiv 152370032\pmod{386201104}.$$
Asi, un exponente astronomico se convierte en una potencia modular completamente manejable.
Si \(k\ge 1\), entonces \(10^k\) es par y por tanto
$$(-1)^{10^k}=1.$$
Solo el caso especial \(k=0\) produce \(n=1\). Para las instancias reales con \(k\ge 1\), la expresion se simplifica a
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M,$$
donde \(e\equiv 10^k\pmod{\varphi(M)}\).
Una comprobacion exacta pequena es \(n=4\). Entonces
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
Llevando todo al denominador \(15\),
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82.$$
Esto coincide con el valor de control usado por la implementacion. Otro control util es
$$f(10^9)\equiv 126897180\pmod{17^7}.$$
La implementacion realiza solo un numero constante de exponenciaciones modulares rapidas. Primero calcula \(\varphi(17^7)\). Despues obtiene \(10^k\bmod \varphi(17^7)\) mediante exponenciacion binaria, lo cual basta para recuperar las potencias necesarias de \(2\) y \(4\). Los coeficientes racionales se convierten en inversos modulares usando \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\) para \(a\in\{3,5,15\}\). Finalmente se ensamblan los cuatro terminos de la formula cerrada con sumas y restas modulares.
En ningun momento se construye \(10^{10^{18}}\) como entero ordinario ni se enumeran teselaciones. Todo queda reducido a unas pocas operaciones modulares.
La exponenciacion binaria requiere tiempo logaritmico en el exponente. Por tanto, el coste total es
$$O(\log k+\log M)$$
en tiempo y \(O(1)\) en memoria. Como \(M=17^7\) es fijo en este problema, en la practica el coste es esencialmente \(O(\log k)\) con memoria constante.
设 \(f(n)\) 表示题目中定义的矩形铺砌计数。实现并不直接枚举所有铺法，而是从这个计数序列的精确闭式出发。程序采用 \(f(10^k)\) 的参数化写法，而实际 Project Euler 实例取 \(k=10^{18}\)，因此真正要求的是 \(f(10^{10^{18}})\bmod 17^7\)。
C++、Python 和 Java 三个实现都使用同一个恒等式：
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
这说明原始的铺砌组合结构已经被压缩成三个指数项加一个常数项。已知这个闭式之后，计算问题就变成了“如何在模 \(17^7\) 下高效求值”。
虽然公式里有分数，但 \(f(n)\) 对每个 \(n\) 都是整数。两边同乘 \(15\)，得到
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
右边同时能被 \(3\) 和 \(5\) 整除。模 \(3\) 下，由于 \(2\equiv -1\pmod 3\)，有
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
模 \(5\) 下，由于 \(4\equiv -1\pmod 5\)，有
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
因此分子始终是 \(15\) 的倍数，这就解释了为什么闭式虽然写成有理数形式，但实际序列值始终是整数。
令
$$M=17^7=410338673.$$
因为 \(3\)、\(5\)、\(15\) 都与 \(M\) 互素，所以它们在模 \(M\) 下都有逆元。于是可以写成
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M.$$
这正是实现的核心形式：把除法改成乘以模逆元，并在每一步都对 \(M\) 取模。
真正的难点在于 \(n\) 本身极大。实际实例里 \(n=10^{10^{18}}\)。由于 \(2\) 和 \(4\) 都与 \(17^7\) 互素，可以使用欧拉定理。对素数幂 \(17^7\) 有
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
因此
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
从而
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M.$$
对参数形式 \(n=10^k\)，只需先计算
$$e\equiv 10^k\pmod{\varphi(M)}$$
然后再求 \(2^e\) 和 \(4^e\) 的模值。对真实输入 \(k=10^{18}\)，有
$$10^{10^{18}}\equiv 152370032\pmod{386201104}.$$
也就是说，天文级别的大指数最终被压缩成了普通规模的模幂计算。
当 \(k\ge 1\) 时，\(10^k\) 一定是偶数，所以
$$(-1)^{10^k}=1.$$
只有特殊情形 \(k=0\) 才会给出 \(n=1\)。因此在真正的问题输入中，公式直接化简为
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M,$$
其中 \(e\equiv 10^k\pmod{\varphi(M)}\)。
一个小的精确校验是 \(n=4\)。此时
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
统一分母为 \(15\)，得到
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82.$$
这与实现中的检查值一致。另一个更大的模校验为
$$f(10^9)\equiv 126897180\pmod{17^7}.$$
实现只做常数次快速模幂。首先计算 \(\varphi(17^7)\)。然后用二进制快速幂求出 \(10^k\bmod \varphi(17^7)\)，这就足以恢复所需的 \(2\) 次幂和 \(4\) 次幂。分数系数通过模逆元处理，即对 \(a\in\{3,5,15\}\) 使用 \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\)。最后再把闭式中的四个部分用模加法和模减法组合起来。
整个过程从不真正构造 \(10^{10^{18}}\)，也不枚举任何铺砌方案。所有工作都被压缩成少量模运算。
二进制快速幂对指数的时间复杂度是对数级，因此总复杂度为
$$O(\log k+\log M)$$
时间，\(O(1)\) 额外空间。由于本题中的模数 \(M=17^7\) 是固定常数，所以实际运行成本基本就是 \(O(\log k)\)。
Пусть \(f(n)\) обозначает число прямоугольных разбиений, заданное в условии. Реализация не перебирает разбиения напрямую, а использует уже известную точную замкнутую формулу для этой последовательности. Программа записана в виде \(f(10^k)\), а в реальном экземпляре Project Euler берется \(k=10^{18}\), поэтому нужно найти \(f(10^{10^{18}})\bmod 17^7\).
Во всех трех реализациях используется тождество
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
То есть вся комбинаторика замощений уже сведена к сумме трех экспоненциальных членов и константы. После этого вычислительная задача состоит только в том, чтобы быстро посчитать эту формулу по модулю \(17^7\) при огромном значении \(n\).
Хотя в записи есть дроби, \(f(n)\) всегда целое число. Умножим формулу на \(15\):
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
Правая часть делится и на \(3\), и на \(5\). По модулю \(3\), так как \(2\equiv -1\pmod 3\), имеем
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
По модулю \(5\), так как \(4\equiv -1\pmod 5\), получаем
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
Следовательно, числитель всегда кратен \(15\). Именно поэтому замкнутая формула с рациональными коэффициентами на самом деле порождает целочисленную последовательность.
Положим
$$M=17^7=410338673.$$
Числа \(3\), \(5\) и \(15\) взаимно просты с \(M\), значит у них существуют обратные элементы по модулю \(M\). Поэтому формулу можно переписать как
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M.$$
Именно в таком виде вычисляет программа: деление заменяется умножением на модульный обратный, а каждое действие немедленно редуцируется по модулю \(M\).
Главная трудность состоит в размере \(n\). В реальной задаче \(n=10^{10^{18}}\). Поскольку \(2\) и \(4\) взаимно просты с \(17^7\), можно применить теорему Эйлера. Для степени простого числа \(17^7\)
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
Следовательно,
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
а значит
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M.$$
Для параметризации \(n=10^k\) достаточно сначала вычислить
$$e\equiv 10^k\pmod{\varphi(M)}$$
и затем использовать только \(2^e\) и \(4^e\) по модулю \(M\). Для реального входа \(k=10^{18}\) получается
$$10^{10^{18}}\equiv 152370032\pmod{386201104}.$$
Таким образом, колоссальный показатель степени заменяется обычной модульной степенью с вполне умеренным показателем.
Если \(k\ge 1\), то \(10^k\) четно, поэтому
$$(-1)^{10^k}=1.$$
Только особый случай \(k=0\) дает \(n=1\). Значит, для реальных входных данных формула упрощается до
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M,$$
где \(e\equiv 10^k\pmod{\varphi(M)}\).
Небольшая точная проверка: \(n=4\). Тогда
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
Приводя к знаменателю \(15\), получаем
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82.$$
Это совпадает с контрольным значением в реализации. Еще одна полезная модульная проверка:
$$f(10^9)\equiv 126897180\pmod{17^7}.$$
Реализация выполняет только постоянное число быстрых модульных возведений в степень. Сначала вычисляется \(\varphi(17^7)\). Затем бинарным возведением в степень находится \(10^k\bmod \varphi(17^7)\), и этого уже достаточно для вычисления нужных степеней \(2\) и \(4\). Рациональные коэффициенты заменяются модульными обратными с помощью формулы \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\) для \(a\in\{3,5,15\}\). После этого четыре члена замкнутой формулы складываются и вычитаются по модулю.
Ни число \(10^{10^{18}}\), ни множество всех разбиений никогда не строятся явно. Вся задача сведена к нескольким модульным операциям.
Бинарное возведение в степень работает за логарифмическое время по величине показателя. Поэтому полный метод имеет сложность
$$O(\log k+\log M)$$
по времени и \(O(1)\) по памяти. Поскольку \(M=17^7\) в этой задаче фиксировано, практическая стоимость по существу равна \(O(\log k)\) при постоянной памяти.
لنرمز بـ \(f(n)\) إلى عدد التبليطات المستطيلة المعرفة في المسألة. لا تقوم التطبيقات بعدّ جميع التبليطات مباشرة، بل تبدأ من صيغة مغلقة دقيقة لهذه المتتالية. والبرنامج مكتوب على صورة \(f(10^k)\)، وفي الحالة الفعلية من Project Euler يكون \(k=10^{18}\)، ولذلك فإن المطلوب هو حساب \(f(10^{10^{18}})\bmod 17^7\).
تعتمد تطبيقات C++ وPython وJava جميعًا على الهوية التالية:
$$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$
وهذا يعني أن البنية التوافقية الأصلية للتبليطات قد اختُزلت إلى ثلاثة حدود أسية وحد ثابت. وبعد معرفة هذه الصيغة، تتحول المهمة الحسابية إلى تقييمها modulo \(17^7\) عند قيمة هائلة جدًا من \(n\).
على الرغم من ظهور الكسور، فإن \(f(n)\) عدد صحيح دائمًا. إذا ضربنا الطرفين في \(15\) نحصل على
$$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$
الطرف الأيمن قابل للقسمة على \(3\) وعلى \(5\). فبترديد \(3\)، وبما أن \(2\equiv -1\pmod 3\)، نحصل على
$$-(-1)^n-20\cdot 2^n\equiv -(-1)^n-2^{n+1}\equiv -(-1)^n-(-1)^{n+1}\equiv 0\pmod 3.$$
وبترديد \(5\)، وبما أن \(4\equiv -1\pmod 5\)، نحصل على
$$-(-1)^n+6\cdot 4^n\equiv -(-1)^n+4^n\equiv -(-1)^n+(-1)^n\equiv 0\pmod 5.$$
إذن البسط دائمًا من مضاعفات \(15\)، وهذا يفسر لماذا تعطي الصيغة المغلقة قيمًا صحيحة رغم أن معاملاتِها كسرية.
لنأخذ
$$M=17^7=410338673.$$
ولأن \(3\) و\(5\) و\(15\) جميعها أولية نسبيًا مع \(M\)، فهي تملك معكوسات معيارية. لذلك يمكن كتابة الصيغة على الصورة
$$f(n)\equiv 1-(-1)^n\cdot 15^{-1}-4\cdot 2^n\cdot 3^{-1}+2\cdot 4^n\cdot 5^{-1}\pmod M.$$
وهذه هي الصيغة العملية في التنفيذ: تُستبدل القسمة بالضرب في المعكوس المعياري، وتُختزل كل عملية مباشرة modulo \(M\).
الصعوبة الأساسية هي أن \(n\) نفسه ضخم للغاية. ففي الحالة الفعلية \(n=10^{10^{18}}\). وبما أن \(2\) و\(4\) أوليان نسبيًا مع \(17^7\)، يمكن تطبيق نظرية أويلر. وللقوة الأولية \(17^7\) يكون
$$\varphi(M)=17^7-17^6=16\cdot 17^6=386201104.$$
ومن ثم
$$2^{\varphi(M)}\equiv 1\pmod M,\qquad 4^{\varphi(M)}\equiv 1\pmod M,$$
وبالتالي
$$2^n\equiv 2^{\,n\bmod \varphi(M)}\pmod M,\qquad 4^n\equiv 4^{\,n\bmod \varphi(M)}\pmod M.$$
وعند كتابة \(n=10^k\)، يكفي أولًا حساب
$$e\equiv 10^k\pmod{\varphi(M)}$$
ثم حساب \(2^e\) و\(4^e\) فقط modulo \(M\). وللقيمة الفعلية \(k=10^{18}\) نحصل على
$$10^{10^{18}}\equiv 152370032\pmod{386201104}.$$
وهكذا ينهار الأس الهائل إلى أس معياري عادي يمكن التعامل معه بسهولة.
إذا كان \(k\ge 1\)، فإن \(10^k\) عدد زوجي، ولذلك
$$(-1)^{10^k}=1.$$
الحالة الخاصة الوحيدة هي \(k=0\) حيث \(n=1\). أما في جميع الحالات الفعلية للمسألة فتتبسط الصيغة إلى
$$f(10^k)\equiv 1-15^{-1}-4\cdot 2^e\cdot 3^{-1}+2\cdot 4^e\cdot 5^{-1}\pmod M,$$
حيث \(e\equiv 10^k\pmod{\varphi(M)}\).
فحص صغير ودقيق هو \(n=4\). عندئذ
$$f(4)=1-\frac{1}{15}-\frac{4}{3}\cdot 16+\frac{2}{5}\cdot 256.$$
وبتوحيد المقام إلى \(15\) نحصل على
$$f(4)=\frac{15-1-320+1536}{15}=\frac{1230}{15}=82.$$
وهذا يطابق قيمة التحقق المستخدمة في التنفيذ. كما أن هناك قيمة تحقق معيارية أكبر هي
$$f(10^9)\equiv 126897180\pmod{17^7}.$$
التنفيذ يحتاج فقط إلى عدد ثابت من عمليات الأس المعياري السريع. يبدأ بحساب \(\varphi(17^7)\)، ثم يحسب \(10^k\bmod \varphi(17^7)\) بالرفع الثنائي السريع، وهذا يكفي لاسترجاع القوتين المطلوبتين لـ \(2\) و\(4\). أما المعاملات الكسرية فتتحول إلى معكوسات معيارية باستعمال العلاقة \(a^{-1}\equiv a^{\varphi(M)-1}\pmod M\) من أجل \(a\in\{3,5,15\}\). وفي النهاية تُجمع حدود الصيغة المغلقة الأربعة وتُطرح معيارياً.
لا يتم أبدًا بناء العدد \(10^{10^{18}}\) كعدد عادي، ولا تُعدّ التبليطات واحدةً واحدة. كل العمل يختزل إلى بضع عمليات معيارية صغيرة.
الرفع الثنائي السريع يعمل بزمن لوغاريتمي في قيمة الأس. لذلك تكون الكلفة الكلية
$$O(\log k+\log M)$$
زمنًا و\(O(1)\) ذاكرةً إضافية. وبما أن \(M=17^7\) ثابت في هذه المسألة، فالكلفة العملية تصبح في الأساس \(O(\log k)\) مع ذاكرة ثابتة.