For fixed integers \(k\), \(t\), and \(r\), define
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031.$$
For each integer \(n\) with \(0 \le n < k\), let \(R_n\) be the least nonnegative residue of \(2^n\alpha^r\) modulo \(\beta\), and let
$$D_n = \min(R_n,\beta - R_n).$$
The required value is
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}.$$
The hard part is that \(k\) and \(t\) are enormous, so iterating through all \(n\) directly is impossible. The solution works by expanding \(\alpha^r\), folding powers across the modulus \(2^k+1\), and proving that almost all \(n\)-values inside each interval contribute the same weighted amount.
The implementations use the target value \(r=62\), and the given parameters satisfy \(rt<k\). That inequality is crucial: after expansion, every exponent lies below \(2k\), so any term can cross the \(k\)-boundary at most once.
By the binomial theorem,
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}.$$
Multiplying by \(2^n\) gives
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}.$$
So the entire problem is controlled by the exponents
$$e_i(n)=n+it.$$
Because \(0 \le n < k\) and \(rt<k\), every \(e_i(n)\) lies in the half-open range \([0,2k)\). Therefore each term is either already below \(k\), or it exceeds \(k\) once and can be folded back using the congruence \(2^k\equiv -1 \pmod{\beta}\).
For \(s=1,2,\dots,r\), define
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1].$$
There is also a last interval
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1],$$
which may be empty for some parameters.
If \(n\in I_s\), then exactly the terms with \(i\ge s\) satisfy \(e_i(n)\ge k\), while the terms with \(i<s\) stay below \(k\). Hence
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
and therefore
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}.$$
On the last interval \(I_{r+1}\), nothing folds, so only the first sum remains. This interval decomposition is the key structural simplification: instead of treating each \(n\) separately, we only need to understand one pattern per interval.
Suppose that for some \(n\in I_s\) the centered representative is simply \(D_n=E_s(n)\). Then multiplying by the outer weight gives
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}.$$
The right-hand side no longer depends on \(n\). So every non-exceptional \(n\) in the same interval contributes the same weighted amount.
For the last interval, the constant becomes
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it},$$
again independent of \(n\), whenever the centered residue is taken without switching to \(\beta-R_n\).
This is why the program can add most of the contribution of a huge interval in one bulk step instead of visiting every index inside it.
Fix an interval \(I_s\), and let the leading positive exponent be
$$e_{\max}=n+(s-1)t$$
for \(s\le r\), or \(e_{\max}=n+rt\) on the final interval. Write
$$\delta = k-e_{\max}.$$
When \(\delta \ge 63\), every other term in the signed sum is at least \(2^{63}\) times smaller than the boundary scale \(2^k\), while the total coefficient mass is bounded by
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}.$$
So the leading term dominates and the entire signed value sits strictly between \(0\) and \(\beta/2\). In that regime there is no need to compare \(R_n\) with \(\beta-R_n\): the nearer value is automatically the unreversed one.
Consequently, only the values with \(\delta\le 62\) need exact centered-remainder logic. Those are exactly the last \(62\) positions of each nonempty interval, which is why the implementations peel off that short suffix and treat the earlier part as bulk.
For an exceptional \(n\), let \(j=s-1\) for \(s\le r\), and \(j=r\) on the last interval. The dominant term is
$$\binom{r}{j}2^{k-\delta}.$$
Write the coefficient in base \(2^\delta\):
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta.$$
Then
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q.$$
This identity shows that the exact quotient by \(\beta=2^k+1\) can be read off from the bit shift
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor.$$
After subtracting \(q\beta\), the low bits \(\ell\) determine on which side of \(\beta/2\) the remainder lies. If \(\ell<2^{\delta-1}\), the remainder is below half the modulus. If \(\ell>2^{\delta-1}\), the complementary distance \(\beta-R_n\) is smaller. In the tie case \(\ell=2^{\delta-1}\), the lower-order terms decide the outcome. This is exactly what the implementations evaluate for the short exceptional suffix of each interval.
Here
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9.$$
Since \(r=1\), we only need the values \(n=0,1,2\):
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6. \end{aligned}$$
Therefore
$$F(3,1,1)=24+12+6=42,$$
which matches the validation value used by the implementations.
The C++, Python, and Java implementations all follow the same mathematical plan. They first precompute the binomial coefficients \(\binom{r}{i}\), their values modulo \(M\), and the modular powers \(2^{it}\pmod M\). They also compute \(2^k\pmod M\) and the modular inverse of \(2^k\) modulo \(M\), because folded terms naturally introduce factors of \(2^{-k}\) when everything is tracked directly modulo \(M\).
Next, the implementation forms prefix sums for the unfolded part and suffix sums for the folded part. That makes the constant bulk contribution of an interval available in \(O(1)\) modular time once the interval length is known. Only the last \(62\) values of each interval are handled one by one.
For those exceptional positions, the implementation rebuilds the signed folded expression, extracts the quotient \(q\) from the dominant binomial coefficient by a bit shift, subtracts the corresponding multiple of \(\beta\), decides whether the remainder or its complement is closer to zero, and finally multiplies by the outer factor \(2^{k-n}\). The C++ version parallelizes these independent exceptional evaluations; the Python and Java versions evaluate the same cases sequentially.
There are only \(r+1\) interval patterns. Each interval contributes one bulk term and at most \(62\) exceptional positions. Each exceptional evaluation scans the \(r+1\) binomial terms, so the arithmetic core uses \(O(r^2)\) modular operations and \(O(r)\) memory.
For the target problem \(r=62\) is fixed, so the runtime is effectively constant with respect to the sizes of \(k\) and \(t\); it does not grow linearly with either parameter. The only remaining dependence on their magnitudes comes from modular exponentiation, which costs logarithmic time in the exponent values.
Für feste ganze Zahlen \(k\), \(t\) und \(r\) definieren wir
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031.$$
Für jedes \(n\) mit \(0 \le n < k\) sei \(R_n\) der kleinste nichtnegative Rest von \(2^n\alpha^r\) modulo \(\beta\), und setze
$$D_n = \min(R_n,\beta - R_n).$$
Gesucht ist
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}.$$
Die Schwierigkeit ist, dass \(k\) und \(t\) riesig sind. Eine direkte Schleife über alle \(n\) ist daher ausgeschlossen. Die Lösung zerlegt \(\alpha^r\) binomial, faltet hohe Zweierpotenzen an der Modulusgrenze \(2^k+1\) zurück und zeigt, dass in jedem Intervall fast alle Indizes denselben gewichteten Beitrag liefern.
Die Implementierungen arbeiten mit dem Zielwert \(r=62\), und für die gegebenen Parameter gilt \(rt<k\). Genau dadurch liegt nach der Entwicklung jeder Exponent unter \(2k\), sodass ein Term die Grenze bei \(k\) höchstens einmal überschreitet.
Nach dem binomischen Lehrsatz gilt
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}.$$
Mit dem Faktor \(2^n\) wird daraus
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}.$$
Das Problem wird also vollständig von den Exponenten
$$e_i(n)=n+it$$
gesteuert. Weil \(0 \le n < k\) und \(rt<k\), liegt jedes \(e_i(n)\) im Bereich \([0,2k)\). Damit ist jeder Term entweder schon unterhalb von \(k\), oder er überschreitet \(k\) genau einmal und lässt sich mit \(2^k\equiv -1 \pmod{\beta}\) zurückfalten.
Für \(s=1,2,\dots,r\) definieren wir
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1].$$
Dazu kommt das letzte Intervall
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1],$$
das für manche Parameter leer sein kann.
Gilt \(n\in I_s\), so erfüllen genau die Terme mit \(i\ge s\) die Ungleichung \(e_i(n)\ge k\), während die Terme mit \(i<s\) unterhalb von \(k\) bleiben. Deshalb
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
und damit
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}.$$
Im letzten Intervall \(I_{r+1}\) wird nichts gefaltet, also bleibt nur die erste Summe übrig. Diese Intervallzerlegung ist der zentrale Strukturgewinn: Statt jedes \(n\) einzeln zu behandeln, genügt ein Muster pro Intervall.
Nehmen wir an, für ein \(n\in I_s\) sei der zentrierte Vertreter einfach \(D_n=E_s(n)\). Dann folgt nach Multiplikation mit dem äußeren Gewicht
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}.$$
Die rechte Seite hängt nicht mehr von \(n\) ab. Also liefern alle nicht-ausnahmehaften \(n\) desselben Intervalls denselben gewichteten Beitrag.
Für das letzte Intervall lautet die Konstante
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it},$$
wieder unabhängig von \(n\), sofern kein Wechsel zu \(\beta-R_n\) nötig ist.
Genau deshalb kann das Programm den größten Teil eines riesigen Intervalls in einem einzigen Bulk-Schritt addieren.
Fixiere ein Intervall \(I_s\). Der führende positive Exponent ist
$$e_{\max}=n+(s-1)t$$
für \(s\le r\), beziehungsweise \(e_{\max}=n+rt\) im letzten Intervall. Schreibe
$$\delta = k-e_{\max}.$$
Falls \(\delta \ge 63\), sind alle übrigen Terme im vorzeichenbehafteten Ausdruck mindestens um den Faktor \(2^{63}\) kleiner als die Grenzskala \(2^k\), während die gesamte Koeffizientenmasse durch
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}$$
beschränkt ist. Daher dominiert der führende Term, und der gesamte Wert liegt strikt zwischen \(0\) und \(\beta/2\). In diesem Bereich ist kein Vergleich mit \(\beta-R_n\) mehr nötig: Der nähere Wert ist automatisch der unrevidierte Rest.
Somit brauchen nur die Fälle mit \(\delta\le 62\) eine exakte zentrierte Restberechnung. Das sind genau die letzten \(62\) Positionen jedes nichtleeren Intervalls. Deshalb schneiden die Implementierungen dieses kurze Suffix ab und behandeln den früheren Teil als Bulk.
Für ein Ausnahme-\(n\) sei \(j=s-1\) für \(s\le r\), und \(j=r\) im letzten Intervall. Der dominante Term ist
$$\binom{r}{j}2^{k-\delta}.$$
Schreibe den Koeffizienten zur Basis \(2^\delta\):
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta.$$
Dann gilt
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q.$$
Damit sieht man, dass der exakte Quotient bei Division durch \(\beta=2^k+1\) direkt aus dem Bitshift
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor$$
gewonnen werden kann. Nach Abzug von \(q\beta\) entscheiden die niedrigen Bits \(\ell\), auf welcher Seite von \(\beta/2\) der Rest liegt. Bei \(\ell<2^{\delta-1}\) liegt der Rest unterhalb der Hälfte des Modulus, bei \(\ell>2^{\delta-1}\) ist der komplementäre Abstand \(\beta-R_n\) kleiner. Im Grenzfall \(\ell=2^{\delta-1}\) entscheiden die kleineren Terme. Genau das werten die Implementierungen für das kurze Ausnahme-Suffix jedes Intervalls aus.
Hier ist
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9.$$
Für \(r=1\) genügen die Werte \(n=0,1,2\):
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6. \end{aligned}$$
Also
$$F(3,1,1)=24+12+6=42,$$
genau der Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen alle demselben mathematischen Plan. Zuerst werden die Binomialkoeffizienten \(\binom{r}{i}\), ihre Werte modulo \(M\) und die modularen Potenzen \(2^{it}\pmod M\) vorab berechnet. Zusätzlich werden \(2^k\pmod M\) und das multiplikative Inverse von \(2^k\) modulo \(M\) bestimmt, weil gefaltete Terme beim Arbeiten direkt modulo \(M\) natürlich Faktoren \(2^{-k}\) erzeugen.
Anschließend bildet die Implementierung Präfixsummen für den ungefalteten Teil und Suffixsummen für den gefalteten Teil. So lässt sich der konstante Bulk-Beitrag eines Intervalls in \(O(1)\) modularer Zeit auswerten, sobald die Intervalllänge bekannt ist. Nur die letzten \(62\) Werte jedes Intervalls werden einzeln behandelt.
Für diese Ausnahmepositionen rekonstruiert die Implementierung den vorzeichenbehafteten gefalteten Ausdruck, gewinnt den Quotienten \(q\) per Bitshift aus dem dominanten Binomialkoeffizienten, zieht das entsprechende Vielfache von \(\beta\) ab, entscheidet zwischen Rest und Komplement und multipliziert am Ende mit dem äußeren Faktor \(2^{k-n}\). Die C++-Version parallelisiert diese unabhängigen Ausnahmeauswertungen; Python und Java rechnen dieselben Fälle sequenziell aus.
Es gibt nur \(r+1\) Intervallmuster. Jedes Intervall liefert einen Bulk-Term und höchstens \(62\) Ausnahmepositionen. Jede Ausnahmeauswertung betrachtet die \(r+1\) Binomialterme, daher benötigt der arithmetische Kern \(O(r^2)\) modulare Operationen und \(O(r)\) Speicher.
Im Zielproblem ist \(r=62\) fest, daher ist die Laufzeit praktisch konstant bezüglich der Größen von \(k\) und \(t\); sie wächst insbesondere nicht linear mit diesen Parametern. Die einzige verbleibende Abhängigkeit von ihren Größen entsteht durch modulare Potenzierung und ist logarithmisch in den Exponenten.
Sabit \(k\), \(t\) ve \(r\) tamsayıları için
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031$$
tanımlansın. \(0 \le n < k\) için \(R_n\), \(2^n\alpha^r\) ifadesinin \(\beta\) modundaki en küçük negatif olmayan kalanı olsun ve
$$D_n = \min(R_n,\beta - R_n)$$
olarak tanımlansın. Aranan değer
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}$$
şeklindedir. Asıl zorluk, \(k\) ve \(t\) değerlerinin devasa olmasıdır. Bu yüzden tüm \(n\) değerleri üzerinde doğrudan dolaşmak yerine, çözüm \(\alpha^r\) açılımını yapar, yüksek üsleri \(2^k+1\) modülünde geri katlar ve her aralıkta neredeyse bütün \(n\) değerlerinin aynı ağırlıklı katkıyı verdiğini gösterir.
Uygulamalar hedef problemde \(r=62\) kullanır ve verilen parametrelerde \(rt<k\) eşitsizliği sağlanır. Bu kritik bir noktadır: açılımdan sonra her üs \(2k\)'nin altında kalır, dolayısıyla her terim \(k\) sınırını en fazla bir kez aşar.
Binom teoremine göre
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}.$$
\(2^n\) ile çarpınca
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}$$
elde edilir. Yani problem tamamen şu üslere bağlıdır:
$$e_i(n)=n+it.$$
\(0 \le n < k\) ve \(rt<k\) olduğundan her \(e_i(n)\) değeri \([0,2k)\) aralığındadır. Böylece her terim ya zaten \(k\)'nin altındadır ya da \(k\)'yi bir kez geçer ve \(2^k\equiv -1 \pmod{\beta}\) bağıntısıyla geri katlanır.
\(s=1,2,\dots,r\) için
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1]$$
tanımını yapalım. Buna ek olarak son aralık
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1]$$
vardır; bazı parametrelerde boş olabilir.
Eğer \(n\in I_s\) ise tam olarak \(i\ge s\) olan terimler için \(e_i(n)\ge k\) olur; \(i<s\) olanlar ise \(k\)'nin altında kalır. Bu yüzden
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
ve dolayısıyla
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}.$$
Son aralık \(I_{r+1}\) içinde hiçbir terim katlanmaz, dolayısıyla sadece ilk toplam kalır. Bu aralık ayrımı bütün yöntemin omurgasıdır: her \(n\) için ayrı işlem yapmak yerine, her aralık için tek bir desen incelenir.
Bir \(n\in I_s\) için merkezlenmiş temsilcinin doğrudan \(D_n=E_s(n)\) olduğunu varsayalım. O zaman dış ağırlıkla çarpınca
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}$$
elde edilir. Sağ taraf artık \(n\)'ye bağlı değildir. Demek ki aynı aralıktaki istisna olmayan tüm \(n\) değerleri aynı ağırlıklı katkıyı verir.
Son aralıkta sabit ifade
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it}$$
olur; burada da \(n\)'ye bağlılık yoktur, yeter ki \(\beta-R_n\) tarafına geçmek gerekmemiş olsun.
Bu nedenle kod, çok büyük bir aralığın büyük kısmını tek bir bulk eklemesiyle toplayabilir.
Sabit bir \(I_s\) aralığı alalım. En büyük pozitif üs
$$e_{\max}=n+(s-1)t$$
\(s\le r\) için, son aralıkta ise \(e_{\max}=n+rt\) olur. Şimdi
$$\delta = k-e_{\max}$$
tanımını yapalım. Eğer \(\delta \ge 63\) ise işaretli toplam içindeki diğer bütün terimler, \(2^k\) ölçeğine göre en az \(2^{63}\) kat daha küçüktür; üstelik toplam katsayı kütlesi
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}$$
ile sınırlıdır. Bu durumda başat terim açıkça baskındır ve toplam değer sıkı biçimde \(0\) ile \(\beta/2\) arasına düşer. Yani \(R_n\) ile \(\beta-R_n\) arasında seçim yapmaya gerek kalmaz; yakın olan her zaman doğrudan kalanın kendisidir.
Buna göre yalnızca \(\delta\le 62\) olan durumlarda tam merkezlenmiş kalan hesabı gerekir. Bu da her boş olmayan aralığın tam olarak son \(62\) noktasına karşılık gelir. Uygulamalar bu kısa kuyruğu ayrı işler, erken kısmı ise bulk olarak toplar.
İstisna bir \(n\) için \(s\le r\) olduğunda \(j=s-1\), son aralıkta ise \(j=r\) olsun. Baskın terim
$$\binom{r}{j}2^{k-\delta}$$
şeklindedir. Katsayıyı \(2^\delta\) tabanında yazalım:
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta.$$
O halde
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q.$$
Bu özdeşlik, \(\beta=2^k+1\) ile bölümde gereken tam bölümün
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor$$
şeklindeki basit bit kaydırmasından geldiğini gösterir. \(q\beta\) çıkarıldıktan sonra kalan tarafın \(\beta/2\)'nin hangi yanında olduğunu düşük bitler \(\ell\) belirler. \(\ell<2^{\delta-1}\) ise kalan yarının altındadır; \(\ell>2^{\delta-1}\) ise tamamlayıcı uzaklık \(\beta-R_n\) daha küçüktür. Eşitlik durumunda \(\ell=2^{\delta-1}\), kararı daha küçük dereceli terimler verir. Kod, her aralığın kısa istisna kuyruğunda tam olarak bunu uygular.
Burada
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9$$
olur. \(r=1\) olduğundan sadece \(n=0,1,2\) gerekir:
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6. \end{aligned}$$
Dolayısıyla
$$F(3,1,1)=24+12+6=42$$
elde edilir; bu da uygulamalardaki doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamalarının üçü de aynı matematiksel planı izler. Önce \(\binom{r}{i}\) binom katsayıları, bunların \(M\) modundaki değerleri ve \(2^{it}\pmod M\) kuvvetleri önceden hesaplanır. Ayrıca \(2^k\pmod M\) ve \(2^k\)'nin \(M\) modundaki çarpımsal tersi bulunur; çünkü katlanmış terimler doğrudan \(M\) modunda izlenirken doğal olarak \(2^{-k}\) çarpanları ortaya çıkar.
Daha sonra uygulama, katlanmayan kısım için önek toplamları ve katlanan kısım için sonek toplamları kurar. Böylece bir aralığın sabit bulk katkısı, aralığın uzunluğu bilindiğinde \(O(1)\) modüler zamanda alınabilir. Yalnızca her aralığın son \(62\) değeri tek tek değerlendirilir.
Bu istisna noktalarında uygulama işaretli katlanmış ifadeyi yeniden oluşturur, baskın binom katsayısından bit kaydırmasıyla bölüm \(q\)'yu çıkarır, karşılık gelen \(\beta\) katını düşer, kalanın mı yoksa tamamlayıcısının mı daha yakın olduğunu belirler ve en son \(2^{k-n}\) ile çarpar. C++ sürümü bu bağımsız istisna hesaplarını paralelleştirir; Python ve Java ise aynı mantığı sıralı biçimde uygular.
Yalnızca \(r+1\) farklı aralık deseni vardır. Her aralık bir bulk terimi ve en fazla \(62\) istisna noktası üretir. Her istisna değerlendirmesi \(r+1\) binom terimini taradığı için, aritmetik çekirdek \(O(r^2)\) modüler işlem ve \(O(r)\) bellek kullanır.
Hedef problemde \(r=62\) sabittir. Bu yüzden çalışma süresi, \(k\) ve \(t\) büyüklüklerine göre pratikte sabittir; özellikle bu parametrelerle doğrusal artmaz. Büyüklüklerine bağlı kalan tek maliyet, üslerde logaritmik zaman alan modüler üs alma adımlarıdır.
Para enteros fijos \(k\), \(t\) y \(r\), definimos
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031.$$
Para cada \(n\) con \(0 \le n < k\), sea \(R_n\) el residuo no negativo de \(2^n\alpha^r\) módulo \(\beta\), y sea
$$D_n = \min(R_n,\beta - R_n).$$
El valor pedido es
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}.$$
La dificultad real es que \(k\) y \(t\) son gigantescos. No se puede recorrer todos los \(n\) de forma directa. La solución expande \(\alpha^r\), repliega las potencias altas usando el módulo \(2^k+1\), y demuestra que dentro de cada intervalo casi todos los índices aportan exactamente la misma contribución ponderada.
Las implementaciones usan el valor objetivo \(r=62\), y para los parámetros dados se cumple \(rt<k\). Esa desigualdad es esencial: después de la expansión, cada exponente queda por debajo de \(2k\), así que cada término puede cruzar la frontera \(k\) como máximo una vez.
Por el teorema binomial,
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}.$$
Al multiplicar por \(2^n\), obtenemos
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}.$$
Por lo tanto, todo el problema queda gobernado por los exponentes
$$e_i(n)=n+it.$$
Como \(0 \le n < k\) y \(rt<k\), cada \(e_i(n)\) pertenece al rango \([0,2k)\). Entonces cada término ya está por debajo de \(k\), o bien supera \(k\) una sola vez y se puede replegar mediante \(2^k\equiv -1 \pmod{\beta}\).
Para \(s=1,2,\dots,r\), definimos
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1].$$
Además existe el intervalo final
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1],$$
que puede ser vacío según los parámetros.
Si \(n\in I_s\), exactamente los términos con \(i\ge s\) satisfacen \(e_i(n)\ge k\), mientras que los términos con \(i<s\) se mantienen por debajo de \(k\). Por tanto,
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
y por consiguiente
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}.$$
En el último intervalo \(I_{r+1}\) no se repliega nada, así que solo queda la primera suma. Esta descomposición por intervalos es la simplificación central: en lugar de tratar cada \(n\) por separado, basta estudiar un único patrón por intervalo.
Supongamos que para cierto \(n\in I_s\) el representante centrado es simplemente \(D_n=E_s(n)\). Entonces
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}.$$
El lado derecho ya no depende de \(n\). Así, todos los \(n\) no excepcionales del mismo intervalo aportan la misma cantidad ponderada.
En el intervalo final, la constante toma la forma
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it},$$
también independiente de \(n\), siempre que no sea necesario cambiar a \(\beta-R_n\).
Ese hecho explica por qué el programa puede sumar la mayor parte de un intervalo enorme en un solo bloque.
Fijemos un intervalo \(I_s\). El exponente positivo dominante es
$$e_{\max}=n+(s-1)t$$
para \(s\le r\), o bien \(e_{\max}=n+rt\) en el intervalo final. Definimos
$$\delta = k-e_{\max}.$$
Cuando \(\delta \ge 63\), todos los demás términos de la suma con signo son al menos \(2^{63}\) veces más pequeños que la escala crítica \(2^k\), mientras que la masa total de coeficientes está acotada por
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}.$$
Por ello, el término dominante manda y el valor completo queda estrictamente entre \(0\) y \(\beta/2\). En esa situación no hace falta comparar \(R_n\) con \(\beta-R_n\): el valor más cercano es automáticamente el residuo sin invertir.
Por consiguiente, solo los casos con \(\delta\le 62\) requieren una evaluación exacta del residuo centrado. Eso coincide exactamente con las últimas \(62\) posiciones de cada intervalo no vacío, y por eso las implementaciones separan ese sufijo corto y tratan la parte anterior como bloque masivo.
Para un \(n\) excepcional, tomamos \(j=s-1\) si \(s\le r\), y \(j=r\) en el intervalo final. El término dominante es
$$\binom{r}{j}2^{k-\delta}.$$
Escribimos el coeficiente en base \(2^\delta\):
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta.$$
Entonces
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q.$$
Esta identidad muestra que el cociente exacto al dividir por \(\beta=2^k+1\) se obtiene mediante el desplazamiento
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor.$$
Tras restar \(q\beta\), los bits bajos \(\ell\) indican en qué lado de \(\beta/2\) queda el residuo. Si \(\ell<2^{\delta-1}\), el residuo está por debajo de la mitad del módulo. Si \(\ell>2^{\delta-1}\), la distancia complementaria \(\beta-R_n\) es menor. En el caso límite \(\ell=2^{\delta-1}\), la decisión final la toman los términos de orden inferior. Eso es exactamente lo que evalúan las implementaciones en el sufijo excepcional de cada intervalo.
Aquí
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9.$$
Como \(r=1\), basta con \(n=0,1,2\):
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6. \end{aligned}$$
Por tanto,
$$F(3,1,1)=24+12+6=42,$$
que coincide con el valor de validación usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan matemático. Primero precalculan los coeficientes binomiales \(\binom{r}{i}\), sus valores módulo \(M\), y las potencias modulares \(2^{it}\pmod M\). También calculan \(2^k\pmod M\) y el inverso multiplicativo de \(2^k\) módulo \(M\), porque los términos replegados introducen de forma natural factores \(2^{-k}\) cuando todo se sigue directamente módulo \(M\).
Después, la implementación construye sumas prefijas para la parte no replegada y sumas sufijas para la parte replegada. Así, la contribución constante de un intervalo se obtiene en tiempo modular \(O(1)\) una vez conocida la longitud del bloque. Solo las últimas \(62\) posiciones de cada intervalo se tratan de manera individual.
Para esas posiciones excepcionales, la implementación recompone la expresión replegada con signo, extrae el cociente \(q\) mediante un desplazamiento de bits del coeficiente binomial dominante, resta el múltiplo correspondiente de \(\beta\), decide si es más pequeño el residuo o su complemento, y finalmente multiplica por el factor exterior \(2^{k-n}\). La versión en C++ paraleliza estas evaluaciones independientes; las versiones en Python y Java recorren los mismos casos de forma secuencial.
Solo existen \(r+1\) patrones de intervalo. Cada intervalo aporta un término masivo y como máximo \(62\) posiciones excepcionales. Cada evaluación excepcional recorre los \(r+1\) términos binomiales, así que el núcleo aritmético usa \(O(r^2)\) operaciones modulares y \(O(r)\) memoria.
En el problema objetivo, \(r=62\) es fijo. Por eso el tiempo de ejecución es, en la práctica, constante respecto al tamaño de \(k\) y \(t\); en particular, no crece linealmente con ellos. La única dependencia restante aparece en la exponenciación modular, cuyo coste es logarítmico en el valor del exponente.
对固定整数 \(k\)、\(t\)、\(r\)，定义
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031$$
对每个满足 \(0 \le n < k\) 的整数 \(n\)，令 \(R_n\) 表示 \(2^n\alpha^r\) 对 \(\beta\) 取模后的最小非负余数，并定义
$$D_n = \min(R_n,\beta - R_n)$$
题目要求计算
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}$$
真正的难点在于 \(k\) 和 \(t\) 极大，根本无法逐个遍历所有 \(n\)。因此解法必须重写这个和式：先把 \(\alpha^r\) 展开，再利用模数 \(2^k+1\) 折叠高次幂，最后证明在每个区间里，绝大多数 \(n\) 的加权贡献其实是同一个常数。
实现所用的目标参数是 \(r=62\)，并且给定数据满足 \(rt<k\)。这一点非常关键，因为它保证展开后的每个指数都小于 \(2k\)，所以任意一项至多只会跨过一次 \(k\) 这条边界。
由二项式定理，
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}$$
再乘上 \(2^n\)，得到
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}$$
于是整个问题都被这些指数控制：
$$e_i(n)=n+it$$
由于 \(0 \le n < k\) 且 \(rt<k\)，每个 \(e_i(n)\) 都落在 \([0,2k)\) 内。也就是说，每一项要么本来就在 \(k\) 以下，要么只会超过 \(k\) 一次，然后可以借助
$$2^k\equiv -1 \pmod{\beta}$$
把它折回到较低的幂次。
对 \(s=1,2,\dots,r\)，定义
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1]$$
此外还要考虑最后一个区间
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1]$$
它在某些参数下可能为空。
若 \(n\in I_s\)，那么恰好是 \(i\ge s\) 的那些项满足 \(e_i(n)\ge k\)，而 \(i<s\) 的项仍然低于 \(k\)。因此
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
从而有
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}$$
在最后一个区间 \(I_{r+1}\) 中，没有任何项需要折叠，所以只剩下第一部分求和。这个区间分解是整套方法的核心，因为它把“按 \(n\) 逐点处理”的思路改成了“每个区间只处理一种结构”。
设某个 \(n\in I_s\) 对应的中心化代表就是 \(D_n=E_s(n)\)，也就是不需要改取 \(\beta-R_n\)。那么乘上外层权重后，
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}$$
右边已经完全不含 \(n\)。所以同一个区间中，所有“非边界”的 \(n\) 都会给出完全相同的加权贡献。
在最后一个区间里，对应常数变成
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it}$$
只要此时最近的距离仍然来自 \(R_n\) 本身，而不是它的补数。
这就是程序可以整块累加巨大区间的原因：区间前面的大段位置根本不必逐一计算。
固定一个区间 \(I_s\)。当 \(s\le r\) 时，最大的正幂指数是
$$e_{\max}=n+(s-1)t$$
在最后一个区间中则是
$$e_{\max}=n+rt$$
记
$$\delta = k-e_{\max}$$
如果 \(\delta \ge 63\)，那么带符号和式里的其他所有项，相对于临界尺度 \(2^k\) 都至少小了 \(2^{63}\) 倍；而全部二项式系数的总和至多是
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}$$
因此主导项必然压倒其余项，整个值严格落在 \(0\) 与 \(\beta/2\) 之间。在这种情况下，不需要再比较 \(R_n\) 与 \(\beta-R_n\)：离零最近的一定就是原余数对应的那一边。
于是，只有 \(\delta\le 62\) 时才必须做精确的“中心余数”判断。这恰好对应每个非空区间末尾的 \(62\) 个位置，所以实现把这段短尾巴单独拿出来处理，而把前面的长段直接当作 bulk 常数贡献。
对一个异常位置 \(n\)，若 \(s\le r\)，取 \(j=s-1\)；若位于最后一个区间，则取 \(j=r\)。主导项为
$$\binom{r}{j}2^{k-\delta}$$
把系数写成 \(2^\delta\) 进制：
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta$$
于是
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q$$
这个恒等式说明，除以 \(\beta=2^k+1\) 时所需的整数商其实可以直接由位移得到：
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor$$
减去 \(q\beta\) 以后，低位部分 \(\ell\) 决定余数位于 \(\beta/2\) 的哪一边。若 \(\ell<2^{\delta-1}\)，则余数低于一半；若 \(\ell>2^{\delta-1}\)，则补数距离 \(\beta-R_n\) 更小。若正好 \(\ell=2^{\delta-1}\)，就必须再看更低阶的其余项来打破平局。实现中对每个区间的短尾部正是这样精确处理的。
此时
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9$$
因为 \(r=1\)，只需考察 \(n=0,1,2\)：
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6 \end{aligned}$$
因此
$$F(3,1,1)=24+12+6=42$$
这与实现中使用的校验值完全一致。
C++、Python 和 Java 三个实现都遵循同一套数学方案。首先，它们预计算 \(\binom{r}{i}\) 的精确值、这些值在 \(M\) 模下的结果，以及 \(2^{it}\pmod M\) 的幂。与此同时，还会计算 \(2^k\pmod M\) 以及 \(2^k\) 在 \(M\) 模下的乘法逆元，因为一旦某一项被折叠，直接在 \(M\) 模下跟踪时就会自然出现 \(2^{-k}\) 这样的因子。
接着，实现为“未折叠部分”构造前缀和，为“已折叠部分”构造后缀和。这样一来，只要知道某个区间的长度，就能在 \(O(1)\) 的模运算时间内得到该区间的 bulk 常数贡献。只有每个区间最后的 \(62\) 个位置才需要逐点精算。
对于这些异常位置，实现会重建带符号的折叠表达式，通过主导二项式系数的位移恢复整数商 \(q\)，减去相应倍数的 \(\beta\)，判断应该取余数本身还是取补数更近，最后再乘上外层权重 \(2^{k-n}\)。C++ 版本把这些彼此独立的异常位置并行处理；Python 与 Java 版本则顺序执行同样的计算。
总共只有 \(r+1\) 种区间模式。每个区间贡献一个 bulk 项，以及最多 \(62\) 个异常位置。每次异常位置的精算都要扫描 \(r+1\) 个二项式项，因此核心算术复杂度是 \(O(r^2)\)，所需内存为 \(O(r)\)。
在目标问题中，\(r=62\) 是固定常数，所以运行时间相对于 \(k\) 和 \(t\) 的规模可以看作常数级；它不会随着这两个参数线性增长。对 \(k\) 与 \(t\) 大小的剩余依赖，只体现在模幂计算上，而模幂的时间复杂度是关于指数大小的对数级。
Для фиксированных целых \(k\), \(t\) и \(r\) положим
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031.$$
Для каждого \(n\), где \(0 \le n < k\), обозначим через \(R_n\) наименьший неотрицательный остаток числа \(2^n\alpha^r\) по модулю \(\beta\), и определим
$$D_n = \min(R_n,\beta - R_n).$$
Нужно вычислить
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}.$$
Главная трудность в том, что \(k\) и \(t\) огромны, поэтому прямой перебор по всем \(n\) невозможен. Решение раскрывает \(\alpha^r\) по биному, сворачивает большие степени по модулю \(2^k+1\) и доказывает, что внутри каждого интервала почти все значения \(n\) дают один и тот же взвешенный вклад.
В реализации используется целевое значение \(r=62\), и для заданных параметров выполняется неравенство \(rt<k\). Это принципиально: после раскрытия все показатели остаются меньше \(2k\), так что каждый член может пересечь границу \(k\) не более одного раза.
По биному Ньютона
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}.$$
После умножения на \(2^n\) получаем
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}.$$
Тем самым всё управление задачей переходит к показателям
$$e_i(n)=n+it.$$
Так как \(0 \le n < k\) и \(rt<k\), каждый \(e_i(n)\) лежит в диапазоне \([0,2k)\). Значит, каждый член либо уже ниже \(k\), либо пересекает уровень \(k\) ровно один раз и после этого сворачивается с помощью
$$2^k\equiv -1 \pmod{\beta}.$$
Для \(s=1,2,\dots,r\) определим
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1].$$
Кроме того, есть последний интервал
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1],$$
который при некоторых параметрах может оказаться пустым.
Если \(n\in I_s\), то ровно для индексов \(i\ge s\) выполняется \(e_i(n)\ge k\), а для \(i<s\) степени остаются ниже \(k\). Поэтому
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
и, следовательно,
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}.$$
На последнем интервале \(I_{r+1}\) свёртки нет вовсе, поэтому остаётся только первая сумма. Именно это интервальное представление даёт основной выигрыш: вместо работы с каждым \(n\) по отдельности достаточно понять одну схему для каждого интервала.
Предположим, что для некоторого \(n\in I_s\) центрированный представитель равен просто \(D_n=E_s(n)\), то есть переход к \(\beta-R_n\) не нужен. Тогда
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}.$$
Правая часть уже не зависит от \(n\). Значит, все некраевые значения \(n\) в одном и том же интервале дают одинаковый взвешенный вклад.
Для последнего интервала константа имеет вид
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it},$$
что тоже не зависит от \(n\), пока ближайшее расстояние даёт именно \(R_n\), а не его дополнение.
Именно поэтому программа может прибавлять основную часть длинного интервала одним блоком.
Зафиксируем интервал \(I_s\). Ведущий положительный показатель равен
$$e_{\max}=n+(s-1)t$$
для \(s\le r\), а на последнем интервале \(e_{\max}=n+rt\). Обозначим
$$\delta = k-e_{\max}.$$
Если \(\delta \ge 63\), то все остальные члены знакопеременной суммы как минимум в \(2^{63}\) раз меньше критического масштаба \(2^k\), а суммарная масса коэффициентов ограничена величиной
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}.$$
Следовательно, ведущий член доминирует, и всё выражение строго попадает между \(0\) и \(\beta/2\). В этой области сравнивать \(R_n\) и \(\beta-R_n\) уже не нужно: ближайшим представителем автоматически является невозвращённый остаток.
Значит, точная логика центрированного остатка нужна только при \(\delta\le 62\). Это ровно последние \(62\) позиции каждого непустого интервала, поэтому реализации отделяют этот короткий хвост, а предыдущую часть обрабатывают как bulk-блок.
Для исключительного значения \(n\) положим \(j=s-1\), если \(s\le r\), и \(j=r\) на последнем интервале. Доминирующий член имеет вид
$$\binom{r}{j}2^{k-\delta}.$$
Разложим коэффициент по основанию \(2^\delta\):
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta.$$
Тогда
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q.$$
Из этого сразу видно, что точная целая часть при делении на \(\beta=2^k+1\) считывается обычным сдвигом:
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor.$$
После вычитания \(q\beta\) младшие биты \(\ell\) показывают, по какую сторону от \(\beta/2\) лежит остаток. Если \(\ell<2^{\delta-1}\), остаток ниже половины модуля. Если \(\ell>2^{\delta-1}\), меньшим становится дополнение \(\beta-R_n\). В точном случае \(\ell=2^{\delta-1}\) решение зависит от младших членов. Именно это и вычисляют реализации для короткого исключительного хвоста каждого интервала.
Здесь
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9.$$
Так как \(r=1\), достаточно рассмотреть \(n=0,1,2\):
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6. \end{aligned}$$
Следовательно,
$$F(3,1,1)=24+12+6=42,$$
что совпадает с проверочным значением в реализациях.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они заранее вычисляют биномиальные коэффициенты \(\binom{r}{i}\), их значения по модулю \(M\), а также степени \(2^{it}\pmod M\). Кроме того, вычисляются \(2^k\pmod M\) и мультипликативная обратная величина к \(2^k\) по модулю \(M\), потому что после свёртки естественным образом появляются множители вида \(2^{-k}\), если вести расчёт сразу по модулю \(M\).
Затем реализация строит префиксные суммы для несвёрнутой части и суффиксные суммы для свёрнутой части. Это позволяет получить постоянный bulk-вклад интервала за \(O(1)\) модульного времени, как только известна длина интервала. Лишь последние \(62\) значения каждого интервала обрабатываются по отдельности.
Для этих исключительных позиций реализация восстанавливает знакопеременное свёрнутое выражение, извлекает целую часть \(q\) сдвигом ведущего биномиального коэффициента, вычитает соответствующее кратное \(\beta\), решает, что меньше — сам остаток или его дополнение, — и в конце умножает результат на внешний множитель \(2^{k-n}\). Версия на C++ распараллеливает эти независимые вычисления, а версии на Python и Java выполняют те же действия последовательно.
Существует только \(r+1\) типов интервалов. Каждый интервал даёт один bulk-вклад и не более \(62\) исключительных позиций. Каждая исключительная позиция просматривает \(r+1\) биномиальных членов, поэтому арифметическое ядро требует \(O(r^2)\) модульных операций и \(O(r)\) памяти.
В целевой задаче \(r=62\) фиксировано, поэтому время работы практически постоянно по отношению к размерам \(k\) и \(t\); в частности, оно не растёт линейно вместе с ними. Оставшаяся зависимость появляется только в модульном возведении в степень, а там стоимость логарифмична по величине показателя.
لأعداد صحيحة ثابتة \(k\) و\(t\) و\(r\)، نعرّف
$$\alpha = 2^t + 1,\qquad \beta = 2^k + 1,\qquad M = 10^9 + 62031.$$
ولكل \(n\) بحيث \(0 \le n < k\)، ليكن \(R_n\) هو الباقي غير السالب لـ \(2^n\alpha^r\) modulo \(\beta\)، ثم نعرّف
$$D_n = \min(R_n,\beta - R_n).$$
القيمة المطلوبة هي
$$F(k,t,r)=\sum_{n=0}^{k-1} 2^{k-n} D_n \pmod{M}.$$
الصعوبة الأساسية أن \(k\) و\(t\) هائلان جدًا، لذلك لا يمكن المرور على كل قيم \(n\) مباشرة. الفكرة هي توسيع \(\alpha^r\)، ثم طيّ القوى الكبيرة تحت المودولو \(2^k+1\)، ثم إثبات أن معظم قيم \(n\) داخل كل فترة تعطي المساهمة الموزونة نفسها تمامًا.
التنفيذات تعمل على القيمة الهدف \(r=62\)، ومع المعطيات المستعملة يتحقق الشرط \(rt<k\). هذا الشرط حاسم، لأنه يعني أن كل أس بعد التوسيع يبقى أقل من \(2k\)، وبالتالي فإن كل حد يعبر الحاجز \(k\) مرة واحدة على الأكثر.
من نظرية ذات الحدين نحصل على
$$\alpha^r=(1+2^t)^r=\sum_{i=0}^{r}\binom{r}{i}2^{it}.$$
وبعد الضرب في \(2^n\) يصبح التعبير
$$2^n\alpha^r=\sum_{i=0}^{r}\binom{r}{i}2^{n+it}.$$
إذًا جوهر المسألة يتحكم فيه الأس
$$e_i(n)=n+it.$$
وبما أن \(0 \le n < k\) و\(rt<k\)، فإن كل \(e_i(n)\) يقع في المجال \([0,2k)\). لذلك فكل حد إما أنه أصلًا تحت \(k\)، أو أنه يتجاوز \(k\) مرة واحدة فقط ثم يمكن طيه باستعمال العلاقة
$$2^k\equiv -1 \pmod{\beta}.$$
لكل \(s=1,2,\dots,r\) نعرّف
$$I_s=\left[k-st,\ k-(s-1)t-1\right]\cap [0,k-1].$$
وهناك أيضًا الفترة الأخيرة
$$I_{r+1}=[0,\ k-rt-1]\cap [0,k-1],$$
وقد تكون فارغة لبعض القيم.
إذا كان \(n\in I_s\)، فإن الحدود ذات \(i\ge s\) فقط هي التي تحقق \(e_i(n)\ge k\)، أما الحدود ذات \(i<s\) فتبقى تحت \(k\). ومن ثم
$$2^{e_i(n)} \equiv \begin{cases} 2^{n+it}, & i<s,\\[4pt] -2^{n+it-k}, & i\ge s, \end{cases}\pmod{\beta}$$
وبالتالي
$$R_n \equiv E_s(n):=\sum_{i=0}^{s-1}\binom{r}{i}2^{n+it}-\sum_{i=s}^{r}\binom{r}{i}2^{n+it-k}\pmod{\beta}.$$
في الفترة الأخيرة \(I_{r+1}\) لا يحدث أي طي، لذلك تبقى فقط المجموعة الأولى من الحدود. هذا التقسيم إلى فترات هو التبسيط البنيوي الأهم، لأنه يستبدل المعالجة المنفصلة لكل \(n\) بدراسة نمط واحد لكل فترة.
افترض أن الممثل المتمركز لبعض \(n\in I_s\) هو ببساطة \(D_n=E_s(n)\)، أي لا حاجة لاختيار \(\beta-R_n\). عندئذ
$$2^{k-n}D_n=\sum_{i=0}^{s-1}\binom{r}{i}2^{k+it}-\sum_{i=s}^{r}\binom{r}{i}2^{it}.$$
الطرف الأيمن لا يعتمد على \(n\) إطلاقًا. لذلك فإن كل قيم \(n\) غير الاستثنائية داخل الفترة نفسها تعطي المساهمة الموزونة نفسها.
وفي الفترة الأخيرة تصبح الثابتة
$$2^{k-n}D_n=\sum_{i=0}^{r}\binom{r}{i}2^{k+it},$$
وهي أيضًا مستقلة عن \(n\)، ما دام الأقرب هو الباقي نفسه وليس متممه.
ولهذا يستطيع البرنامج جمع معظم مساهمة فترة ضخمة في خطوة كتلية واحدة بدل المرور على جميع المواضع داخلها.
ثبّت فترة \(I_s\). الأس الموجب القائد هو
$$e_{\max}=n+(s-1)t$$
عندما \(s\le r\)، أو \(e_{\max}=n+rt\) في الفترة الأخيرة. ولنكتب
$$\delta = k-e_{\max}.$$
إذا كان \(\delta \ge 63\)، فإن جميع الحدود الأخرى في المجموع ذي الإشارات تكون أصغر على الأقل بعامل \(2^{63}\) من مقياس العتبة \(2^k\)، بينما تكون الكتلة الإجمالية للمعاملات محصورة بـ
$$\sum_{i=0}^{r}\binom{r}{i}=2^r=2^{62}.$$
إذًا يهيمن الحد القائد، ويقع المجموع كله قطعًا بين \(0\) و\(\beta/2\). في هذه الحالة لا حاجة أصلًا إلى المقارنة بين \(R_n\) و\(\beta-R_n\): القيمة الأقرب هي تلقائيًا الجهة غير المعكوسة.
وعليه فإن الحالات الوحيدة التي تتطلب منطقًا دقيقًا للباقي المتمركز هي الحالات التي فيها \(\delta\le 62\). وهذه هي بالضبط آخر \(62\) قيمة في كل فترة غير فارغة، ولذلك تفصل التنفيذات هذا الذيل القصير وتعالج ما قبله على أنه كتلة ثابتة.
لأي \(n\) استثنائي، نأخذ \(j=s-1\) إذا كان \(s\le r\)، ونأخذ \(j=r\) في الفترة الأخيرة. الحد المهيمن هو
$$\binom{r}{j}2^{k-\delta}.$$
اكتب المعامل بالنسبة إلى الأساس \(2^\delta\):
$$\binom{r}{j}=q\,2^\delta+\ell,\qquad 0\le \ell < 2^\delta.$$
عندئذ
$$\binom{r}{j}2^{k-\delta}=q2^k+\ell 2^{k-\delta}=q(2^k+1)+\ell 2^{k-\delta}-q.$$
هذه الهوية تبيّن أن خارج القسمة الصحيح على \(\beta=2^k+1\) يمكن استخراجه مباشرة من الإزاحة الثنائية
$$q=\left\lfloor \frac{\binom{r}{j}}{2^\delta}\right\rfloor.$$
بعد طرح \(q\beta\)، تحدد البتات المنخفضة \(\ell\) أي طرف من \(\beta/2\) يقع عليه الباقي. إذا كان \(\ell<2^{\delta-1}\)، فالباقي أقل من نصف المودولو. وإذا كان \(\ell>2^{\delta-1}\)، فالمسافة الأصغر هي \(\beta-R_n\). أما في حالة التعادل \(\ell=2^{\delta-1}\)، فتحسم الحدود الأدنى رتبة القرار النهائي. وهذا بالضبط ما تطبقه التنفيذات على الذيل الاستثنائي القصير لكل فترة.
لدينا هنا
$$\alpha=2^1+1=3,\qquad \beta=2^3+1=9.$$
وبما أن \(r=1\)، تكفي القيم \(n=0,1,2\):
$$\begin{aligned} n=0&:&&2^0\alpha^1=3\equiv 3 \pmod 9,\quad D_0=\min(3,6)=3,\quad 2^{3-0}D_0=24,\\ n=1&:&&2^1\alpha^1=6\equiv 6 \pmod 9,\quad D_1=\min(6,3)=3,\quad 2^{3-1}D_1=12,\\ n=2&:&&2^2\alpha^1=12\equiv 3 \pmod 9,\quad D_2=\min(3,6)=3,\quad 2^{3-2}D_2=6. \end{aligned}$$
إذن
$$F(3,1,1)=24+12+6=42,$$
وهو تمامًا مقدار التحقق الذي تستعمله التنفيذات.
تنفيذات C++ وPython وJava تتبع الخطة الرياضية نفسها. فهي تبدأ بحساب معاملات ذات الحدين \(\binom{r}{i}\) مسبقًا، وكذلك قيمها modulo \(M\)، وقوى \(2^{it}\pmod M\). كما تحسب \(2^k\pmod M\) ومعكوس \(2^k\) الضربي modulo \(M\)، لأن الحدود المطوية تولّد طبيعيًا عوامل من نوع \(2^{-k}\) عندما يُتتبع كل شيء مباشرة modulo \(M\).
بعد ذلك تبني التنفيذات مجاميع بادئة للجزء غير المطوي ومجاميع لاحقة للجزء المطوي. وبهذه الطريقة تصبح مساهمة الكتلة الثابتة لأي فترة متاحة بزمن \(O(1)\) modulo بمجرد معرفة طول الفترة. أما آخر \(62\) موضعًا فقط في كل فترة فيُعالَج كل واحد منها على حدة.
في هذه المواضع الاستثنائية، تعيد التنفيذات تركيب التعبير المطوي ذي الإشارات، وتستخرج خارج القسمة \(q\) من الحد الثنائي المسيطر عبر إزاحة بتية، ثم تطرح المضاعف المناسب لـ \(\beta\)، وتقرر هل الباقي نفسه أقرب أم متممه، ثم تضرب في العامل الخارجي \(2^{k-n}\). نسخة C++ توزّع هذه الحالات المستقلة على خيوط متوازية، أما نسختا Python وJava فتقيّمان الحالات نفسها على نحو تسلسلي.
يوجد فقط \(r+1\) أنماط من الفترات. كل فترة تعطي حدًا كتليًا واحدًا، وما يصل إلى \(62\) موضعًا استثنائيًا. وكل تقييم استثنائي يفحص \(r+1\) حدًا ثنائيًا، لذلك يستخدم القلب الحسابي \(O(r^2)\) من العمليات المعيارية و\(O(r)\) من الذاكرة.
في المسألة الهدف تكون \(r=62\) ثابتة، ولذلك يكون زمن التنفيذ عمليًا ثابتًا بالنسبة إلى أحجام \(k\) و\(t\)، ولا ينمو خطيًا معهما. أما الاعتماد المتبقي على كبرهما فيأتي فقط من الأسّ المعياري، وكلفته لوغاريتمية في قيمة الأس.