A positive integer is called a simber when every even digit occurs an even number of times, and every odd digit that occurs does so an odd number of times. If \(Q(n)\) denotes the number of simbers below \(10^n\), the task is to evaluate
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
Because \(2^{39}\) is enormous, direct enumeration is impossible. The solution therefore converts the digit-parity rules into algebraic projectors, compresses each fixed-length count into a short linear combination of powers \(\lambda^t\), and then sums those powers as geometric series modulo the given modulus.
Let \(E=\{0,2,4,6,8\}\) and \(O=\{1,3,5,7,9\}\). For any decimal string, let \(c_d\) be the number of occurrences of digit \(d\).
For an even digit, the allowed counts are \(0,2,4,\dots\), so its indicator is
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}.$$
For an odd digit, the allowed counts are \(0,1,3,5,\dots\): zero is allowed, but every positive even count is forbidden. A convenient form is
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2},$$
with the usual convention \(0^0=1\). This identity gives \(1\) when \(c=0\), \(1\) when \(c\) is odd, and \(0\) when \(c\) is a positive even number.
Let \(A_t\) be the number of length-\(t\) decimal strings that satisfy the simber rules when leading zero is allowed. If the count vector is \((c_0,\dots,c_9)\), then
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o).$$
After multiplying by \(2^{10}\) and expanding the projectors, each even digit contributes a choice of weight \(+1\) or \(-1\), while each odd digit contributes a choice of weight \(0\), \(+1\), or \(-1\) with coefficients \(2\), \(1\), and \(-1\). For one complete global choice of weights \(w_0,\dots,w_9\), the multinomial theorem gives
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t.$$
So the exact identities of the digits no longer matter; only the total weight matters. If \(a\) digits contribute \(+1\) and \(b\) digits contribute \(-1\), then the contribution is \(\lambda^t\) with \(\lambda=a-b\). After aggregating equal values of \(\lambda\), we obtain a small coefficient table \(C(\lambda)\) such that
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
A positive integer with exactly \(t\) digits corresponds to a length-\(t\) string that does not begin with zero. Therefore we must subtract the simber strings whose first character is \(0\).
If we remove that leading zero, the remaining suffix has length \(t-1\). Since digit \(0\) has already appeared once, its remaining count must be odd so that the total number of zeros is even. The other four nonzero even digits keep the usual even rule, and the five odd digits keep the usual “zero or odd” rule. Hence the distinguished zero digit uses
$$J(c)=\frac{1-(-1)^c}{2},$$
which is the indicator of an odd count. Let \(B_s\) be the number of length-\(s\) suffixes with that modified rule for digit \(0\). By the same expansion-and-grouping argument, there is another coefficient table \(D(\lambda)\) with
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
Therefore the number of genuine \(t\)-digit simbers is
$$N_t=A_t-B_{t-1}.$$
For \(t=2\), the leading-zero-allowed simber strings are easy to classify. There are five repeated even-digit strings
$$00,\ 22,\ 44,\ 66,\ 88,$$
and there are \(5\cdot 4=20\) ordered strings formed by two distinct odd digits. Hence \(A_2=25\).
Among these, only \(00\) starts with zero, so \(B_1=1\) and
$$N_2=A_2-B_1=25-1=24.$$
The one-digit simbers are \(1,3,5,7,9\), so \(N_1=5\). Therefore
$$Q(2)=N_1+N_2=5+24=29.$$
This tiny case is exactly what the general projector method is automating for huge values of \(n\).
Now sum the exact-length counts from \(1\) to \(n\):
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
For \(\lambda\neq 0,1\), the inner sums are
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}.$$
The exceptional values are handled separately:
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
All arithmetic is performed modulo
$$M=1{,}000{,}000{,}123,$$
so division by \(\lambda-1\) and by \(2^{10}\) becomes multiplication by modular inverses.
The decimal alphabet is fixed. Each of the five odd digits contributes one of three weights \(\{0,+1,-1\}\), and each of the five even digits contributes one of two weights \(\{+1,-1\}\). Therefore \(\lambda\) can only lie between \(-10\) and \(10\), so after aggregation there are at most \(21\) distinct powers to evaluate. The difficult combinatorics has been compressed into two tiny coefficient tables, and the remaining work is just fast modular exponentiation together with short geometric-sum evaluations.
The C++, Python, and Java implementations build the two coefficient tables directly from the projector factors. One table corresponds to all length-\(t\) strings, and the other corresponds to the leading-zero correction in which digit \(0\) must occur an odd number of times in the suffix. In both cases, the expansion is grouped only by the value of \(\lambda\), because that is the only quantity that survives the multinomial sum.
For a requested \(n\), the implementation evaluates the first table against \(\sum_{t=1}^{n}\lambda^t\) and the second table against \(\sum_{s=0}^{n-1}\lambda^s\). Fast modular exponentiation is used inside the closed forms for those geometric sums, and the final factor \(2^{-10}\) is applied with a modular inverse.
Finally, the program computes \(Q(2^u)\) for \(u=1,2,\dots,39\) and accumulates the answers modulo \(M\). It also checks two published checkpoints,
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
and confirms the small case \(Q(4)\) by direct brute force.
With the decimal digit set fixed, constructing the two coefficient tables is constant work and constant memory. After aggregation, each table has only a small number of nonzero \(\lambda\)-entries, bounded by the range \(-10\) to \(10\).
Each evaluation of \(Q(n)\) therefore needs only a short loop over those entries, and each term uses \(O(\log n)\) time for modular exponentiation. So one query costs \(O(L\log n)\), where \(L\) is the number of distinct \(\lambda\)-values, and in this problem \(L\) is tiny. Summing the 39 required values is easily within practical limits, and the memory usage stays \(O(L)\).
Eine positive ganze Zahl heißt simber, wenn jede gerade Ziffer eine gerade Anzahl von Malen vorkommt und jede ungerade Ziffer, die überhaupt vorkommt, dies eine ungerade Anzahl von Malen tut. Bezeichnet \(Q(n)\) die Anzahl der simber-Zahlen unterhalb von \(10^n\), so ist zu berechnen
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
Da \(2^{39}\) riesig ist, kann man die Zahlen nicht direkt nach Länge durchsuchen. Die Lösung übersetzt die Paritätsbedingungen der Ziffern in algebraische Projektoren, komprimiert jede feste Länge zu einer kurzen Linearkombination von Potenzen \(\lambda^t\) und summiert diese Potenzen anschließend als geometrische Reihen modulo des gegebenen Moduls.
Sei \(E=\{0,2,4,6,8\}\) die Menge der geraden Ziffern und \(O=\{1,3,5,7,9\}\) die Menge der ungeraden Ziffern. Für eine Dezimalzeichenkette sei \(c_d\) die Anzahl der Vorkommen der Ziffer \(d\).
Für eine gerade Ziffer sind genau die Anzahlen \(0,2,4,\dots\) erlaubt. Der passende Indikator lautet daher
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}.$$
Für eine ungerade Ziffer sind \(0,1,3,5,\dots\) erlaubt: Null ist zulässig, positive gerade Anzahlen sind verboten. Praktisch ist die Darstellung
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2},$$
wobei wie üblich \(0^0=1\) gesetzt wird. Diese Identität liefert genau dann \(1\), wenn \(c=0\) oder \(c\) ungerade ist, und sonst \(0\).
Sei \(A_t\) die Anzahl der Dezimalzeichenketten der Länge \(t\), die die Simber-Bedingungen erfüllen, wobei eine führende Null erlaubt ist. Für den Zählvektor \((c_0,\dots,c_9)\) gilt dann
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o).$$
Multipliziert man mit \(2^{10}\) und expandiert alle Projektoren, so liefert jede gerade Ziffer ein Gewicht \(+1\) oder \(-1\), während jede ungerade Ziffer eines der Gewichte \(0\), \(+1\) oder \(-1\) mit Koeffizienten \(2\), \(1\) und \(-1\) beiträgt. Für eine vollständige globale Gewichtswahl \(w_0,\dots,w_9\) ergibt der Multinomialsatz
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t.$$
Damit sind die konkreten Ziffern nicht mehr wichtig; entscheidend ist nur die Summe der Gewichte. Tragen \(a\) Ziffern das Gewicht \(+1\) und \(b\) Ziffern das Gewicht \(-1\), dann entsteht \(\lambda^t\) mit \(\lambda=a-b\). Nach dem Zusammenfassen gleicher \(\lambda\)-Werte erhält man eine kleine Koeffiziententabelle \(C(\lambda)\) mit
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
Eine positive ganze Zahl mit genau \(t\) Stellen entspricht einer Zeichenkette der Länge \(t\), die nicht mit Null beginnt. Daher müssen die simber-Zeichenketten abgezogen werden, deren erstes Zeichen \(0\) ist.
Entfernt man diese führende Null, bleibt ein Suffix der Länge \(t-1\). Die Ziffer \(0\) ist dann bereits einmal benutzt worden, also muss ihre Restanzahl ungerade sein, damit die Gesamtzahl der Nullen gerade wird. Die vier nichtnulligen geraden Ziffern behalten die normale Gerade-Regel, und die fünf ungeraden Ziffern behalten die normale Regel „Null oder ungerade“. Für die ausgezeichnete Ziffer \(0\) verwendet man also
$$J(c)=\frac{1-(-1)^c}{2},$$
den Indikator einer ungeraden Anzahl. Sei \(B_s\) die Anzahl der Suffixe der Länge \(s\) mit genau dieser modifizierten Regel für die Ziffer \(0\). Dasselbe Expansionsargument liefert dann eine zweite Koeffiziententabelle \(D(\lambda)\) mit
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
Damit ist die Anzahl echter \(t\)-stelliger simber-Zahlen
$$N_t=A_t-B_{t-1}.$$
Für \(t=2\) lassen sich die simber-Zeichenketten mit erlaubter führender Null direkt klassifizieren. Es gibt fünf doppelte gerade Ziffern
$$00,\ 22,\ 44,\ 66,\ 88,$$
und außerdem \(5\cdot 4=20\) geordnete Zeichenketten aus zwei verschiedenen ungeraden Ziffern. Also ist \(A_2=25\).
Unter diesen beginnt nur \(00\) mit Null, also ist \(B_1=1\) und damit
$$N_2=A_2-B_1=25-1=24.$$
Die einstelligen simber-Zahlen sind \(1,3,5,7,9\), also \(N_1=5\). Folglich
$$Q(2)=N_1+N_2=5+24=29.$$
Genau diese Kleinarbeit automatisiert die allgemeine Projektormethode für riesige Werte von \(n\).
Nun summieren wir die exakten Längenbeiträge von \(1\) bis \(n\):
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
Für \(\lambda\neq 0,1\) lauten die inneren Summen
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}.$$
Die Sonderfälle behandelt man separat:
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
Alle Rechnungen erfolgen modulo
$$M=1{,}000{,}000{,}123,$$
weshalb die Division durch \(\lambda-1\) und durch \(2^{10}\) als Multiplikation mit modularen Inversen umgesetzt wird.
Das Dezimalsystem ist fest. Jede der fünf ungeraden Ziffern trägt eines der Gewichte \(\{0,+1,-1\}\) bei, jede der fünf geraden Ziffern eines der Gewichte \(\{+1,-1\}\). Daher kann \(\lambda\) nur zwischen \(-10\) und \(10\) liegen, also gibt es nach dem Zusammenfassen höchstens \(21\) verschiedene Potenzen. Die schwierige Kombinatorik ist damit in zwei sehr kleine Koeffiziententabellen komprimiert, und die Restarbeit besteht nur noch aus schneller modularer Exponentiation und kurzen geometrischen Summen.
Die C++-, Python- und Java-Implementierungen bauen die beiden Koeffiziententabellen direkt aus den Projektorfaktoren auf. Eine Tabelle entspricht allen Zeichenketten der Länge \(t\), die andere der Korrektur für führende Nullen, bei der die Ziffer \(0\) im Suffix ungerade oft vorkommen muss. In beiden Fällen wird nur nach dem Wert von \(\lambda\) gruppiert, weil genau diese Größe den multinomialen Summenschritt überlebt.
Für ein gegebenes \(n\) wertet die Implementierung die erste Tabelle gegen \(\sum_{t=1}^{n}\lambda^t\) und die zweite gegen \(\sum_{s=0}^{n-1}\lambda^s\) aus. Schnelle modulare Exponentiation erscheint in den geschlossenen Formen dieser geometrischen Reihen, und der Faktor \(2^{-10}\) wird über ein modulares Inverses angewendet.
Am Ende berechnet das Programm \(Q(2^u)\) für \(u=1,2,\dots,39\) und summiert die Werte modulo \(M\). Zusätzlich prüft es die beiden Kontrollwerte
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
und bestätigt den kleinen Fall \(Q(4)\) durch direkte Brute-Force-Zählung.
Da die Dezimalziffernmenge fest ist, kosten Aufbau und Speicherung der beiden Koeffiziententabellen nur konstante Zeit und konstanten Speicher. Nach dem Zusammenfassen besitzt jede Tabelle nur wenige von Null verschiedene \(\lambda\)-Einträge, beschränkt durch den Bereich \(-10\) bis \(10\).
Jede Auswertung von \(Q(n)\) benötigt daher nur eine kurze Schleife über diese Einträge, und jeder Term kostet \(O(\log n)\) für die modulare Exponentiation. Eine Anfrage hat also Aufwand \(O(L\log n)\), wobei \(L\) die Anzahl verschiedener \(\lambda\)-Werte ist; in diesem Problem ist \(L\) sehr klein. Die Summe über die 39 geforderten Werte ist daher problemlos praktisch, und der Speicherverbrauch bleibt \(O(L)\).
Bir pozitif tamsayıya simber denir; eğer her çift rakam toplamda çift sayıda görünüyorsa ve görünen her tek rakam toplamda tek sayıda görünüyorsa. \(Q(n)\), \(10^n\)'den küçük simber sayıların sayısı olsun. İstenen değer
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
\(2^{39}\) çok büyük olduğu için sayıları uzunluklarına göre tek tek taramak mümkün değildir. Çözüm bunun yerine rakam paritesi koşullarını cebirsel projektörlere dönüştürür, her sabit uzunluğu birkaç \(\lambda^t\) terimine sıkıştırır ve sonra bu terimleri verilen mod altında geometrik seri olarak toplar.
\(E=\{0,2,4,6,8\}\) çift rakamlar kümesi, \(O=\{1,3,5,7,9\}\) tek rakamlar kümesi olsun. Bir onluk dizgede \(d\) rakamının görünme sayısını \(c_d\) ile gösterelim.
Çift bir rakam için izin verilen sayılar \(0,2,4,\dots\) olduğundan gösterge fonksiyonu
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}$$
olur. Tek bir rakam için ise izin verilen sayılar \(0,1,3,5,\dots\) biçimindedir: sıfır kabul edilir, ama pozitif çift sayılar yasaktır. Uygun bir yazım
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2}$$
şeklindedir; burada alışıldığı gibi \(0^0=1\) kabul edilir. Bu ifade \(c=0\) iken \(1\), \(c\) tek iken \(1\), \(c\) pozitif çift iken \(0\) verir.
\(A_t\), başta sıfıra izin verildiğinde simber koşullarını sağlayan uzunluğu \(t\) olan onluk dizgelerin sayısı olsun. Sayım vektörü \((c_0,\dots,c_9)\) için
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o)$$
yazılır. Bu ifadeyi \(2^{10}\) ile çarpıp projektörleri açarsak, her çift rakam \(+1\) veya \(-1\) ağırlığı verir; her tek rakam ise katsayıları sırasıyla \(2\), \(1\), \(-1\) olan \(0\), \(+1\), \(-1\) ağırlıklarından birini verir. Tam bir global ağırlık seçimi \(w_0,\dots,w_9\) için çokterimli teorem
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t$$
sonucunu verir. Böylece asıl önemli olan hangi rakamın seçildiği değil, ağırlıkların toplamıdır. Eğer \(a\) tane \(+1\), \(b\) tane \(-1\) varsa katkı \(\lambda^t\) olur; burada \(\lambda=a-b\). Aynı \(\lambda\) değerleri birleştirildiğinde küçük bir \(C(\lambda)\) katsayı tablosu elde edilir:
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
Tam olarak \(t\) basamaklı bir pozitif sayı, uzunluğu \(t\) olan ve sıfırla başlamayan bir dizgeye karşılık gelir. Bu yüzden ilk karakteri \(0\) olan simber dizgeleri ayrıca çıkarmamız gerekir.
Bu baştaki sıfırı kaldırınca geriye uzunluğu \(t-1\) olan bir son ek kalır. \(0\) rakamı zaten bir kez kullanıldığı için, toplam sıfır sayısının çift olması adına kalan sıfır sayısı tek olmalıdır. Diğer dört sıfır olmayan çift rakam normal çiftlik kuralını korur; beş tek rakam da normal “sıfır ya da tek” kuralını korur. Dolayısıyla özel durumdaki \(0\) rakamı için
$$J(c)=\frac{1-(-1)^c}{2}$$
kullanılır; bu tek sayım göstergesidir. \(B_s\), \(0\) rakamı için bu değiştirilmiş kuralla uzunluğu \(s\) olan son eklerin sayısı olsun. Aynı açılım ve gruplayma mantığı ikinci bir \(D(\lambda)\) katsayı tablosu verir:
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
Böylece gerçek \(t\) basamaklı simber sayılarının sayısı
$$N_t=A_t-B_{t-1}$$
olur.
\(t=2\) için, başta sıfıra izin verilen simber dizgeleri doğrudan sınıflandırabiliriz. Beş adet aynı çift rakamdan oluşan dizge vardır:
$$00,\ 22,\ 44,\ 66,\ 88,$$
ve iki farklı tek rakamın sıralı seçiminden gelen \(5\cdot 4=20\) dizge daha vardır. Demek ki \(A_2=25\).
Bunların içinde yalnızca \(00\) sıfırla başlar; dolayısıyla \(B_1=1\) ve
$$N_2=A_2-B_1=25-1=24.$$
Tek basamaklı simber sayılar \(1,3,5,7,9\) olduğundan \(N_1=5\). Sonuç olarak
$$Q(2)=N_1+N_2=5+24=29.$$
Genel yöntem, işte bu küçük elle sayımı çok büyük \(n\) değerleri için otomatik hale getirir.
Şimdi tam uzunluk katkılarını \(1\)'den \(n\)'e kadar topluyoruz:
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
\(\lambda\neq 0,1\) için iç toplamlar
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}$$
şeklindedir. Özel durumlar ayrıca ele alınır:
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
Tüm aritmetik
$$M=1{,}000{,}000{,}123$$
modunda yapıldığı için, \(\lambda-1\) ve \(2^{10}\) ile bölmeler modüler ters ile gerçekleştirilir.
Onluk alfabe sabittir. Beş tek rakamın her biri \(\{0,+1,-1\}\) kümesinden bir ağırlık, beş çift rakamın her biri ise \(\{+1,-1\}\) kümesinden bir ağırlık verir. Bu nedenle \(\lambda\) yalnızca \(-10\) ile \(10\) arasında olabilir; yani birleştirmeden sonra en fazla \(21\) farklı kuvvet hesaplanır. Zor kombinatorik kısım iki küçük katsayı tablosuna sıkıştırılmış olur; geriye sadece hızlı modüler üs alma ve kısa geometrik toplamlar kalır.
C++, Python ve Java implementasyonları iki katsayı tablosunu doğrudan projektör çarpanlarından kurar. Bir tablo tüm uzunluğu \(t\) olan dizgeleri temsil eder; diğer tablo ise son ekte \(0\) rakamının tek sayıda görünmesi gereken baştaki sıfır düzeltmesini temsil eder. Her iki durumda da açılım yalnızca \(\lambda\) değerine göre gruplanır; çünkü çokterimli toplamdan sonra ayakta kalan tek nicelik budur.
İstenen bir \(n\) için implementasyon ilk tabloyu \(\sum_{t=1}^{n}\lambda^t\) ile, ikinci tabloyu ise \(\sum_{s=0}^{n-1}\lambda^s\) ile eşleştirerek değerlendirir. Geometrik toplamların kapalı biçimlerinde hızlı modüler üs alma kullanılır; son çarpan olan \(2^{-10}\) da modüler ters ile uygulanır.
Son olarak program \(u=1,2,\dots,39\) için \(Q(2^u)\) değerlerini hesaplayıp sonucu \(M\) modunda toplar. Ayrıca şu iki kontrol değerini doğrular:
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
ve küçük \(Q(4)\) durumunu doğrudan kaba kuvvetle de teyit eder.
Onluk rakam kümesi sabit olduğu için iki katsayı tablosunun kurulması sabit zaman ve sabit bellek gerektirir. Birleştirme sonrasında her tabloda sıfır olmayan \(\lambda\) değerlerinin sayısı çok küçüktür ve \(-10\) ile \(10\) aralığıyla sınırlıdır.
Bu nedenle her \(Q(n)\) hesabı sadece bu girişler üzerinde kısa bir döngü ister; her terim için modüler üs alma maliyeti \(O(\log n)\)'dir. Yani tek sorgu maliyeti \(O(L\log n)\) olur; burada \(L\), farklı \(\lambda\) sayısıdır ve bu problemde çok küçüktür. Gerekli 39 değerin toplamı rahatlıkla pratiktir; bellek kullanımı da \(O(L)\) olarak kalır.
Un entero positivo se llama simber cuando cada dígito par aparece un número par de veces y cada dígito impar que aparece lo hace un número impar de veces. Si \(Q(n)\) es la cantidad de simbers menores que \(10^n\), hay que calcular
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
Como \(2^{39}\) es enorme, no se puede enumerar por longitud. La idea es convertir las restricciones de paridad de los dígitos en proyectores algebraicos, comprimir cada conteo de longitud fija en una combinación lineal muy corta de potencias \(\lambda^t\) y luego sumar esas potencias mediante series geométricas módulo el valor pedido.
Sea \(E=\{0,2,4,6,8\}\) el conjunto de dígitos pares y \(O=\{1,3,5,7,9\}\) el de impares. Para una cadena decimal, llamemos \(c_d\) al número de apariciones del dígito \(d\).
Para un dígito par, los conteos permitidos son \(0,2,4,\dots\), así que su indicador es
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}.$$
Para un dígito impar, los conteos permitidos son \(0,1,3,5,\dots\): el cero sí vale, pero todo conteo par positivo está prohibido. Una forma útil es
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2},$$
con la convención habitual \(0^0=1\). Esta identidad produce \(1\) cuando \(c=0\), \(1\) cuando \(c\) es impar y \(0\) cuando \(c\) es un número par positivo.
Sea \(A_t\) el número de cadenas decimales de longitud \(t\) que cumplen la condición simber permitiendo cero inicial. Si el vector de conteos es \((c_0,\dots,c_9)\), entonces
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o).$$
Al multiplicar por \(2^{10}\) y expandir los proyectores, cada dígito par aporta un peso \(+1\) o \(-1\), mientras que cada dígito impar aporta un peso \(0\), \(+1\) o \(-1\) con coeficientes \(2\), \(1\) y \(-1\). Para una elección global completa de pesos \(w_0,\dots,w_9\), el teorema multinomial da
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t.$$
Así que ya no importa qué dígito concreto lleva cada peso; solo importa la suma total. Si \(a\) dígitos aportan \(+1\) y \(b\) aportan \(-1\), aparece \(\lambda^t\) con \(\lambda=a-b\). Agrupando los términos con el mismo \(\lambda\), se obtiene una pequeña tabla de coeficientes \(C(\lambda)\) tal que
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
Un entero positivo de exactamente \(t\) cifras corresponde a una cadena de longitud \(t\) que no empieza con cero. Por tanto, hay que restar las cadenas simber cuyo primer carácter es \(0\).
Si quitamos ese cero inicial, queda un sufijo de longitud \(t-1\). Como el dígito \(0\) ya apareció una vez, su cuenta restante debe ser impar para que el total de ceros sea par. Los otros cuatro dígitos pares no nulos siguen con la regla par habitual, y los cinco impares conservan la regla habitual “cero o impar”. Por eso, para el dígito \(0\) distinguido se usa
$$J(c)=\frac{1-(-1)^c}{2},$$
que es el indicador de conteo impar. Sea \(B_s\) el número de sufijos de longitud \(s\) con esa regla modificada para el dígito \(0\). El mismo argumento de expansión y agrupación produce una segunda tabla \(D(\lambda)\) con
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
En consecuencia, el número de simbers genuinos de \(t\) cifras es
$$N_t=A_t-B_{t-1}.$$
Para \(t=2\), las cadenas simber permitiendo cero inicial se clasifican con facilidad. Hay cinco cadenas con un dígito par repetido:
$$00,\ 22,\ 44,\ 66,\ 88,$$
y además \(5\cdot 4=20\) cadenas ordenadas formadas por dos dígitos impares distintos. Por tanto, \(A_2=25\).
Entre ellas, solo \(00\) empieza con cero, así que \(B_1=1\) y
$$N_2=A_2-B_1=25-1=24.$$
Los simbers de una cifra son \(1,3,5,7,9\), luego \(N_1=5\). Así,
$$Q(2)=N_1+N_2=5+24=29.$$
Este ejemplo pequeño es exactamente lo que el método general automatiza para valores enormes de \(n\).
Ahora sumamos los conteos por longitud exacta desde \(1\) hasta \(n\):
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
Para \(\lambda\neq 0,1\), las sumas internas son
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}.$$
Los valores especiales se tratan aparte:
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
Toda la aritmética se realiza módulo
$$M=1{,}000{,}000{,}123,$$
de modo que dividir por \(\lambda-1\) y por \(2^{10}\) se convierte en multiplicar por inversos modulares.
El alfabeto decimal es fijo. Cada uno de los cinco dígitos impares aporta uno de los pesos \(\{0,+1,-1\}\), y cada uno de los cinco dígitos pares aporta uno de los pesos \(\{+1,-1\}\). Por eso \(\lambda\) solo puede estar entre \(-10\) y \(10\), de modo que tras agrupar hay como máximo \(21\) potencias distintas que evaluar. La parte combinatoria difícil queda comprimida en dos tablas diminutas de coeficientes, y el resto es solo exponenciación modular rápida junto con sumas geométricas muy cortas.
Las implementaciones en C++, Python y Java construyen las dos tablas de coeficientes directamente a partir de los factores proyectores. Una tabla corresponde a todas las cadenas de longitud \(t\); la otra corresponde a la corrección por cero inicial, donde el dígito \(0\) debe aparecer un número impar de veces en el sufijo. En ambos casos, la expansión se agrupa solo por el valor de \(\lambda\), porque esa es la única cantidad que sobrevive a la suma multinomial.
Para un \(n\) dado, la implementación evalúa la primera tabla contra \(\sum_{t=1}^{n}\lambda^t\) y la segunda contra \(\sum_{s=0}^{n-1}\lambda^s\). Dentro de las formas cerradas de esas series geométricas se usa exponenciación modular rápida, y el factor final \(2^{-10}\) se aplica mediante un inverso modular.
Por último, el programa calcula \(Q(2^u)\) para \(u=1,2,\dots,39\) y acumula el resultado módulo \(M\). También verifica dos puntos de control,
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
y confirma el caso pequeño \(Q(4)\) por fuerza bruta directa.
Como el conjunto de dígitos decimales es fijo, construir las dos tablas de coeficientes requiere tiempo constante y memoria constante. Tras agrupar, cada tabla contiene solo unos pocos valores no nulos de \(\lambda\), acotados por el intervalo \(-10\) a \(10\).
Cada evaluación de \(Q(n)\) necesita entonces solo un bucle corto sobre esas entradas, y cada término cuesta \(O(\log n)\) por la exponenciación modular. Por tanto, una consulta cuesta \(O(L\log n)\), donde \(L\) es el número de valores distintos de \(\lambda\), y en este problema \(L\) es muy pequeño. La suma de los 39 valores pedidos es totalmente práctica, y la memoria sigue siendo \(O(L)\).
如果一个正整数中，每个偶数字出现的次数都是偶数，而每个实际出现过的奇数字出现的次数都是奇数，那么这个整数就叫作 simber。记 \(Q(n)\) 为小于 \(10^n\) 的 simber 个数，题目要求计算
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
由于 \(2^{39}\) 极大，不可能按位数直接枚举所有候选数。实现采用的核心思路是：先把“每个数字出现次数的奇偶限制”写成代数投影器，再把固定长度的计数压缩成少量 \(\lambda^t\) 的线性组合，最后用几何级数在模数下完成长度求和。
设偶数字集合为 \(E=\{0,2,4,6,8\}\)，奇数字集合为 \(O=\{1,3,5,7,9\}\)。对于任意十进制字符串，记数字 \(d\) 的出现次数为 \(c_d\)。
对于偶数字，允许的出现次数是 \(0,2,4,\dots\)，因此其指示函数可以写成
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}.$$
对于奇数字，允许的出现次数是 \(0,1,3,5,\dots\)：出现零次是允许的，出现正偶数次则不允许。一个很适合展开的写法是
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2},$$
其中采用通常约定 \(0^0=1\)。这个式子恰好在三种情况下给出正确结果：当 \(c=0\) 时取值为 \(1\)，当 \(c\) 为奇数时取值为 \(1\)，当 \(c\) 为正偶数时取值为 \(0\)。
设 \(A_t\) 表示长度为 \(t\) 的十进制字符串中，满足 simber 条件且允许前导零的总数。如果计数向量为 \((c_0,\dots,c_9)\)，那么
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o).$$
把上式整体乘以 \(2^{10}\) 后展开，每个偶数字都会贡献权重 \(+1\) 或 \(-1\)；每个奇数字则会贡献权重 \(0\)、\(+1\)、\(-1\)，其对应系数分别是 \(2\)、\(1\)、\(-1\)。对于一种完整的全局权重选择 \(w_0,\dots,w_9\)，多项式定理给出
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t.$$
这一步非常关键，因为它说明具体是哪几个数字带什么权重并不重要，真正留下来的只有总权重之和。如果有 \(a\) 个数字贡献 \(+1\)，有 \(b\) 个数字贡献 \(-1\)，那么该项只会表现为 \(\lambda^t\)，其中
$$\lambda=a-b.$$
把所有产生相同 \(\lambda\) 的项合并后，就得到一个很小的系数表 \(C(\lambda)\)，使得
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
恰好有 \(t\) 位的正整数，对应的是长度为 \(t\) 且首位不为 \(0\) 的字符串。所以除了统计全部满足条件的长度 \(t\) 字符串之外，还必须减去那些首字符就是 \(0\) 的 simber 字符串。
去掉这个前导零以后，剩下的是一个长度为 \(t-1\) 的后缀。由于数字 \(0\) 已经先出现了一次，因此后缀中 \(0\) 的剩余出现次数必须是奇数，这样总的 \(0\) 的出现次数才会回到偶数。其余四个非零偶数字仍然遵守“出现偶数次”的规则，五个奇数字仍然遵守“出现零次或奇数次”的规则。因此，对被单独拿出来处理的数字 \(0\)，要使用
$$J(c)=\frac{1-(-1)^c}{2},$$
也就是“奇数次出现”的指示函数。设 \(B_s\) 为满足这组修正规则的长度 \(s\) 后缀数量。用与上一步完全相同的展开与合并方法，可以得到第二个系数表 \(D(\lambda)\)：
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
于是，真正的 \(t\) 位 simber 数量就是
$$N_t=A_t-B_{t-1}.$$
当 \(t=2\) 时，允许前导零的 simber 字符串可以直接分类。第一类是重复的偶数字：
$$00,\ 22,\ 44,\ 66,\ 88,$$
一共 \(5\) 个。第二类是两个不同奇数字组成的有序字符串，数量为 \(5\cdot 4=20\)。因此
$$A_2=25.$$
其中只有 \(00\) 以前导零开头，所以 \(B_1=1\)，从而
$$N_2=A_2-B_1=25-1=24.$$
一位数的 simber 恰好是 \(1,3,5,7,9\)，因此 \(N_1=5\)。于是
$$Q(2)=N_1+N_2=5+24=29.$$
这个小例子正好说明了通用方法在做什么：它不是改变计数逻辑，而是把原本需要手工分类的过程压缩成统一的代数表达式。
把所有精确位数的贡献从 \(1\) 加到 \(n\)，得到
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
当 \(\lambda\neq 0,1\) 时，内部求和是标准几何级数：
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}.$$
而特殊值需要单独处理：
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
所有运算都在
$$M=1{,}000{,}000{,}123$$
这个模数下进行，所以除以 \(\lambda-1\) 与除以 \(2^{10}\) 都通过模逆元完成。
十进制字母表是固定的。五个奇数字各自只可能贡献 \(\{0,+1,-1\}\) 中的一个权重，五个偶数字各自只可能贡献 \(\{+1,-1\}\) 中的一个权重，所以 \(\lambda\) 的取值范围只能落在 \(-10\) 到 \(10\) 之间。也就是说，合并之后最多只有 \(21\) 个不同的幂需要计算。真正复杂的组合信息已经被压缩进两个很小的系数表里，剩余工作只是快速模幂和短几何级数求和。
C++、Python 和 Java 实现都先直接从这些投影器因子构造两个系数表。第一个系数表对应“所有长度为 \(t\) 的字符串”；第二个系数表对应“首位为 \(0\) 的情况需要扣除”的修正，其中后缀里的数字 \(0\) 必须出现奇数次。两张表在构造时都只按 \(\lambda\) 分组，因为在多项式求和之后，真正保留下来的只有这个总权重。
对于给定的 \(n\)，实现会把第一张表与 \(\sum_{t=1}^{n}\lambda^t\) 配对，把第二张表与 \(\sum_{s=0}^{n-1}\lambda^s\) 配对。几何级数闭式中的 \(\lambda^n\) 通过快速模幂计算，最后的 \(2^{-10}\) 也通过模逆元乘回去。
最后，程序对 \(u=1,2,\dots,39\) 依次计算 \(Q(2^u)\)，并把结果在模 \(M\) 下累加。同时它还验证两个检查点：
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
并用直接暴力计数确认小规模情形 \(Q(4)\)。
由于十进制数字集合固定，构造这两张系数表只需要常数时间和常数空间。合并后每张表中非零的 \(\lambda\) 项非常少，而且一定落在 \(-10\) 到 \(10\) 之间。
因此每次计算 \(Q(n)\) 时，只需要遍历这几个 \(\lambda\) 项。每一项主要成本是一次 \(O(\log n)\) 的快速模幂，所以单次查询复杂度为 \(O(L\log n)\)，其中 \(L\) 是不同 \(\lambda\) 值的个数，而本题中的 \(L\) 很小。总共只需求 \(39\) 次，运行时间极低，内存使用保持在 \(O(L)\)。
Положительное целое число называется simber, если каждая чётная цифра встречается чётное число раз, а каждая нечётная цифра, которая вообще встречается, встречается нечётное число раз. Если \(Q(n)\) обозначает количество simber-чисел, меньших \(10^n\), то требуется вычислить
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
Поскольку \(2^{39}\) огромно, прямой перебор по длинам невозможен. Поэтому решение переводит условия на чётность числа вхождений цифр в алгебраические проекторы, сжимает подсчёт для каждой фиксированной длины в короткую линейную комбинацию степеней \(\lambda^t\), а затем суммирует эти степени как геометрические прогрессии по заданному модулю.
Обозначим через \(E=\{0,2,4,6,8\}\) множество чётных цифр, а через \(O=\{1,3,5,7,9\}\) множество нечётных. Для десятичной строки пусть \(c_d\) означает число вхождений цифры \(d\).
Для чётной цифры допустимы количества \(0,2,4,\dots\), поэтому её индикатор равен
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}.$$
Для нечётной цифры допустимы количества \(0,1,3,5,\dots\): ноль разрешён, а любое положительное чётное число запрещено. Удобная форма такова:
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2},$$
где используется стандартное соглашение \(0^0=1\). Эта формула даёт \(1\) при \(c=0\), даёт \(1\) при нечётном \(c\) и даёт \(0\) при положительном чётном \(c\).
Пусть \(A_t\) — число десятичных строк длины \(t\), удовлетворяющих условию simber при разрешённом ведущем нуле. Если вектор счётчиков равен \((c_0,\dots,c_9)\), то
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o).$$
После умножения на \(2^{10}\) и раскрытия проекторов каждая чётная цифра даёт выбор веса \(+1\) или \(-1\), а каждая нечётная цифра — выбор веса \(0\), \(+1\) или \(-1\) с коэффициентами \(2\), \(1\) и \(-1\). Для одного полного глобального выбора весов \(w_0,\dots,w_9\) многочленный тождественный переход даёт
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t.$$
Следовательно, важны уже не сами цифры, а только сумма выбранных весов. Если \(a\) цифр дают \(+1\), а \(b\) цифр дают \(-1\), то возникает вклад \(\lambda^t\), где \(\lambda=a-b\). После объединения одинаковых значений \(\lambda\) получается небольшая таблица коэффициентов \(C(\lambda)\):
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
Положительное число ровно из \(t\) цифр соответствует строке длины \(t\), которая не начинается с нуля. Поэтому нужно отдельно вычесть simber-строки, у которых первый символ равен \(0\).
Если убрать этот ведущий ноль, останется суффикс длины \(t-1\). Поскольку цифра \(0\) уже использована один раз, её оставшееся количество должно быть нечётным, чтобы общее число нулей стало чётным. Остальные четыре ненулевые чётные цифры продолжают подчиняться обычному чётному правилу, а пять нечётных цифр — правилу «ноль или нечётно». Поэтому для выделенной цифры \(0\) используется
$$J(c)=\frac{1-(-1)^c}{2},$$
то есть индикатор нечётного количества. Пусть \(B_s\) — число суффиксов длины \(s\) с этой модифицированной ролью цифры \(0\). Тогда тем же самым аргументом раскрытия и группировки получаем вторую таблицу коэффициентов \(D(\lambda)\):
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
Отсюда число настоящих \(t\)-значных simber-чисел равно
$$N_t=A_t-B_{t-1}.$$
Для \(t=2\) simber-строки с разрешённым ведущим нулём легко описать явно. Во-первых, есть пять строк с повторяющейся чётной цифрой:
$$00,\ 22,\ 44,\ 66,\ 88,$$
во-вторых, есть \(5\cdot 4=20\) упорядоченных строк из двух различных нечётных цифр. Значит,
$$A_2=25.$$
Среди них только строка \(00\) начинается с нуля, поэтому \(B_1=1\) и
$$N_2=A_2-B_1=25-1=24.$$
Однозначные simber-числа — это \(1,3,5,7,9\), так что \(N_1=5\). Следовательно,
$$Q(2)=N_1+N_2=5+24=29.$$
Этот маленький пример показывает, что общий метод не меняет логику подсчёта, а просто делает её вычислимой для очень больших \(n\).
Теперь суммируем вклады точной длины от \(1\) до \(n\):
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
Для \(\lambda\neq 0,1\) внутренние суммы имеют вид
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}.$$
Особые случаи обрабатываются отдельно:
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
Вся арифметика ведётся по модулю
$$M=1{,}000{,}000{,}123,$$
поэтому деление на \(\lambda-1\) и на \(2^{10}\) реализуется умножением на обратные элементы по модулю.
Десятичный алфавит фиксирован. Каждая из пяти нечётных цифр вносит один из весов \(\{0,+1,-1\}\), а каждая из пяти чётных цифр — один из весов \(\{+1,-1\}\). Поэтому \(\lambda\) может лежать только в диапазоне от \(-10\) до \(10\), то есть после объединения остаётся не более \(21\) различных степеней. Вся трудная комбинаторика сжимается в две очень маленькие таблицы коэффициентов, а оставшаяся работа — это быстрая модульная степень и короткие геометрические суммы.
Реализации на C++, Python и Java строят две таблицы коэффициентов напрямую из проекторов. Одна таблица соответствует всем строкам длины \(t\), другая — поправке на ведущий ноль, в которой цифра \(0\) должна встречаться в суффиксе нечётное число раз. В обоих случаях развёртка группируется только по значению \(\lambda\), потому что именно эта величина остаётся после применения многочленного тождества.
Для заданного \(n\) реализация подставляет первую таблицу в \(\sum_{t=1}^{n}\lambda^t\), а вторую — в \(\sum_{s=0}^{n-1}\lambda^s\). Быстрое модульное возведение в степень используется внутри замкнутых форм этих геометрических рядов, а множитель \(2^{-10}\) применяется через модульный обратный элемент.
Затем программа вычисляет \(Q(2^u)\) для \(u=1,2,\dots,39\) и накапливает ответ по модулю \(M\). Кроме того, она проверяет два контрольных значения,
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
а также подтверждает малый случай \(Q(4)\) прямым полным перебором.
Так как набор десятичных цифр фиксирован, построение двух таблиц коэффициентов требует лишь постоянного времени и постоянной памяти. После объединения каждая таблица содержит совсем немного ненулевых значений \(\lambda\), ограниченных диапазоном от \(-10\) до \(10\).
Поэтому каждое вычисление \(Q(n)\) сводится к короткому проходу по этим значениям, а каждый член требует \(O(\log n)\) времени на модульное возведение в степень. Итак, одна вычислительная сессия стоит \(O(L\log n)\), где \(L\) — число различных значений \(\lambda\), причём в этой задаче \(L\) очень мало. Сумма по всем 39 запросам легко укладывается в практические ограничения, а память остаётся \(O(L)\).
يسمى العدد الصحيح الموجب simber إذا كان كل رقم زوجي يظهر عددًا زوجيًا من المرات، وكان كل رقم فردي يظهر أصلًا يظهر عددًا فرديًا من المرات. وإذا رمزنا بعدد الأعداد simber الأصغر من \(10^n\) بالرمز \(Q(n)\)، فالمطلوب هو حساب
$$\sum_{u=1}^{39} Q(2^u)\pmod{1{,}000{,}000{,}123}.$$
ولأن \(2^{39}\) هائل جدًا، فلا يمكن تعداد الأعداد مباشرة حسب عدد الخانات. لذلك تُحوِّل الفكرة الأساسية شروط زوجية/فردية تكرار الأرقام إلى مُسقِّطات جبرية، ثم تختزل عدَّ كل طول ثابت إلى تركيب خطي قصير من حدود على الصورة \(\lambda^t\)، ثم تجمع هذه الحدود باستعمال مجاميع هندسية تحت المودولو المطلوب.
لنكتب \(E=\{0,2,4,6,8\}\) لمجموعة الأرقام الزوجية و\(O=\{1,3,5,7,9\}\) لمجموعة الأرقام الفردية. وبالنسبة إلى أي سلسلة عشرية، نرمز بعدد مرات ظهور الرقم \(d\) بالرمز \(c_d\).
بالنسبة إلى الرقم الزوجي، القيم المسموح بها هي \(0,2,4,\dots\)، ولذلك يكون مؤشر القبول
$$I_{\mathrm{even}}(c)=\frac{1+(-1)^c}{2}.$$
أما الرقم الفردي فالقيم المسموح بها هي \(0,1,3,5,\dots\): الظهور صفر مرة مسموح، لكن أي عدد زوجي موجب من التكرارات مرفوض. والصيغة المناسبة للتوسيع هي
$$I_{\mathrm{odd}}(c)=\delta_{c,0}+\frac{1-(-1)^c}{2}=\frac{2\cdot 0^c+1^c-(-1)^c}{2},$$
مع استعمال الاصطلاح المعتاد \(0^0=1\). هذه الصيغة تعطي \(1\) عندما \(c=0\)، وتعطي \(1\) عندما يكون \(c\) فرديًا، وتعطي \(0\) عندما يكون \(c\) زوجيًا موجبًا.
ليكن \(A_t\) عدد السلاسل العشرية ذات الطول \(t\) التي تحقق شرط simber مع السماح بالصفر في البداية. إذا كان متجه العد هو \((c_0,\dots,c_9)\)، فإن
$$A_t=\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{e\in E} I_{\mathrm{even}}(c_e)\prod_{o\in O} I_{\mathrm{odd}}(c_o).$$
بعد ضرب هذا التعبير في \(2^{10}\) وتوسيع جميع المُسقِّطات، يساهم كل رقم زوجي بوزن \(+1\) أو \(-1\)، بينما يساهم كل رقم فردي بوزن \(0\) أو \(+1\) أو \(-1\) مع معاملات \(2\) و\(1\) و\(-1\) على الترتيب. وعند اختيار أوزان كاملة \(w_0,\dots,w_9\)، يعطي مبرهنة متعددة الحدود
$$\sum_{\substack{c_0+\cdots+c_9=t\\ c_d\ge 0}} \frac{t!}{c_0!\cdots c_9!}\prod_{d=0}^{9} w_d^{\,c_d}=(w_0+\cdots+w_9)^t.$$
وهذا يعني أن هوية الأرقام نفسها لم تعد مهمة؛ المهم فقط هو مجموع الأوزان. فإذا ساهم \(a\) أرقام بالوزن \(+1\) وساهم \(b\) أرقام بالوزن \(-1\)، فإن الحد الناتج هو \(\lambda^t\) حيث
$$\lambda=a-b.$$
وبعد جمع كل الحدود التي تعطي القيمة نفسها لـ \(\lambda\)، نحصل على جدول معاملات صغير \(C(\lambda)\) بحيث
$$A_t=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} C(\lambda)\lambda^t.$$
العدد الصحيح الموجب ذو \(t\) خانات يقابل سلسلة طولها \(t\) ولا تبدأ بالصفر. لذلك لا يكفي عدّ جميع السلاسل الموافقة للشرط؛ بل يجب طرح السلاسل simber التي يكون أول رمز فيها هو \(0\).
إذا حذفنا هذا الصفر القائد، بقي لاحقة طولها \(t-1\). وبما أن الرقم \(0\) ظهر مرة واحدة مسبقًا، فيجب أن يكون عدد مرات ظهوره في اللاحقة عددًا فرديًا حتى يصبح العدد الكلي لمرات ظهور \(0\) زوجيًا. أما الأرقام الزوجية الأربعة غير الصفرية فتبقى على شرطها الزوجي المعتاد، وتبقى الأرقام الفردية الخمسة على شرطها المعتاد «صفر أو عدد فردي». لذلك يستخدم الرقم \(0\) المميز الصيغة
$$J(c)=\frac{1-(-1)^c}{2},$$
وهي مؤشر العد الفردي. وليكن \(B_s\) عدد اللواحق ذات الطول \(s\) التي تحقق هذه القاعدة المعدلة للرقم \(0\). وبالحجة نفسها الخاصة بالتوسيع والتجميع نحصل على جدول معاملات ثانٍ \(D(\lambda)\):
$$B_s=\frac{1}{2^{10}}\sum_{\lambda=-10}^{10} D(\lambda)\lambda^s.$$
ومن ثم يكون عدد أعداد simber الحقيقية ذات الطول \(t\) هو
$$N_t=A_t-B_{t-1}.$$
عندما \(t=2\)، يمكن تصنيف سلاسل simber المسموح فيها بالصفر القائد بسهولة. يوجد خمسة سلاسل فيها رقم زوجي مكرر:
$$00,\ 22,\ 44,\ 66,\ 88,$$
وهناك أيضًا \(5\cdot 4=20\) سلسلة مرتبة مكوّنة من رقمين فرديين مختلفين. إذن
$$A_2=25.$$
ومن بين هذه السلاسل لا تبدأ بالصفر إلا \(00\)، ولذلك \(B_1=1\) وبالتالي
$$N_2=A_2-B_1=25-1=24.$$
أما أعداد simber ذات الخانة الواحدة فهي \(1,3,5,7,9\)، أي إن \(N_1=5\). ومن هنا
$$Q(2)=N_1+N_2=5+24=29.$$
هذا المثال الصغير هو بالضبط ما تعممه الطريقة العامة آليًا عندما يصبح \(n\) كبيرًا جدًا.
نجمع الآن مساهمات الأطوال الدقيقة من \(1\) حتى \(n\):
$$Q(n)=\sum_{t=1}^{n} N_t=\frac{1}{2^{10}}\left(\sum_{\lambda} C(\lambda)\sum_{t=1}^{n}\lambda^t-\sum_{\lambda} D(\lambda)\sum_{s=0}^{n-1}\lambda^s\right).$$
عندما \(\lambda\neq 0,1\) تكون المجاميع الداخلية
$$\sum_{t=1}^{n}\lambda^t=\lambda\frac{\lambda^n-1}{\lambda-1},\qquad \sum_{s=0}^{n-1}\lambda^s=\frac{\lambda^n-1}{\lambda-1}.$$
أما القيم الخاصة فتعالج منفصلة:
$$\sum_{t=1}^{n}1^t=n,\qquad \sum_{s=0}^{n-1}1^s=n,$$
$$\sum_{t=1}^{n}0^t=0,\qquad \sum_{s=0}^{n-1}0^s=1\quad (n\ge 1).$$
وجميع الحسابات تتم modulo
$$M=1{,}000{,}000{,}123,$$
ولذلك يتحول القسمة على \(\lambda-1\) وعلى \(2^{10}\) إلى ضرب بالمعكوس الضربي modulo.
الأبجدية العشرية ثابتة. كل واحد من الأرقام الفردية الخمسة يساهم بأحد الأوزان \(\{0,+1,-1\}\)، وكل واحد من الأرقام الزوجية الخمسة يساهم بأحد الأوزان \(\{+1,-1\}\). لذلك لا يمكن أن تقع \(\lambda\) إلا بين \(-10\) و\(10\)، أي إن عدد القوى المختلفة بعد التجميع لا يتجاوز \(21\). وهكذا تُضغط البنية التوافقية الصعبة كلها داخل جدولين صغيرين جدًا من المعاملات، وتبقى المهمة الحسابية محصورة في الأسس السريعة modulo ومجاميع هندسية قصيرة.
تبني تطبيقات C++ وPython وJava جدولي المعاملات مباشرة من عوامل المُسقِّطات. الجدول الأول يمثل جميع السلاسل ذات الطول \(t\)، والجدول الثاني يمثل تصحيح الصفر القائد حيث يجب أن يظهر الرقم \(0\) عددًا فرديًا من المرات داخل اللاحقة. وفي الحالتين لا يُحتفَظ إلا بالتجميع حسب قيمة \(\lambda\)، لأن هذه هي الكمية الوحيدة التي تبقى بعد تطبيق صيغة متعددة الحدود.
ولقيمة \(n\) المطلوبة، تُقيِّم الشيفرة الجدول الأول مع \(\sum_{t=1}^{n}\lambda^t\) والجدول الثاني مع \(\sum_{s=0}^{n-1}\lambda^s\). وتُستخدم الأسس السريعة modulo داخل الصيغ المغلقة لهذه المجاميع الهندسية، ثم يُطبَّق العامل النهائي \(2^{-10}\) باستعمال معكوس ضربي modulo.
في النهاية يحسب البرنامج القيم \(Q(2^u)\) من أجل \(u=1,2,\dots,39\) ثم يجمعها modulo \(M\). كما أنه يتحقق من نقطتي فحص هما
$$Q(7)=287975,\qquad Q(100)\equiv 123864868 \pmod{M},$$
ويؤكد أيضًا الحالة الصغيرة \(Q(4)\) بالمقارنة مع عدّ مباشر كامل.
بما أن مجموعة الأرقام العشرية ثابتة، فإن بناء جدولي المعاملات يحتاج إلى زمن ثابت وذاكرة ثابتة. وبعد التجميع، يحتوي كل جدول على عدد صغير جدًا من قيم \(\lambda\) غير الصفرية، وجميعها محصورة بين \(-10\) و\(10\).
لذلك فإن كل حساب لـ \(Q(n)\) يحتاج فقط إلى دورة قصيرة على هذه القيم، وكل حد يكلف \(O(\log n)\) بسبب الأس السريع modulo. وعليه فإن كلفة الاستعلام الواحد هي \(O(L\log n)\)، حيث \(L\) هو عدد قيم \(\lambda\) المختلفة، وهو صغير جدًا هنا. أما مجموع القيم التسع والثلاثين المطلوبة فعملي جدًا، ويظل استخدام الذاكرة في حدود \(O(L)\).