The implementations first collapse the original three-operator expression with the identity
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
So the target quantity can be written as
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr),$$
where \(\operatorname{OR}\) denotes bitwise OR. The real input is \(n=10^{18}\), so a direct double loop is hopeless. The solution therefore derives recurrences that replace \(n\) by roughly \(n/2\) at every step.
Introduce the diagonal sum
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
and its prefix sum
$$Q(n)=\sum_{x=0}^{n}T(x).$$
Then the desired answer is simply
$$G(n)=2Q(n).$$
Writing integers as \(2a\) or \(2a+1\) isolates the least significant bit. The four cases are
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
Each identity strips off one binary digit and replaces the original pair by a smaller pair. That is the key divide-and-conquer observation.
Take an even argument \(x=2m\). The pairs \((k,2m-k)\) split into even-even and odd-odd cases.
If \(k=2a\), then \(2m-k=2(m-a)\), so the contribution is \(2\operatorname{OR}(a,m-a)\).
If \(k=2a+1\), then \(2m-k=2(m-a-1)+1\), so the contribution is \(2\operatorname{OR}(a,m-a-1)+1\).
Summing both families gives
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$$
For an odd argument \(x=2m+1\), every pair has opposite parity, and both parity orders reduce to the same smaller problem. Therefore
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$$
Since \(Q(n)\) is the prefix sum of \(T\), an even index can be grouped by parity:
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
Substituting the formulas from Step 2 and collecting the repeated terms yields
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$$
For odd indices, start from \(Q(2m+1)=Q(2m)+T(2m+1)\). Because
$$T(m)=Q(m)-Q(m-1),$$
the odd case simplifies to
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
The whole computation is determined by the zero boundary rule
$$T(n)=Q(n)=0 \qquad \text{for } n\le 0,$$
together with
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
The polynomial parts are always integers: \(m(m+1)\) is even, and \(3m^2+7m+4 \equiv m(m+1)\pmod 2\) is even as well. This is why the modular implementation can safely replace division by \(2\) with multiplication by the modular inverse of \(2\).
Start from the small diagonal values:
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
The even recurrence then gives
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$$
For the prefix sums, one obtains
$$Q(4)=35,\qquad Q(5)=61,$$
so
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
Finally,
$$G(10)=2Q(10)=754,$$
which matches the checkpoint used by the implementations. A second checkpoint is \(G(100)=583766\).
The C++, Python, and Java implementations memoize the pair \((T(n),Q(n))\) for each requested argument. When a new state is needed, they first evaluate the two smaller states at \(\lfloor n/2\rfloor\) and \(\lfloor n/2\rfloor-1\), then apply the even or odd formula above.
All arithmetic is performed modulo \(10^9+7\). The coefficients involving \(\frac{1}{2}\) are handled by multiplying with the modular inverse of \(2\), so the recurrence remains exact in modular arithmetic.
Once the memoized prefix value \(Q(n)\) is known, the final answer is returned as \(2Q(n)\bmod 10^9+7\).
Each recurrence step replaces \(n\) by \(\lfloor n/2\rfloor\) or \(\lfloor n/2\rfloor-1\), so only a logarithmic number of distinct arguments are memoized. That gives \(O(\log n)\) time and \(O(\log n)\) memory. The direct definition, by contrast, needs \(\Theta(n^2)\) bitwise evaluations.
Die Implementierungen reduzieren den ursprünglichen Ausdruck mit drei bitweisen Operatoren zuerst mittels der Identität
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
Damit lässt sich die Zielgröße als
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
schreiben, wobei \(\operatorname{OR}\) das bitweise Oder bezeichnet. Für den echten Eingabewert \(n=10^{18}\) ist eine direkte Doppelsumme aussichtslos, daher wird eine Rekursion hergeleitet, die das Argument in jedem Schritt ungefähr halbiert.
Wir definieren zunächst die Diagonalsumme
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
und ihre Präfixsumme
$$Q(n)=\sum_{x=0}^{n}T(x).$$
Dann gilt sofort
$$G(n)=2Q(n).$$
Schreibt man ganze Zahlen als \(2a\) oder \(2a+1\), wird das niederwertigste Bit isoliert. Die vier Fälle lauten
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
Jede dieser Formeln entfernt genau ein Binärdigit und ersetzt das ursprüngliche Paar durch ein kleineres Paar. Darauf beruht der gesamte Divide-and-Conquer-Schritt.
Betrachte zunächst einen geraden Wert \(x=2m\). Die Paare \((k,2m-k)\) zerfallen dann in gerade-gerade und ungerade-ungerade Fälle.
Für \(k=2a\) ist \(2m-k=2(m-a)\), also entsteht der Beitrag \(2\operatorname{OR}(a,m-a)\).
Für \(k=2a+1\) ist \(2m-k=2(m-a-1)+1\), also entsteht der Beitrag \(2\operatorname{OR}(a,m-a-1)+1\).
Die Summe beider Familien ergibt
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$$
Für einen ungeraden Wert \(x=2m+1\) haben alle Paare unterschiedliche Parität, und beide Paritätsordnungen führen auf dasselbe kleinere Teilproblem. Also gilt
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$$
Da \(Q(n)\) die Präfixsumme von \(T\) ist, kann man den geraden Fall nach Parität gruppieren:
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
Setzt man die Formeln aus Schritt 2 ein und fasst gleiche Summanden zusammen, erhält man
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$$
Für ungerade Indizes benutzt man \(Q(2m+1)=Q(2m)+T(2m+1)\). Mit
$$T(m)=Q(m)-Q(m-1)$$
vereinfacht sich der ungerade Fall zu
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
Die gesamte Rechnung ist also durch die Nullrandbedingung
$$T(n)=Q(n)=0 \qquad \text{für } n\le 0$$
sowie durch
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}$$
festgelegt. Die Polynomterme sind stets ganzzahlig: \(m(m+1)\) ist gerade, und \(3m^2+7m+4 \equiv m(m+1)\pmod 2\) ist ebenfalls gerade. Deshalb kann die Implementierung die Division durch \(2\) modulo \(10^9+7\) als Multiplikation mit dem modularen Inversen von \(2\) ausführen.
Beginnen wir mit kleinen Diagonalwerten:
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
Dann liefert die gerade Rekurrenz
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$$
Für die Präfixsummen erhält man
$$Q(4)=35,\qquad Q(5)=61,$$
also
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
Schließlich folgt
$$G(10)=2Q(10)=754,$$
genau der Kontrollwert der Implementierungen. Ein zweiter Kontrollwert ist \(G(100)=583766\).
Die C++-, Python- und Java-Implementierungen memoizieren für jedes angefragte Argument das Paar \((T(n),Q(n))\). Wenn ein neuer Zustand benötigt wird, werden zuerst die beiden kleineren Zustände bei \(\lfloor n/2\rfloor\) und \(\lfloor n/2\rfloor-1\) berechnet; danach wird die passende Formel für gerades oder ungerades \(n\) angewendet.
Die gesamte Arithmetik läuft modulo \(10^9+7\). Faktoren der Form \(\frac{1}{2}\) werden durch Multiplikation mit dem modularen Inversen von \(2\) umgesetzt, sodass die Rekursion auch modulo \(10^9+7\) exakt bleibt.
Sobald der memoizierte Präfixwert \(Q(n)\) vorliegt, wird das Endergebnis als \(2Q(n)\bmod 10^9+7\) ausgegeben.
Jeder Rekurrenzschritt ersetzt \(n\) durch \(\lfloor n/2\rfloor\) oder \(\lfloor n/2\rfloor-1\). Dadurch werden nur logarithmisch viele verschiedene Argumente memoisiert. Das ergibt \(O(\log n)\) Zeit und \(O(\log n)\) Speicher. Die direkte Definition benötigt dagegen \(\Theta(n^2)\) bitweise Auswertungen.
Uygulamalar önce üç bit işlemini içeren özgün ifadeyi şu özdeşlikle sadeleştirir:
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
Böylece hedef büyüklük
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
şeklinde yazılabilir; burada \(\operatorname{OR}\) bit düzeyinde OR işlemini gösterir. Gerçek girdi \(n=10^{18}\) olduğundan doğrudan çift döngü mümkün değildir. Çözüm bu yüzden her adımda argümanı yaklaşık yarıya indiren reküranslar kurar.
Önce köşegen toplamını
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
ve bunun önek toplamını
$$Q(n)=\sum_{x=0}^{n}T(x)$$
tanımlayalım. O zaman aranan değer
$$G(n)=2Q(n)$$
olur.
Tamsayıları \(2a\) veya \(2a+1\) biçiminde yazmak en düşük anlamlı biti ayırır. Dört temel durum şunlardır:
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
Her formül bir ikili basamağı sıyırır ve büyük problemi daha küçük bir çifte indirger. Böl-ve-yönet adımı tam olarak bundan doğar.
\(x=2m\) olsun. Bu durumda \((k,2m-k)\) çiftleri çift-çift ve tek-tek olmak üzere iki aileye ayrılır.
\(k=2a\) ise \(2m-k=2(m-a)\) olur ve katkı \(2\operatorname{OR}(a,m-a)\) gelir.
\(k=2a+1\) ise \(2m-k=2(m-a-1)+1\) olur ve katkı \(2\operatorname{OR}(a,m-a-1)+1\) gelir.
İki aileyi topladığımızda
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m \end{aligned}$$
elde edilir. \(x=2m+1\) tek olduğunda her çift farklı paritededir ve iki parite sırası da aynı küçük probleme iner. Dolayısıyla
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1) \end{aligned}$$
olur.
\(Q(n)\), \(T\)'nin önek toplamı olduğundan çift durumda terimleri pariteye göre gruplayabiliriz:
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
Adım 2'deki formülleri yerine koyup benzer terimleri toplarsak
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}$$
çıkar. Tek durumda önce \(Q(2m+1)=Q(2m)+T(2m+1)\) yazılır. Ayrıca
$$T(m)=Q(m)-Q(m-1)$$
olduğundan sadeleştirme sonunda
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}$$
elde edilir.
Tüm hesap artık şu sıfır sınır koşulu ile belirlenir:
$$T(n)=Q(n)=0 \qquad \text{for } n\le 0,$$
ve buna ek olarak
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
Polinom parçaları her zaman tam sayıdır: \(m(m+1)\) çifttir ve \(3m^2+7m+4 \equiv m(m+1)\pmod 2\) olduğu için o da çifttir. Bu yüzden mod \(10^9+7\) altında bölü \(2\) işlemi, \(2\)'nin modüler tersiyle çarpma olarak güvenle uygulanabilir.
Küçük köşegen değerleriyle başlayalım:
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
Çift durum reküransı
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89$$
sonucunu verir. Önek toplamlar için
$$Q(4)=35,\qquad Q(5)=61,$$
dolayısıyla
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
Son olarak
$$G(10)=2Q(10)=754$$
elde edilir; bu, uygulamalardaki kontrol değeriyle aynıdır. İkinci bir kontrol noktası da \(G(100)=583766\) değeridir.
C++, Python ve Java uygulamaları her istenen argüman için \((T(n),Q(n))\) çiftini memoize eder. Yeni bir durum gerektiğinde önce \(\lfloor n/2\rfloor\) ve \(\lfloor n/2\rfloor-1\) durumları hesaplanır, ardından \(n\)'nin çift ya da tek olmasına göre uygun formül uygulanır.
Tüm aritmetik işlemler \(10^9+7\) modunda yapılır. \(\frac{1}{2}\) içeren katsayılar, \(2\)'nin modüler tersiyle çarpılarak değerlendirilir; böylece rekürans modüler aritmetikte de tam doğrulukla korunur.
Memoize edilmiş \(Q(n)\) değeri elde edilince nihai cevap \(2Q(n)\bmod 10^9+7\) olarak döndürülür.
Her rekürans adımı \(n\)'yi \(\lfloor n/2\rfloor\) ya da \(\lfloor n/2\rfloor-1\) biçimine indirir. Bu nedenle memoize edilen farklı argüman sayısı logaritmiktir. Sonuç olarak zaman \(O(\log n)\), bellek \(O(\log n)\) olur. Doğrudan tanım ise \(\Theta(n^2)\) adet bit işlemi gerektirir.
Las implementaciones primero simplifican la expresión original con tres operadores bit a bit mediante la identidad
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
Asi, la cantidad buscada puede escribirse como
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr),$$
donde \(\operatorname{OR}\) significa OR bit a bit. Como el valor real es \(n=10^{18}\), una doble suma directa es inviable. La idea es derivar recurrencias que sustituyen \(n\) por un argumento de tamano cercano a \(n/2\) en cada paso.
Definimos la suma sobre una sola diagonal
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
y su suma prefija
$$Q(n)=\sum_{x=0}^{n}T(x).$$
Entonces la respuesta buscada es
$$G(n)=2Q(n).$$
Escribir cada entero como \(2a\) o \(2a+1\) aísla el bit menos significativo. Los cuatro casos básicos son
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
Cada identidad elimina un bit binario y reemplaza el par grande por un par mas pequeno. De ahi nace toda la estrategia de divide y venceras.
Tomemos primero un argumento par \(x=2m\). Los pares \((k,2m-k)\) se dividen en casos par-par e impar-impar.
Si \(k=2a\), entonces \(2m-k=2(m-a)\) y la contribucion es \(2\operatorname{OR}(a,m-a)\).
Si \(k=2a+1\), entonces \(2m-k=2(m-a-1)+1\) y la contribucion es \(2\operatorname{OR}(a,m-a-1)+1\).
Al sumar ambas familias obtenemos
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$$
Si \(x=2m+1\) es impar, cada par tiene paridades opuestas y ambos ordenes llevan al mismo subproblema pequeno. Por tanto
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$$
Como \(Q(n)\) es la suma prefija de \(T\), para un indice par podemos reagrupar por paridad:
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
Sustituyendo las formulas del paso 2 y reuniendo terminos iguales se llega a
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$$
Para indices impares usamos \(Q(2m+1)=Q(2m)+T(2m+1)\). Como
$$T(m)=Q(m)-Q(m-1),$$
el caso impar se simplifica a
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
Todo el calculo queda determinado por la condicion de frontera
$$T(n)=Q(n)=0 \qquad \text{para } n\le 0,$$
junto con
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
Las partes polinomicas siempre son enteras: \(m(m+1)\) es par y \(3m^2+7m+4 \equiv m(m+1)\pmod 2\) tambien es par. Por eso la implementacion puede reemplazar la division por \(2\) por una multiplicacion con el inverso modular de \(2\) modulo \(10^9+7\).
Empezamos con algunos valores pequenos de diagonal:
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
La recurrencia par da
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$$
Para las sumas prefijas se obtiene
$$Q(4)=35,\qquad Q(5)=61,$$
y por tanto
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
Finalmente,
$$G(10)=2Q(10)=754,$$
que coincide con el punto de control usado por las implementaciones. Un segundo control es \(G(100)=583766\).
Las implementaciones en C++, Python y Java memorizan el par \((T(n),Q(n))\) para cada argumento que se necesita. Cuando aparece un estado nuevo, primero calculan los dos estados menores en \(\lfloor n/2\rfloor\) y \(\lfloor n/2\rfloor-1\), y luego aplican la formula adecuada segun \(n\) sea par o impar.
Toda la aritmetica se realiza modulo \(10^9+7\). Los coeficientes con \(\frac{1}{2}\) se tratan multiplicando por el inverso modular de \(2\), de modo que la recurrencia sigue siendo exacta en aritmetica modular.
Una vez conocido el valor memorizado \(Q(n)\), la respuesta final se devuelve como \(2Q(n)\bmod 10^9+7\).
Cada paso recursivo reemplaza \(n\) por \(\lfloor n/2\rfloor\) o \(\lfloor n/2\rfloor-1\), asi que solo se memorizan un numero logaritmico de argumentos distintos. Eso produce tiempo \(O(\log n)\) y memoria \(O(\log n)\). La definicion directa, en cambio, requiere \(\Theta(n^2)\) evaluaciones bit a bit.
这道题在实现中先利用一个非常关键的恒等式，把原本涉及三个按位运算的表达式压缩成只含按位 OR 的形式：
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
因此目标量可以改写为
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr),$$
其中 \(\operatorname{OR}\) 表示按位 OR。真正需要计算的是 \(n=10^{18}\)，所以任何按定义进行的双重枚举都完全不可行。核心思路是推导出一组递推式，使每一步都把参数缩小到大约一半。
先定义单条对角线上的和
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
以及它的前缀和
$$Q(n)=\sum_{x=0}^{n}T(x).$$
这样原题所需结果就是
$$G(n)=2Q(n).$$
所以问题被分成两层：先研究固定 \(x\) 时的对角线和 \(T(x)\)，再把这些对角线和累加成前缀和 \(Q(n)\)。
把整数写成 \(2a\) 或 \(2a+1\) 的形式，可以直接观察最低有效位在按位 OR 下怎样变化。四种基本情况是
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
这些式子表达的是同一件事：把两个数同时右移一位后，原问题会缩成一个更小的 OR 问题，而最低位只会额外贡献 \(0\) 或 \(1\)。这正是递归能够成立的根本原因。
先看偶数情形 \(x=2m\)。此时所有配对 \((k,2m-k)\) 会自然分成两类：
第一类是 \(k=2a\)，于是另一项是 \(2m-k=2(m-a)\)，对应贡献为 \(2\operatorname{OR}(a,m-a)\)。
第二类是 \(k=2a+1\)，于是另一项变成 \(2m-k=2(m-a-1)+1\)，对应贡献为 \(2\operatorname{OR}(a,m-a-1)+1\)。
把两类全部相加，可以得到
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$$
再看奇数情形 \(x=2m+1\)。这时每一对 \((k,2m+1-k)\) 必然一奇一偶，两种顺序在缩小后都会落到同一个小问题 \(\operatorname{OR}(a,m-a)\) 上，只是每一项都会额外带来一个最低位 \(1\)。于是
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$$
到这里，固定一条对角线的求和就已经被压缩成更小规模的同类问题了。
真正要输出的是 \(Q(n)\)，所以还需要把单条对角线的递推升级成前缀和递推。对于偶数指标，按奇偶分组可写成
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
把上一步得到的 \(T(2j)\) 与 \(T(2j+1)\) 公式代入，并把相同的前缀项合并，便得到
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$$
对于奇数指标，可以先写
$$Q(2m+1)=Q(2m)+T(2m+1).$$
又因为
$$T(m)=Q(m)-Q(m-1),$$
所以将前面的公式继续代入后，奇数情形化简为
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
这样一来，最终答案 \(Q(n)\) 也完全可以通过折半递归来求。
整个计算只需要下面这套边界条件和递推式：
$$T(n)=Q(n)=0 \qquad \text{当 } n\le 0,$$
以及
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
这里两个带 \(\frac{1}{2}\) 的多项式项其实始终都是整数。原因很简单：\(m(m+1)\) 一定是偶数，而
$$3m^2+7m+4 \equiv m(m+1)\pmod 2,$$
所以它也一定是偶数。这一点保证了在模 \(10^9+7\) 下可以安全地用 \(2\) 的模逆元来处理除以 \(2\)。
先从几个较小的对角线值出发：
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
于是偶数递推立刻给出
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$$
再看前缀和。由前面的递推可以算到
$$Q(4)=35,\qquad Q(5)=61.$$
代入偶数前缀公式，得到
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
最终答案就是
$$G(10)=2Q(10)=754.$$
这个值与实现中的校验点完全一致。实现还验证了另一个检查值：\(G(100)=583766\)。这说明递推不仅形式上正确，而且和直接计算的小规模结果严格一致。
C++、Python 和 Java 实现都对每个需要的参数 \(n\) 记忆化保存一对值 \((T(n),Q(n))\)。当某个状态首次出现时，程序先递归计算 \(\lfloor n/2\rfloor\) 与 \(\lfloor n/2\rfloor-1\) 这两个更小状态，再根据 \(n\) 的奇偶套用对应公式。
全部运算都在模 \(10^9+7\) 下进行。公式中的 \(\frac{1}{2}\) 不直接做整数除法，而是改成乘以 \(2\) 的模逆元，这样既能保持数学上的等价性，也能保证实现层面的稳定性。
一旦前缀量 \(Q(n)\) 被求出，最终返回的就是 \(2Q(n)\bmod 10^9+7\)。三种语言的实现思路完全一致，只是语法细节不同。
每次递归都会把参数替换成 \(\lfloor n/2\rfloor\) 或 \(\lfloor n/2\rfloor-1\)，因此被记忆化的不同状态数量只有对数级。总时间复杂度为 \(O(\log n)\)，额外空间复杂度也是 \(O(\log n)\)。相比之下，直接根据定义计算需要 \(\Theta(n^2)\) 次按位运算，二者差距极大。
Реализации сначала сводят исходное выражение с тремя побитовыми операторами к более простой форме с помощью тождества
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
После этого искомая величина записывается как
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr),$$
где \(\operatorname{OR}\) означает побитовое OR. Для реального значения \(n=10^{18}\) прямое вычисление двойной суммы невозможно, поэтому решение строит рекуррентные формулы, которые на каждом шаге заменяют \(n\) примерно на \(n/2\).
Введём сумму по одной диагонали
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
и её префиксную сумму
$$Q(n)=\sum_{x=0}^{n}T(x).$$
Тогда ответ задачи равен
$$G(n)=2Q(n).$$
Если представить числа в виде \(2a\) или \(2a+1\), то младший бит отделяется сразу. Получаем четыре базовых случая:
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
Каждая формула снимает один двоичный разряд и заменяет исходную пару меньшей парой. Именно это делает возможным рекурсивное деление пополам.
Рассмотрим сначала чётный аргумент \(x=2m\). Пары \((k,2m-k)\) распадаются на два типа: чётный-чётный и нечётный-нечётный.
Если \(k=2a\), то \(2m-k=2(m-a)\), и вклад равен \(2\operatorname{OR}(a,m-a)\).
Если \(k=2a+1\), то \(2m-k=2(m-a-1)+1\), и вклад равен \(2\operatorname{OR}(a,m-a-1)+1\).
Суммируя обе семьи, получаем
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$$
Для нечётного аргумента \(x=2m+1\) каждая пара имеет разные чётности, а оба порядка сводятся к одной и той же меньшей задаче. Поэтому
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$$
Поскольку \(Q(n)\) есть префиксная сумма от \(T\), для чётного индекса можно сгруппировать слагаемые по чётности:
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
Подставляя формулы из шага 2 и объединяя одинаковые префиксные суммы, получаем
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$$
Для нечётных индексов используем равенство \(Q(2m+1)=Q(2m)+T(2m+1)\). Так как
$$T(m)=Q(m)-Q(m-1),$$
после подстановки и упрощения выходит
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
Всё вычисление определяется нулевым граничным правилом
$$T(n)=Q(n)=0 \qquad \text{при } n\le 0,$$
вместе с формулами
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
Полиномиальные добавки всегда целые: \(m(m+1)\) чётно, а \(3m^2+7m+4 \equiv m(m+1)\pmod 2\), значит и это выражение тоже чётно. Поэтому в вычислениях по модулю \(10^9+7\) деление на \(2\) можно заменить умножением на обратный по модулю элемент.
Начнём с нескольких небольших значений на диагоналях:
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
Тогда из чётной рекурсии следует
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$$
Для префиксных сумм получаем
$$Q(4)=35,\qquad Q(5)=61,$$
и потому
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
Следовательно,
$$G(10)=2Q(10)=754,$$
что точно совпадает с контрольным значением в реализациях. Второй контрольный пример: \(G(100)=583766\).
Реализации на C++, Python и Java мемоизируют пару \((T(n),Q(n))\) для каждого нужного аргумента. Когда требуется новый состояние, сначала рекурсивно вычисляются два меньших состояния \(\lfloor n/2\rfloor\) и \(\lfloor n/2\rfloor-1\), после чего применяется формула для чётного или нечётного \(n\).
Вся арифметика ведётся по модулю \(10^9+7\). Коэффициенты с \(\frac{1}{2}\) обрабатываются через умножение на обратный по модулю элемент к числу \(2\), поэтому рекуррентные формулы сохраняют точность и в модульной арифметике.
Когда вычислено мемоизированное значение \(Q(n)\), окончательный ответ возвращается как \(2Q(n)\bmod 10^9+7\).
На каждом шаге рекурсия заменяет \(n\) на \(\lfloor n/2\rfloor\) или \(\lfloor n/2\rfloor-1\), поэтому число различных мемоизированных аргументов растёт только логарифмически. Отсюда время \(O(\log n)\) и память \(O(\log n)\). Прямое вычисление по определению, напротив, требует \(\Theta(n^2)\) побитовых операций.
تبدأ التطبيقات بتحويل التعبير الأصلي الذي يجمع بين ثلاثة معاملات بتية إلى صيغة أبسط باستعمال الهوية
$$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$$
وبذلك تصبح الكمية المطلوبة
$$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr),$$
حيث تمثل \(\operatorname{OR}\) عملية OR البتية. وبما أن القيمة الحقيقية هي \(n=10^{18}\)، فإن أي جمع مباشر مزدوج غير عملي تماما. لذلك تبني الفكرة مجموعة من العلاقات العودية التي تستبدل \(n\) بقيمة تقارب \(n/2\) في كل خطوة.
نعرف أولا مجموع القطر الواحد
$$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$$
ثم نعرف مجموعه التراكمي
$$Q(n)=\sum_{x=0}^{n}T(x).$$
عندها تكون الإجابة المطلوبة هي ببساطة
$$G(n)=2Q(n).$$
عندما نكتب الأعداد على صورة \(2a\) أو \(2a+1\)، فإننا نعزل البت الأقل أهمية مباشرة. الحالات الأربع الأساسية هي
$$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$$
$$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$$
$$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$$
كل هوية من هذه الهويات تزيل خانة ثنائية واحدة وتحول الزوج الكبير إلى زوج أصغر. هذه هي الفكرة الجوهرية التي تسمح بالتقسيم إلى أنصاف.
لنبدأ بالحالة الزوجية \(x=2m\). عندها تنقسم الأزواج \((k,2m-k)\) إلى حالتين: زوجي-زوجي وفردي-فردي.
إذا كان \(k=2a\)، فإن \(2m-k=2(m-a)\)، وبالتالي يكون الإسهام \(2\operatorname{OR}(a,m-a)\).
وإذا كان \(k=2a+1\)، فإن \(2m-k=2(m-a-1)+1\)، فيكون الإسهام \(2\operatorname{OR}(a,m-a-1)+1\).
بجمع العائلتين نحصل على
$$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$$
أما في الحالة الفردية \(x=2m+1\)، فكل زوج يتكون من عدد زوجي وآخر فردي، وكلا الترتيبين يعودان إلى المسألة الأصغر نفسها. لذا
$$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$$
بما أن \(Q(n)\) هو المجموع التراكمي لقيم \(T\)، فيمكن في الحالة الزوجية إعادة التجميع بحسب الزوجية:
$$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$$
وبتعويض صيغ الخطوة السابقة وتجميع الحدود المتشابهة نحصل على
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$$
وفي الحالة الفردية نبدأ من
$$Q(2m+1)=Q(2m)+T(2m+1).$$
ومع العلاقة
$$T(m)=Q(m)-Q(m-1),$$
يصبح التبسيط النهائي
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
إذن الحساب كله يتحدد بقاعدة الحدود
$$T(n)=Q(n)=0 \qquad (n\le 0).$$
مع العلاقات
$$T(2m)=2T(m)+2T(m-1)+m,$$
$$T(2m+1)=4T(m)+2(m+1),$$
$$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$$
$$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$$
الحدود كثيرات الحدود التي تحتوي على \(\frac{1}{2}\) تظل دائما أعدادا صحيحة، لأن \(m(m+1)\) زوجي، ولأن
$$3m^2+7m+4 \equiv m(m+1)\pmod 2.$$
ولهذا يمكن في الحسابات بترديد \(10^9+7\) استبدال القسمة على \(2\) بالضرب في المعكوس الضربي لـ \(2\) modulo هذا العدد.
نبدأ ببعض القيم الصغيرة لمجاميع الأقطار:
$$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$$
ومن ثم تعطينا العلاقة الزوجية
$$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$$
أما للمجاميع التراكمية فنحصل على
$$Q(4)=35,\qquad Q(5)=61,$$
وبالتالي
$$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$$
إذن الجواب النهائي هو
$$G(10)=2Q(10)=754,$$
وهو تماما قيمة التحقق المستخدمة في التطبيقات. كما يوجد تحقق ثان عند \(G(100)=583766\).
تقوم تطبيقات C++ وPython وJava بحفظ الزوج \((T(n),Q(n))\) لكل قيمة مطلوبة من \(n\) باستخدام التذكر. وعندما تظهر حالة جديدة، تحسب أولا الحالتين الأصغر \(\lfloor n/2\rfloor\) و\(\lfloor n/2\rfloor-1\)، ثم تطبق الصيغة المناسبة بحسب كون \(n\) زوجيا أو فرديا.
كل العمليات الحسابية تنفذ modulo \(10^9+7\). أما الحدود التي تتضمن \(\frac{1}{2}\)، فتتعامل معها التطبيقات عن طريق الضرب في المعكوس الضربي لـ \(2\)، وبذلك تبقى العلاقات الرياضية صحيحة تماما في الحساب المعياري.
وبعد الحصول على القيمة المحفوظة \(Q(n)\)، تعيد الشيفرة النتيجة النهائية على صورة \(2Q(n)\bmod 10^9+7\).
في كل استدعاء عودي يتم استبدال \(n\) بـ \(\lfloor n/2\rfloor\) أو \(\lfloor n/2\rfloor-1\)، ولذلك فإن عدد الحالات المختلفة المحفوظة ينمو لوغاريتميا فقط. وهذا يعطي زمنا \(O(\log n)\) وذاكرة \(O(\log n)\). أما التعريف المباشر فيحتاج إلى \(\Theta(n^2)\) من عمليات OR البتية.