The solution views XOR-multiplication as polynomial multiplication over \(\mathbb{F}_2\). The enormous base value can be written as
$$T^3+T+1,\qquad T=2^{2^{52}},$$
so the task becomes: build the polynomial
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
inside \(\mathbb{F}_2[x]\), then evaluate \(g(T)\) modulo \(10^9+7\). This separates the carryless algebra from the final modular arithmetic and avoids manipulating the astronomical integer directly.
The three implementations all use the same mathematical decomposition: first construct a polynomial with coefficients in \(\{0,1\}\), then substitute a modular value for \(x\).
If a nonnegative integer has binary expansion
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
we associate to it the polynomial
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x].$$
Under this encoding, adding coefficients modulo \(2\) is exactly XOR. Therefore carryless multiplication of integers is the same as ordinary polynomial multiplication in \(\mathbb{F}_2[x]\): if
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j,$$
then the product coefficients satisfy
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j).$$
That identity is the whole reason the XOR-power can be handled as a polynomial power.
Let
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}.$$
Then the target base integer is exactly
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1.$$
So instead of working with a gigantic ordinary integer, we only need the much smaller coefficient pattern \((1,1,0,1)\), i.e. the polynomial \(f(x)\). If the carryless product is denoted by \(\otimes\), then raising the integer \(f(T)\) to an XOR-power corresponds to raising the polynomial \(f(x)\) in \(\mathbb{F}_2[x]\) first and substituting \(x=T\) afterward.
The required exponent is
$$3^8=6561,$$
so the polynomial to construct is
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x].$$
The implementations obtain this with binary exponentiation. Each multiplication is carryless, so every partial result remains a polynomial with coefficients \(0\) or \(1\). Since \(\deg f=3\), the final degree is
$$\deg g = 3\cdot 6561 = 19683.$$
That degree is large, but still tiny compared with the size of the original integer suggested by \(2^{2^{52}}\).
Once \(g(x)\) has been constructed, the remaining task is numerical evaluation. Let
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M.$$
If
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
then the required value is
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M.$$
This evaluation happens in \(\mathbb{Z}/M\mathbb{Z}\), not in \(\mathbb{F}_2[x]\). The switch of rings is valid because the polynomial coefficients are already fixed concrete bits. After the coefficient list is known, the same polynomial can be substituted into any target ring.
A small example shows why carryless squaring behaves differently from ordinary squaring. Over \(\mathbb{F}_2\), cross terms cancel in pairs, so
$$f(x)^2=(x^3+x+1)^2=x^6+x^2+1.$$
The coefficient pattern is therefore
$$1000101_2,$$
which is decimal \(69\). In other words, the carryless square of the bit pattern \(1011_2\) is \(1000101_2\). The full problem uses exactly the same rule, only with exponent \(6561\) instead of \(2\), and with final substitution at \(X\equiv 2^{2^{52}}\pmod M\).
The C++, Python, and Java implementations all follow the same pipeline. First, the polynomial is stored as a large integer whose \(k\)-th bit indicates whether the coefficient of \(x^k\) is \(1\). Carryless multiplication is then performed by scanning the set bits of one operand and XORing shifted copies of the other operand, which is exactly the shift-and-add idea with XOR instead of ordinary addition.
Next, repeated squaring and conditional multiplication build \((x^3+x+1)^{6561}\). After that, ordinary modular exponentiation computes \(2^{2^{52}} \bmod 10^9+7\). Finally, the polynomial is evaluated from highest degree to lowest degree with Horner's method, using only modular multiplication by \(X\) and a possible addition of \(1\) when the current coefficient bit is present.
Let \(E=6561\) and \(d=19683\). With the bitset-style representation used here, one carryless multiplication of degree-\(d\) polynomials costs \(O(d^2)\) bit operations in the naive worst case. Binary exponentiation uses \(O(\log E)\) such multiplications, while the final Horner evaluation costs \(O(d)\) modular operations. The memory usage is \(O(d)\) bits for the current large polynomial values. For this specific problem, those bounds are easily practical because \(d\) is only \(19683\).
Die Lösung interpretiert die XOR-Multiplikation als Polynom-Multiplikation über \(\mathbb{F}_2\). Der riesige Basiswert lässt sich als
$$T^3+T+1,\qquad T=2^{2^{52}},$$
schreiben. Damit reduziert sich die Aufgabe darauf, das Polynom
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
in \(\mathbb{F}_2[x]\) zu konstruieren und anschließend \(g(T)\) modulo \(10^9+7\) auszuwerten. So wird die carryless Algebra sauber von der späteren modularen Auswertung getrennt.
Alle drei Implementierungen zerlegen das Problem gleich: zuerst wird eine Bit-Polynomdarstellung aufgebaut, danach erfolgt die Einsetzung in einen modularen Zahlenwert.
Hat eine nichtnegative ganze Zahl die Binärdarstellung
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
so ordnen wir ihr das Polynom
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x]$$
zu. In diesem Modell ist Koeffizientenaddition modulo \(2\) genau XOR. Deshalb entspricht carryless Multiplikation gewöhnlicher Polynom-Multiplikation in \(\mathbb{F}_2[x]\): für
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j$$
gilt für die Produktkoeffizienten
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j).$$
Genau diese Beobachtung macht aus einer XOR-Potenz eine Polynom-Potenz.
Setze
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}.$$
Dann ist die gesuchte Basiszahl genau
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1.$$
Anstatt also eine astronomisch große gewöhnliche Ganzzahl zu manipulieren, genügt es, das kleine Koeffizientenmuster \((1,1,0,1)\) zu betrachten. Bezeichnet man das carryless Produkt mit \(\otimes\), dann entspricht die XOR-Potenz von \(f(T)\) der Potenz von \(f(x)\) in \(\mathbb{F}_2[x]\), gefolgt von der Einsetzung \(x=T\).
Der Exponent ist
$$3^8=6561,$$
also muss man
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x]$$
bestimmen. Das geschieht per binärer Exponentiation. Jede Zwischenmultiplikation ist carryless, also bleiben alle Koeffizienten stets \(0\) oder \(1\). Da \(\deg f=3\), hat das Endpolynom den Grad
$$\deg g = 3\cdot 6561 = 19683.$$
Dieser Grad ist groß genug, um nicht mehr trivial zu sein, aber immer noch winzig im Vergleich zu den Exponenten, die in \(2^{2^{52}}\) stecken.
Ist \(g(x)\) konstruiert, bleibt nur noch eine numerische Auswertung. Mit
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M$$
und
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
ist der gesuchte Wert
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M.$$
Diese Auswertung findet in \(\mathbb{Z}/M\mathbb{Z}\) statt, nicht mehr in \(\mathbb{F}_2[x]\). Das ist zulässig, weil die Koeffizientenliste schon feststeht und nur aus den Zahlen \(0\) und \(1\) besteht. Dasselbe Polynom kann daher anschließend in einem anderen Ring eingesetzt werden.
Ein kleines Beispiel zeigt, warum carryless Quadrieren anders aussieht als gewöhnliches Quadrieren. Über \(\mathbb{F}_2\) heben sich Kreuzterme paarweise auf, also
$$f(x)^2=(x^3+x+1)^2=x^6+x^2+1.$$
Das zugehörige Bitmuster ist
$$1000101_2,$$
also dezimal \(69\). Mit anderen Worten: Das carryless Quadrat von \(1011_2\) ist \(1000101_2\). Für die eigentliche Aufgabe passiert exakt derselbe Mechanismus, nur mit Exponent \(6561\) statt \(2\) und anschließender Einsetzung bei \(X\equiv 2^{2^{52}}\pmod M\).
Die C++, Python- und Java-Implementierungen folgen alle derselben Pipeline. Zuerst wird das Polynom als große Ganzzahl gespeichert, bei der das \(k\)-te Bit markiert, ob der Koeffizient von \(x^k\) gleich \(1\) ist. Carryless Multiplikation entsteht dann dadurch, dass man die gesetzten Bits eines Operanden durchläuft und passend verschobene Kopien des anderen Operanden per XOR einmischt.
Anschließend erzeugt binäre Exponentiation das Polynom \((x^3+x+1)^{6561}\). Danach wird mit gewöhnlicher modularer Exponentiation \(2^{2^{52}} \bmod 10^9+7\) berechnet. Zum Schluss wertet Horner das Polynom von oben nach unten aus: in jedem Schritt wird mit \(X\) multipliziert und bei gesetztem Koeffizientenbit noch \(1\) addiert.
Mit \(E=6561\) und \(d=19683\) kostet eine carryless Multiplikation von Polynomen bis Grad \(d\) in der naiven Worst-Case-Betrachtung \(O(d^2)\) Bit-Operationen. Die binäre Exponentiation benötigt \(O(\log E)\) solcher Multiplikationen. Die abschließende Horner-Auswertung kostet \(O(d)\) modulare Operationen, und der Speicherbedarf liegt bei \(O(d)\) Bits für die aktuellen großen Polynome. Für die konkrete Problemgröße ist das problemlos praktikabel.
Çözüm, XOR çarpımını \(\mathbb{F}_2\) üzerinde polinom çarpımı olarak yorumlar. Devasa taban değer
$$T^3+T+1,\qquad T=2^{2^{52}},$$
şeklinde yazılabildiği için görev,
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
polinomunu önce \(\mathbb{F}_2[x]\) içinde üretip sonra \(g(T)\) değerini \(10^9+7\) modunda hesaplamaya indirgenir. Böylece taşımasız cebir ile son modüler değerlendirme birbirinden ayrılır.
Üç dildeki uygulamaların ortak matematik fikri aynıdır: önce katsayıları \(0\) ve \(1\) olan bir polinom kurulur, sonra bu polinoma modüler bir sayı değeri yerleştirilir.
Negatif olmayan bir tam sayının ikilik açılımı
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
ise buna karşılık gelen polinomu
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x]$$
olarak alırız. Bu modelde katsayıların \(2\) moduna göre toplanması tam olarak XOR işlemidir. Dolayısıyla taşımasız çarpım, \(\mathbb{F}_2[x]\) içindeki sıradan polinom çarpımına denktir. Eğer
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j$$
ise çarpım katsayıları
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j)$$
şeklindedir. Problem başlığındaki XOR-güçler bu eşitlik sayesinde polinom üslerine dönüşür.
Şimdi
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}$$
tanımlarını yapalım. O zaman hedef taban sayı tam olarak
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1$$
olur. Yani astronomik büyüklükte bir tam sayı ile doğrudan uğraşmak yerine, yalnızca küçük katsayı örüntüsü \((1,1,0,1)\) ile uğraşırız. XOR çarpımını \(\otimes\) ile gösterirsek, \(f(T)\)'nin XOR-kuvvetini almak; önce \(f(x)\)'i \(\mathbb{F}_2[x]\) içinde kuvvetlendirmek, sonra \(x=T\) yerleştirmekle aynıdır.
Gerekli üs
$$3^8=6561$$
olduğundan oluşturulacak polinom
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x]$$
şeklindedir. Uygulamalar bunu ikili üs alma ile yapar. Her ara çarpım taşımasız olduğu için tüm ara sonuçlar yine katsayıları \(0\) veya \(1\) olan polinomlar olarak kalır. \(\deg f=3\) olduğundan nihai derece
$$\deg g = 3\cdot 6561 = 19683$$
olur. Bu derece büyük görünse de, \(2^{2^{52}}\) ile ima edilen ham tamsayı büyüklüğü yanında çok küçüktür.
Polinom hazırlandıktan sonra geriye sayısal değerlendirme kalır. Şunu yazalım:
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M.$$
Eğer
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
ise istenen değer
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M$$
olur. Buradaki değerlendirme artık \(\mathbb{F}_2[x]\) içinde değil, \(\mathbb{Z}/M\mathbb{Z}\) halkasında yapılır. Bu geçiş geçerlidir; çünkü katsayı listesi zaten sabitlenmiştir ve yalnızca \(0\) ile \(1\)'lerden oluşur. Aynı polinom farklı bir halkada da yerine koyulabilir.
Küçük bir örnek, taşımasız kare alma ile normal kare alma arasındaki farkı gösterir. \(\mathbb{F}_2\) içinde çapraz terimler çift sayıda geldiği için birbirini götürür:
$$f(x)^2=(x^3+x+1)^2=x^6+x^2+1.$$
Bunun bit örüntüsü
$$1000101_2$$
olup onluk karşılığı \(69\)'dur. Başka bir deyişle, \(1011_2\)'nin taşımasız karesi \(1000101_2\) eder. Gerçek problemde de aynı kural işler; sadece üs \(2\) yerine \(6561\)'dir ve son değerlendirme \(X\equiv 2^{2^{52}}\pmod M\) noktasında yapılır.
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce polinom, \(k\). biti \(x^k\)'nin katsayısının \(1\) olup olmadığını gösteren büyük bir tamsayı olarak tutulur. Taşımasız çarpım yapılırken bir operandın set bitleri taranır ve diğer operandın uygun kadar sola kaydırılmış kopyaları XOR ile sonuca eklenir; yani klasik kaydır-topla fikrinin toplama kısmı XOR ile değiştirilmiştir.
Daha sonra tekrarlı kare alma ve gerekli ara çarpımlar ile \((x^3+x+1)^{6561}\) üretilir. Ardından normal modüler üs alma ile \(2^{2^{52}} \bmod 10^9+7\) bulunur. Son aşamada Horner yöntemi, polinomu en yüksek dereceden en düşüğe doğru tüketerek her adımda \(X\) ile çarpar ve o derecedeki katsayı varsa \(1\) ekler.
\(E=6561\) ve \(d=19683\) olsun. Kullanılan bit-kümesi benzeri gösterimde derece \(d\) civarındaki iki polinomun bir taşımasız çarpımı, en kötü durumda \(O(d^2)\) bit işlemi gerektirir. İkili üs alma \(O(\log E)\) adet böyle çarpım kullanır. Son Horner değerlendirmesi \(O(d)\) modüler işlemdir. Bellek kullanımı mevcut büyük polinomlar için \(O(d)\) bittir. Bu problemde \(d\) yalnızca \(19683\) olduğu için yöntem rahatlıkla uygulanabilir.
La solución interpreta la multiplicación XOR como multiplicación de polinomios sobre \(\mathbb{F}_2\). El valor base gigantesco puede escribirse como
$$T^3+T+1,\qquad T=2^{2^{52}},$$
de modo que la tarea pasa a ser construir
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
dentro de \(\mathbb{F}_2[x]\) y luego evaluar \(g(T)\) módulo \(10^9+7\). Así se evita manipular directamente el entero astronómico y se separan claramente el álgebra carryless y la aritmética modular final.
Las implementaciones en C++, Python y Java usan exactamente la misma idea matemática: primero fijan un polinomio con coeficientes binarios y después sustituyen un valor modular en la variable.
Si un entero no negativo tiene expansión binaria
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
le asociamos el polinomio
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x].$$
En este modelo, sumar coeficientes módulo \(2\) es exactamente hacer XOR. Por eso, la multiplicación carryless de enteros coincide con la multiplicación ordinaria de polinomios sobre \(\mathbb{F}_2[x]\). Si
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j,$$
entonces los coeficientes del producto cumplen
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j).$$
Esa equivalencia convierte una potencia XOR en una potencia de polinomios.
Definamos
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}.$$
Entonces el entero base es precisamente
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1.$$
En lugar de trabajar con un entero inmenso, basta con manejar el pequeño patrón de coeficientes \((1,1,0,1)\). Si denotamos el producto carryless por \(\otimes\), elevar \(f(T)\) a una potencia XOR equivale a elevar primero \(f(x)\) dentro de \(\mathbb{F}_2[x]\) y sustituir \(x=T\) al final.
El exponente requerido es
$$3^8=6561,$$
de modo que hay que construir
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x].$$
Las implementaciones lo hacen mediante exponenciación binaria. Cada multiplicación intermedia es carryless, así que todos los resultados parciales siguen siendo polinomios con coeficientes \(0\) o \(1\). Como \(\deg f=3\), el grado final es
$$\deg g = 3\cdot 6561 = 19683.$$
Ese tamaño es perfectamente manejable, aunque el número original sugerido por \(2^{2^{52}}\) sea gigantesco.
Una vez construido \(g(x)\), solo falta la evaluación numérica. Sea
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M.$$
Si escribimos
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
entonces el valor buscado es
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M.$$
Obsérvese que esta sustitución ya no ocurre en \(\mathbb{F}_2[x]\), sino en \(\mathbb{Z}/M\mathbb{Z}\). El cambio es válido porque los coeficientes del polinomio ya quedaron fijados como bits concretos. Una vez conocida la lista de coeficientes, el mismo polinomio puede evaluarse en cualquier anillo objetivo.
Un ejemplo pequeño muestra por qué el cuadrado carryless difiere del cuadrado usual. Sobre \(\mathbb{F}_2\), los términos cruzados aparecen dos veces y se cancelan, de modo que
$$f(x)^2=(x^3+x+1)^2=x^6+x^2+1.$$
El patrón de bits correspondiente es
$$1000101_2,$$
que en decimal es \(69\). Es decir, el cuadrado carryless de \(1011_2\) es \(1000101_2\). El problema real usa exactamente la misma regla, solo que con exponente \(6561\) en vez de \(2\), y luego evalúa en \(X\equiv 2^{2^{52}}\pmod M\).
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero representan el polinomio como un entero grande cuyo bit \(k\) indica si el coeficiente de \(x^k\) vale \(1\). Después realizan la multiplicación carryless recorriendo los bits encendidos de un operando y aplicando XOR a copias desplazadas del otro operando. Es la idea clásica de desplazar y sumar, pero con XOR en lugar de suma ordinaria.
Luego, la exponenciación binaria construye \((x^3+x+1)^{6561}\). A continuación, la exponenciación modular habitual calcula \(2^{2^{52}} \bmod 10^9+7\). Por último, la evaluación del polinomio usa el esquema de Horner desde el grado más alto hasta el más bajo, multiplicando cada vez por \(X\) y añadiendo \(1\) cuando el coeficiente actual está presente.
Sean \(E=6561\) y \(d=19683\). Con la representación tipo bitset usada aquí, una multiplicación carryless de polinomios de grado a lo sumo \(d\) cuesta \(O(d^2)\) operaciones de bit en el peor caso ingenuo. La exponenciación binaria necesita \(O(\log E)\) multiplicaciones de ese tipo. La evaluación final por Horner cuesta \(O(d)\) operaciones modulares, y la memoria usada es \(O(d)\) bits para los polinomios grandes intermedios. Para este problema concreto, esos costes son cómodamente manejables.
这道题的关键是把 XOR 乘法看成 \(\mathbb{F}_2\) 上的多项式乘法。题目中的巨大底数可以改写为
$$T^3+T+1,\qquad T=2^{2^{52}},$$
因此真正需要构造的是
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
这个 \(\mathbb{F}_2[x]\) 中的多项式，然后再把 \(x\) 替换成 \(T\)，最后对 \(10^9+7\) 取模。这样做把“无进位乘法的代数结构”和“最终整数模运算”彻底分开，避免直接处理规模极其夸张的普通整数。
三种语言的实现虽然语法不同，但数学思路完全一致：先用二进制系数构造多项式，再在模意义下代入一个具体数值。
如果一个非负整数的二进制展开是
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
那么把它对应成多项式
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x].$$
在这个模型里，系数按模 \(2\) 相加，正好就是按位 XOR。因此，整数的无进位乘法和 \(\mathbb{F}_2[x]\) 里的普通多项式乘法是同一件事。若
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j,$$
则乘积系数满足
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j).$$
这就是为什么题目中的 XOR 幂可以先转化成多项式幂来处理。
定义
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}.$$
那么题目对应的底数其实就是
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1.$$
也就是说，看起来庞大到几乎无法直视的整数，本质上只是把三个非零位放在了指数 \(0\)、\(2^{52}\)、\(3\cdot 2^{52}\) 这几个位置上。真正需要保存的，不是那个天文规模的值，而只是多项式 \(x^3+x+1\) 这份很短的系数表。若把无进位乘法记作 \(\otimes\)，那么对这个整数做 XOR 幂，与先在 \(\mathbb{F}_2[x]\) 中计算 \(f(x)\) 的幂，再把 \(x\) 换回 \(T\)，是完全等价的。
所需指数是
$$3^8=6561,$$
因此我们要构造
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x].$$
实现采用二进制快速幂。每一步乘法都仍然是无进位乘法，所以中间结果始终保持为“系数只有 \(0\) 和 \(1\)”的多项式。因为 \(\deg f=3\)，最终多项式的次数就是
$$\deg g = 3\cdot 6561 = 19683.$$
这个次数并不小，但和原始表达式中 \(2^{2^{52}}\) 所暗示的规模相比，已经被压缩到了完全可计算的范围。实现中并不尝试猜测某种神奇闭式，而是直接用重复平方稳定地把这个多项式算出来。
当 \(g(x)\) 已经确定以后，剩下的事情只是数值代入。记
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M.$$
如果把多项式写成
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
那么目标值就是
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M.$$
这里要特别注意：构造 \(g(x)\) 时所在的代数环境是 \(\mathbb{F}_2[x]\)，而最终代入时所在的环境是 \(\mathbb{Z}/M\mathbb{Z}\)。这并不矛盾，因为一旦多项式系数已经算出来，它们只是普通的 \(0\) 和 \(1\)。同一份系数序列既可以被理解为 \(\mathbb{F}_2\) 中的元素，也可以被理解为模 \(M\) 的整数，因此完全可以在第二步换到新的环里求值。
为什么无进位平方和普通平方不同？最直接的例子就是
$$f(x)^2=(x^3+x+1)^2.$$
在 \(\mathbb{F}_2\) 里，交叉项会成对出现并被抵消，所以
$$f(x)^2=x^6+x^2+1.$$
对应的二进制系数模式是
$$1000101_2,$$
十进制就是 \(69\)。换句话说，位模式 \(1011_2\) 的无进位平方不是普通整数平方，而是 \(1000101_2\)。这正好展示了实现的核心规则。真实题目只是把指数从 \(2\) 换成 \(6561\)，再把构造出来的多项式在 \(X\equiv 2^{2^{52}}\pmod M\) 处求值而已。
C++、Python 和 Java 实现的处理流程一致。首先，它们都把多项式存成一个大整数：如果第 \(k\) 位是 \(1\)，就表示 \(x^k\) 的系数存在。接着，做无进位乘法时，程序会遍历其中一个操作数的所有置位，然后把另一个操作数左移相应位数后做 XOR 叠加。这样就把“多项式乘法中同次数项按模 \(2\) 相加”的规则，直接映射成了位运算。
然后，程序用重复平方和按需相乘，构造出 \((x^3+x+1)^{6561}\)。之后再用普通快速幂算出 \(2^{2^{52}} \bmod 10^9+7\)。最后，多项式求值采用 Horner 法，从最高次项一路扫到常数项；每一步都先乘以 \(X\)，如果当前位置的系数位为 \(1\)，就再加上 \(1\)。因此，整个实现被自然分成了“先算出系数模式”和“再做模意义下代入”两大阶段。
设 \(E=6561\)，\(d=19683\)。在这里的位集式表示下，一次次数不超过 \(d\) 的无进位多项式乘法，朴素最坏情况可以看作 \(O(d^2)\) 位操作。二进制快速幂需要 \(O(\log E)\) 次这样的乘法。最后的 Horner 求值只需要 \(O(d)\) 次模乘和模加。内存方面，只需保存当前若干个大多项式，因此空间复杂度是 \(O(d)\) 位。对于本题固定的 \(d=19683\)，这个代价完全在可接受范围内。
Решение рассматривает XOR-умножение как умножение многочленов над \(\mathbb{F}_2\). Гигантское базовое число можно записать в виде
$$T^3+T+1,\qquad T=2^{2^{52}},$$
поэтому задача сводится к построению многочлена
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
в кольце \(\mathbb{F}_2[x]\), а затем к вычислению \(g(T)\) по модулю \(10^9+7\). Такой подход полностью отделяет безпереносную алгебру от заключительной модульной арифметики и не требует оперировать чудовищно большим обычным целым числом.
Во всех трех реализациях используется одна и та же математическая схема: сначала строится многочлен с коэффициентами \(0\) и \(1\), затем в него подставляется значение в модульном кольце.
Если неотрицательное целое имеет двоичное разложение
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
то ему сопоставляется многочлен
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x].$$
В этой модели сложение коэффициентов по модулю \(2\) есть в точности XOR. Поэтому безпереносное умножение целых совпадает с обычным умножением многочленов над \(\mathbb{F}_2[x]\). Если
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j,$$
то коэффициенты произведения удовлетворяют формуле
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j).$$
Именно это тождество превращает XOR-степень в обычную степень многочлена.
Положим
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}.$$
Тогда исходное базовое число равно
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1.$$
То есть реально важен не сам колоссальный десятичный объект, а очень короткий шаблон коэффициентов \((1,1,0,1)\). Если обозначить безпереносное умножение символом \(\otimes\), то XOR-возведение числа \(f(T)\) в степень эквивалентно возведению \(f(x)\) в ту же степень в \(\mathbb{F}_2[x]\), а затем подстановке \(x=T\).
Нужный показатель равен
$$3^8=6561,$$
значит, требуется построить
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x].$$
Программы делают это двоичным возведением в степень. Каждое промежуточное умножение остается безпереносным, поэтому все промежуточные результаты по-прежнему имеют только бинарные коэффициенты. Так как \(\deg f=3\), итоговая степень равна
$$\deg g = 3\cdot 6561 = 19683.$$
Это уже нетривиальный размер, но он ничтожен по сравнению с масштабом, который подразумевает \(2^{2^{52}}\).
После того как многочлен \(g(x)\) построен, остается только численная подстановка. Обозначим
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M.$$
Если записать
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
то искомое значение равно
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M.$$
Здесь вычисление уже происходит не в \(\mathbb{F}_2[x]\), а в \(\mathbb{Z}/M\mathbb{Z}\). Это корректно, потому что коэффициенты многочлена уже окончательно определены и являются обычными числами \(0\) и \(1\). После фиксации коэффициентов один и тот же многочлен можно подставлять в любой подходящий целевой кольцевой контекст.
Маленький пример хорошо показывает, почему безпереносное возведение в квадрат не совпадает с обычным. В поле \(\mathbb{F}_2\) смешанные члены сокращаются попарно, поэтому
$$f(x)^2=(x^3+x+1)^2=x^6+x^2+1.$$
Соответствующий битовый шаблон равен
$$1000101_2,$$
то есть это число \(69\) в десятичной записи. Иначе говоря, безпереносный квадрат шаблона \(1011_2\) равен \(1000101_2\). В полной задаче работает ровно тот же принцип, только показатель равен \(6561\), а финальная подстановка выполняется при \(X\equiv 2^{2^{52}}\pmod M\).
Реализации на C++, Python и Java проходят один и тот же конвейер. Сначала многочлен хранится как большое целое число: если \(k\)-й бит установлен, это означает наличие коэффициента при \(x^k\). Затем безпереносное умножение реализуется обходом установленных битов одного операнда и XOR-наложением сдвинутых копий второго операнда. По сути это знакомая схема «сдвиг и сложение», только сложение заменено на XOR.
После этого двоичное возведение в степень строит \((x^3+x+1)^{6561}\). Далее обычное модульное возведение в степень вычисляет \(2^{2^{52}} \bmod 10^9+7\). Наконец, значение многочлена находится по схеме Горнера от старшего коэффициента к младшему: текущее значение умножается на \(X\), а затем при наличии соответствующего бита добавляется \(1\).
Пусть \(E=6561\), \(d=19683\). В используемом битовом представлении одно безпереносное умножение многочленов степени не выше \(d\) в наившем худшем случае требует \(O(d^2)\) битовых операций. Двоичное возведение в степень использует \(O(\log E)\) таких умножений. Финальная схема Горнера выполняется за \(O(d)\) модульных операций. Память составляет \(O(d)\) бит для текущих больших многочленов. Для конкретных параметров задачи это вполне умеренные затраты.
الفكرة الأساسية في الحل هي اعتبار ضرب XOR على أنه ضرب كثيرات حدود فوق \(\mathbb{F}_2\). يمكن كتابة القيمة الأساسية الضخمة على الصورة
$$T^3+T+1,\qquad T=2^{2^{52}},$$
ولذلك تتحول المسألة إلى بناء كثير الحدود
$$g(x)=(x^3+x+1)^{3^8}=(x^3+x+1)^{6561}$$
داخل \(\mathbb{F}_2[x]\)، ثم تقييم \(g(T)\) بترديد \(10^9+7\). بهذا نفصل تمامًا بين جبر الضرب دون حمل وبين الحساب العددي النهائي تحت الترديد، ولا نحتاج إلى التعامل مباشرة مع العدد الفلكي الناتج من \(2^{2^{52}}\).
التنفيذات الثلاثة تتبع التحليل نفسه: أولًا نبني كثير حدود بمعاملات ثنائية، ثم نستبدل المتغير بقيمة معيارية مناسبة.
إذا كان لدينا عدد صحيح غير سالب بتمثيل ثنائي
$$n=\sum_{k\ge 0} b_k 2^k,\qquad b_k\in\{0,1\},$$
فنربطه بكثير الحدود
$$P_n(x)=\sum_{k\ge 0} b_k x^k \in \mathbb{F}_2[x].$$
في هذا النموذج، جمع المعاملات بترديد \(2\) هو نفسه عملية XOR. لذلك فإن الضرب دون حمل للأعداد يطابق الضرب العادي لكثيرات الحدود فوق \(\mathbb{F}_2[x]\). فإذا كان
$$A(x)=\sum_i a_i x^i,\qquad B(x)=\sum_j b_j x^j,$$
فإن معاملات الناتج تحقق
$$c_k=\left(\sum_{i+j=k} a_i b_j\right)\bmod 2=\bigoplus_{i+j=k}(a_i\land b_j).$$
وهذه هي الملاحظة التي تجعل قوة XOR قابلة للحساب على شكل قوة لكثير حدود.
لنعرّف
$$f(x)=x^3+x+1,\qquad T=2^{2^{52}}.$$
عندئذ يكون العدد الأساسي المطلوب هو بالضبط
$$f(T)=T^3+T+1=2^{3\cdot 2^{52}}+2^{2^{52}}+1.$$
إذن ما نحتاج إليه فعليًا ليس العدد الهائل نفسه، بل النمط القصير للمعاملات \((1,1,0,1)\). وإذا رمزنا للضرب دون حمل بالرمز \(\otimes\)، فإن رفع العدد \(f(T)\) إلى قوة XOR يكافئ رفع \(f(x)\) إلى القوة نفسها داخل \(\mathbb{F}_2[x]\)، ثم التعويض بـ \(x=T\) في النهاية.
الأس المطلوب هو
$$3^8=6561,$$
ولذلك نبني
$$g(x)=f(x)^{6561}\in \mathbb{F}_2[x].$$
يُنفَّذ ذلك باستخدام الأس السريع الثنائي. كل عملية ضرب وسيطة تبقى ضربًا دون حمل، ولذلك تبقى جميع النتائج المرحلية كثيرات حدود ذات معاملات \(0\) أو \(1\). وبما أن \(\deg f=3\)، فإن درجة الناتج النهائي هي
$$\deg g = 3\cdot 6561 = 19683.$$
هذا الحجم ليس صغيرًا جدًا، لكنه ما زال ضئيلًا مقارنة بالحجم الخام الذي يوحي به التعبير \(2^{2^{52}}\).
بعد تحديد \(g(x)\)، يتبقى التعويض العددي فقط. لنكتب
$$M=10^9+7,\qquad X\equiv T\equiv 2^{2^{52}}\pmod M.$$
إذا كان
$$g(x)=\sum_{k=0}^{19683} g_k x^k,\qquad g_k\in\{0,1\},$$
فإن القيمة المطلوبة هي
$$g(X)\equiv \sum_{k=0}^{19683} g_k X^k \pmod M.$$
لاحظ أن بناء كثير الحدود تم فوق \(\mathbb{F}_2[x]\)، أما هذا التعويض فيجري داخل \(\mathbb{Z}/M\mathbb{Z}\). الانتقال صحيح لأن معاملات كثير الحدود قد حُددت مسبقًا وهي مجرد \(0\) و\(1\). بعد تثبيت هذه المعاملات يمكن تفسير كثير الحدود نفسه داخل أي حلقة مناسبة للتقييم.
مثال بسيط يوضح الفرق بين التربيع دون حمل والتربيع المعتاد. داخل \(\mathbb{F}_2\) تلغى الحدود المتقاطعة لأنها تظهر مرتين، ومن ثم
$$f(x)^2=(x^3+x+1)^2=x^6+x^2+1.$$
ونمط البتات الموافق هو
$$1000101_2,$$
أي العدد \(69\) بالعشري. بمعنى آخر، مربع النمط \(1011_2\) تحت الضرب دون حمل هو \(1000101_2\). في المسألة الكاملة تجري القاعدة نفسها تمامًا، لكن مع الأس \(6561\) بدلًا من \(2\)، ثم يجري التعويض عند \(X\equiv 2^{2^{52}}\pmod M\).
التنفيذات في C++ وPython وJava تسير بالمراحل نفسها. أولًا يُخزَّن كثير الحدود على هيئة عدد صحيح كبير بحيث يشير البت رقم \(k\) إلى وجود المعامل عند \(x^k\). بعد ذلك تُنفَّذ عملية الضرب دون حمل عبر المرور على البتات المضبوطة في أحد العاملين، ثم إجراء XOR لنسخ مزاحة من العامل الآخر. هذه هي فكرة "ازح ثم اجمع" المعتادة، لكن عملية الجمع هنا استبدلت بـ XOR.
بعد ذلك يبني الأس السريع كثير الحدود \((x^3+x+1)^{6561}\). ثم يُحسب \(2^{2^{52}} \bmod 10^9+7\) بالأس المعياري المعتاد. وأخيرًا يتم تقييم كثير الحدود باستخدام طريقة هورنر من أعلى درجة إلى أدناها: في كل خطوة نضرب القيمة الحالية في \(X\)، وإذا كان معامل الدرجة الحالية موجودًا نضيف \(1\).
إذا وضعنا \(E=6561\) و\(d=19683\)، فإن ضربة واحدة دون حمل بين كثيري حدود درجتهما في حدود \(d\) تكلف في أسوأ تحليل ساذج \(O(d^2)\) عملية بت. ويحتاج الأس السريع إلى \(O(\log E)\) عملية ضرب من هذا النوع. أما تقييم هورنر النهائي فيكلف \(O(d)\) عمليات معيارية. واستهلاك الذاكرة هو \(O(d)\) بتات لتخزين القيم المرحلية الكبيرة. لهذه المعطيات المحددة يبقى التنفيذ عمليًا جدًا.