Let \(D(n)\) denote the number of positive integers \(x<10^n\) whose usual decimal representation has a digit appearing in more than half of its positions. Such a digit is called dominating. The goal is to compute \(D(2022)\) modulo \(10^9+7\).
A direct scan over all numbers below \(10^{2022}\) is hopeless. The key simplification is to count valid numbers by decimal length and by the exact number of times the dominating digit appears.
For each length \(\ell\), let \(A(\ell)\) be the number of dominating \(\ell\)-digit numbers. Then
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
The remaining task is to derive a closed formula for \(A(\ell)\).
Assume a length-\(\ell\) number has a dominating digit occurring exactly \(k\) times. By definition, domination means
$$k>\frac{\ell}{2}.$$
This strict inequality is important: two different digits cannot both appear more than half the time. So every dominating number has a unique dominating digit and contributes to exactly one value of \(k\).
Therefore, for fixed \(\ell\), the valid multiplicities are
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell.$$
If \(N(\ell,k)\) denotes the number of \(\ell\)-digit numbers whose dominating digit appears exactly \(k\) times, then
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$$
Fix \(\ell\) and \(k\). First choose which \(k\) positions contain the dominating digit. There are
$$\binom{\ell}{k}$$
such position sets.
Once those positions are chosen, the remaining \(\ell-k\) positions must use digits different from the dominating digit. No extra condition is needed to stop another digit from also dominating, because the non-dominating positions are too few:
$$\ell-k<k.$$
So the combinatorics reduces to counting how many assignments are possible for one fixed choice of the \(k\) dominant positions.
The first digit of an \(\ell\)-digit number cannot be \(0\), so the count is not just \(10\cdot 9^{\ell-k}\). The implementations implicitly resolve this by splitting into two cases for a fixed set of dominant positions.
If the first position is one of the \(k\) dominant positions, then the dominating digit itself must be nonzero. There are \(9\) choices for that digit, and every remaining non-dominant position has \(9\) choices because it may use any digit except the dominating one. This case contributes
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$$
If the first position is not dominant, then the dominating digit may be zero or nonzero. Summing those possibilities gives
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2$$
choices for the pair consisting of the dominating digit and the first digit: \(9\) nonzero dominant digits with \(8\) legal first digits each, or the dominant digit \(0\) with \(9\) legal first digits. The other \(\ell-k-1\) non-dominant positions again have \(9\) choices each, so this case contributes
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}.$$
Both cases give the same value. That is why every chosen position set contributes exactly \(9^{\ell-k+1}\).
Multiplying the number of position sets by the number of valid assignments for each set gives
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$$
Hence the number of dominating numbers of length \(\ell\) is
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$$
Adding the contributions of all lengths from \(1\) to \(n\) yields the final formula
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
This is the exact quantity accumulated by the C++, Python, and Java implementations.
For \(n=4\), compute the contribution of each length separately.
For \(\ell=1\), only \(k=1\) is possible:
$$\binom{1}{1}9^1=9.$$
For \(\ell=2\), only \(k=2\) is allowed:
$$\binom{2}{2}9^1=9.$$
For \(\ell=3\), the allowed values are \(k=2\) and \(k=3\):
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
For \(\ell=4\), the allowed values are \(k=3\) and \(k=4\):
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
Therefore
$$D(4)=9+9+252+333=603,$$
which matches the small checkpoint used by the implementations.
The implementations all follow the same numerical strategy. They precompute factorials, inverse factorials, and powers of \(9\) up to the requested limit \(n\). Because the modulus
$$M=10^9+7$$
is prime, inverse factorials can be obtained using Fermat's little theorem:
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
After that precomputation, every binomial coefficient \(\binom{\ell}{k}\) is available in constant time. The implementation then loops over all lengths \(\ell=1,\dots,n\), loops over all valid dominating multiplicities \(k>\ell/2\), evaluates the term \(\binom{\ell}{k}9^{\ell-k+1}\) modulo \(M\), and accumulates the result.
Building the factorial, inverse-factorial, and power tables costs \(O(n)\) time and \(O(n)\) memory. The main computation is a double sum over all pairs \((\ell,k)\) with \(1\le \ell\le n\) and \(k>\ell/2\), which performs
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2)$$
constant-time updates. Therefore the total running time is \(O(n^2)\) and the memory usage is \(O(n)\).
Sei \(D(n)\) die Anzahl positiver ganzer Zahlen \(x<10^n\), deren übliche Dezimalschreibweise eine Ziffer enthält, die in mehr als der Hälfte aller Stellen vorkommt. Eine solche Ziffer heißt dominierend. Gesucht ist \(D(2022)\) modulo \(10^9+7\).
Eine direkte Enumeration aller Zahlen unter \(10^{2022}\) ist unmöglich. Daher zählt die Lösung die gültigen Zahlen nach ihrer Länge und nach der exakten Häufigkeit der dominierenden Ziffer.
Für jede Länge \(\ell\) bezeichne \(A(\ell)\) die Anzahl dominierender \(\ell\)-stelliger Zahlen. Dann gilt
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
Es bleibt also, eine geschlossene Formel für \(A(\ell)\) herzuleiten.
Angenommen, eine \(\ell\)-stellige Zahl besitzt eine dominierende Ziffer, die genau \(k\)-mal vorkommt. Dominanz bedeutet
$$k>\frac{\ell}{2}.$$
Wegen dieser strengen Ungleichung können nicht zwei verschiedene Ziffern gleichzeitig dominant sein. Jede gültige Zahl besitzt also genau eine dominierende Ziffer und gehört zu genau einem Wert \(k\).
Für feste Länge \(\ell\) sind deshalb genau die Werte
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell$$
zulässig. Bezeichnet \(N(\ell,k)\) die Anzahl \(\ell\)-stelliger Zahlen, bei denen die dominierende Ziffer genau \(k\)-mal erscheint, dann folgt
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$$
Fixiere \(\ell\) und \(k\). Zuerst wählt man die \(k\) Stellen aus, an denen die dominierende Ziffer steht. Dafür gibt es
$$\binom{\ell}{k}$$
Möglichkeiten.
Die übrigen \(\ell-k\) Stellen müssen mit Ziffern gefüllt werden, die von der dominierenden Ziffer verschieden sind. Eine zusätzliche Bedingung, damit keine zweite Ziffer dominant wird, ist nicht nötig, denn es bleiben zu wenige Plätze übrig:
$$\ell-k<k.$$
Somit reduziert sich das Problem darauf, für eine fest gewählte Menge dominierender Positionen die zulässigen Ziffernbelegungen zu zählen.
Die erste Stelle einer \(\ell\)-stelligen Dezimalzahl darf nicht \(0\) sein. Deshalb ist die Zahl der Belegungen nicht einfach \(10\cdot 9^{\ell-k}\). Die Implementierungen lösen das implizit durch eine Fallunterscheidung für eine feste Positionsmenge.
Liegt die erste Stelle unter den \(k\) dominierenden Positionen, dann muss die dominierende Ziffer selbst ungleich \(0\) sein. Dafür gibt es \(9\) Möglichkeiten. Jede übrige nicht-dominierende Stelle kann dann jede der \(9\) Ziffern annehmen, die von der dominierenden Ziffer verschieden sind. Dieser Fall liefert
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$$
Liegt die erste Stelle nicht unter den dominierenden Positionen, dann darf die dominierende Ziffer null oder nichtnull sein. Summiert man beide Möglichkeiten, erhält man
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2$$
Möglichkeiten für das Paar aus dominierender Ziffer und erster Ziffer: \(9\) nichtnullige dominante Ziffern mit jeweils \(8\) legalen ersten Ziffern oder die dominante Ziffer \(0\) mit \(9\) legalen ersten Ziffern. Die übrigen \(\ell-k-1\) nicht-dominierenden Stellen haben wieder jeweils \(9\) Möglichkeiten, also trägt auch dieser Fall
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}$$
bei. Beide Fälle liefern also denselben Wert. Genau deshalb trägt jede gewählte Positionsmenge exakt \(9^{\ell-k+1}\) bei.
Multipliziert man die Anzahl der Positionsmengen mit der Anzahl zulässiger Belegungen je Menge, so erhält man
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$$
Damit ist die Anzahl dominierender Zahlen der Länge \(\ell\)
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$$
Addiert man die Beiträge aller Längen von \(1\) bis \(n\), erhält man die Endformel
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
Genau diese Größe akkumulieren die C++-, Python- und Java-Implementierungen.
Für \(n=4\) berechnet man den Beitrag jeder Länge getrennt.
Für \(\ell=1\) ist nur \(k=1\) möglich:
$$\binom{1}{1}9^1=9.$$
Für \(\ell=2\) ist nur \(k=2\) erlaubt:
$$\binom{2}{2}9^1=9.$$
Für \(\ell=3\) sind \(k=2\) und \(k=3\) zulässig:
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
Für \(\ell=4\) sind \(k=3\) und \(k=4\) zulässig:
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
Also
$$D(4)=9+9+252+333=603,$$
genau der kleine Kontrollwert aus den Implementierungen.
Alle Implementierungen folgen demselben numerischen Plan. Zuerst werden Fakultäten, inverse Fakultäten und Potenzen von \(9\) bis zur benötigten Grenze \(n\) vorab berechnet. Da der Modulus
$$M=10^9+7$$
eine Primzahl ist, lassen sich inverse Fakultäten mit dem kleinen Satz von Fermat bestimmen:
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
Danach steht jeder Binomialkoeffizient \(\binom{\ell}{k}\) in \(O(1)\) Zeit zur Verfügung. Anschließend iteriert die Implementierung über alle Längen \(\ell=1,\dots,n\), über alle zulässigen Dominanzhäufigkeiten \(k>\ell/2\), berechnet den Term \(\binom{\ell}{k}9^{\ell-k+1}\) modulo \(M\) und addiert ihn zum Ergebnis.
Das Aufbauen der Fakultäts-, Inversen- und Potenztabellen kostet \(O(n)\) Zeit und \(O(n)\) Speicher. Die Hauptrechnung ist eine Doppelsumme über alle Paare \((\ell,k)\) mit \(1\le \ell\le n\) und \(k>\ell/2\); dabei werden
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2)$$
konstante Aktualisierungen ausgeführt. Damit beträgt die Gesamtlaufzeit \(O(n^2)\) und der Speicherbedarf \(O(n)\).
\(D(n)\), \(x<10^n\) koşulunu sağlayan pozitif tamsayılar arasında, normal onluk yazımında bir rakamı toplam basamak sayısının yarısından fazla kez görünen sayıların adedidir. Böyle bir rakama baskın rakam denir. Amaç \(D(2022)\) değerini \(10^9+7\) modunda bulmaktır.
\(10^{2022}\)'den küçük tüm sayıları tek tek denemek mümkün değildir. Bu yüzden çözüm, geçerli sayıları basamak uzunluğuna ve baskın rakamın tam kaç kez geçtiğine göre sayar.
Her \(\ell\) uzunluğu için \(A(\ell)\), baskın olan \(\ell\) basamaklı sayıların sayısı olsun. O zaman
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
Dolayısıyla ana iş, \(A(\ell)\) için kapalı bir ifade elde etmektir.
\(\ell\) basamaklı bir sayıda baskın rakamın tam \(k\) kez geçtiğini varsayalım. Baskın olma koşulu
$$k>\frac{\ell}{2}$$
şeklindedir.
Bu sıkı eşitsizlik nedeniyle iki farklı rakam aynı anda baskın olamaz. Yani her geçerli sayının baskın rakamı tektir ve tam bir adet \(k\) değerine karşılık gelir.
Bu nedenle sabit \(\ell\) için izin verilen değerler
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell$$
olur. Eğer \(N(\ell,k)\), baskın rakamı tam \(k\) kez geçen \(\ell\) basamaklı sayıların sayısıysa,
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k)$$
elde edilir.
\(\ell\) ve \(k\) sabit olsun. Önce baskın rakamın yer aldığı \(k\) konumu seçeriz. Bunun sayısı
$$\binom{\ell}{k}$$
kadardır.
Kalan \(\ell-k\) konumlar, baskın rakamdan farklı rakamlarla doldurulmalıdır. Başka bir rakamın da baskın olmasını ayrıca engellemeye gerek yoktur; çünkü geriye kalan yer sayısı zaten \(k\)'den küçüktür:
$$\ell-k<k.$$
Böylece problem, baskın konumlar kümesi sabitken kaç farklı rakam yerleşimi yapılabildiğini saymaya indirgenir.
\(\ell\) basamaklı bir sayının ilk basamağı \(0\) olamaz. Bu yüzden sayım doğrudan \(10\cdot 9^{\ell-k}\) değildir. Uygulamalar, sabit bir baskın konum kümesi için bunu iki duruma ayırarak çözer.
Eğer ilk basamak baskın konumlardan biriyse, baskın rakamın sıfır olmaması gerekir. Bu rakam için \(9\) seçim vardır. Kalan baskın olmayan her konum ise baskın rakam dışındaki \(9\) rakamdan biri olabilir. Bu durumun katkısı
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}$$
olur.
Eğer ilk basamak baskın değilse, baskın rakam sıfır da olabilir sıfır olmayan bir rakam da olabilir. Bu iki olasılığı birlikte sayınca
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2$$
elde edilir: sıfır olmayan \(9\) baskın rakam için ilk basamakta \(8\) yasal seçim veya baskın rakam \(0\) iken ilk basamakta \(9\) yasal seçim. Diğer \(\ell-k-1\) baskın olmayan konumların her biri yine \(9\) seçenek taşır. Dolayısıyla bu durumun katkısı da
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}$$
olur. Her iki durumda da aynı değer çıktığı için, seçilen her baskın konum kümesi tam olarak \(9^{\ell-k+1}\) katkı verir.
Konum seçimlerinin sayısı ile her seçim için geçerli yerleşim sayısını çarpınca
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}$$
bulunur. Böylece \(\ell\) basamaklı baskın sayı sayısı
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}$$
olur.
\(1\) ile \(n\) arasındaki tüm basamak uzunluklarını topladığımızda nihai ifade
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
şeklini alır. C++, Python ve Java uygulamaları tam olarak bu toplamı hesaplar.
\(n=4\) için her uzunluğun katkısını ayrı ayrı hesaplayalım.
\(\ell=1\) için yalnızca \(k=1\) mümkündür:
$$\binom{1}{1}9^1=9.$$
\(\ell=2\) için yalnızca \(k=2\) uygundur:
$$\binom{2}{2}9^1=9.$$
\(\ell=3\) için \(k=2\) ve \(k=3\) değerleri gelir:
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
\(\ell=4\) için \(k=3\) ve \(k=4\) değerleri gelir:
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
Dolayısıyla
$$D(4)=9+9+252+333=603,$$
ve bu değer uygulamalardaki küçük doğrulama sonucuyla aynıdır.
Üç uygulama da aynı sayısal planı izler. Önce \(n\)'e kadar faktöriyeller, ters faktöriyeller ve \(9\)'un kuvvetleri önceden hesaplanır. Çünkü modül
$$M=10^9+7$$
asal sayıdır; bu yüzden ters faktöriyel değerleri Fermat'nın küçük teoremi ile bulunabilir:
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
Böylece her bir \(\binom{\ell}{k}\) değeri ön hesaplamadan sonra sabit zamanda elde edilir. Uygulama daha sonra \(\ell=1,\dots,n\) uzunluklarını ve \(k>\ell/2\) koşulunu sağlayan tüm tekrar sayılarını dolaşır, \(\binom{\ell}{k}9^{\ell-k+1}\) terimini mod \(M\) altında hesaplar ve toplama ekler.
Faktöriyel, ters faktöriyel ve kuvvet tablolarının kurulması \(O(n)\) zaman ve \(O(n)\) bellek ister. Ana hesaplama, \(1\le \ell\le n\) ve \(k>\ell/2\) olan tüm \((\ell,k)\) çiftleri üzerinde bir çift toplamdır; burada
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2)$$
adet sabit zamanlı güncelleme yapılır. Sonuç olarak toplam süre \(O(n^2)\), bellek kullanımı ise \(O(n)\)'dir.
Sea \(D(n)\) la cantidad de enteros positivos \(x<10^n\) cuya representación decimal usual contiene un dígito que aparece en más de la mitad de sus posiciones. A ese dígito lo llamamos dominante. El objetivo es calcular \(D(2022)\) módulo \(10^9+7\).
Recorrer todos los números menores que \(10^{2022}\) no es viable. La idea es contar los números válidos por longitud decimal y por el número exacto de veces que aparece el dígito dominante.
Para cada longitud \(\ell\), sea \(A(\ell)\) el número de números dominantes de \(\ell\) cifras. Entonces
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
Por tanto, todo se reduce a obtener una fórmula cerrada para \(A(\ell)\).
Supongamos que un número de longitud \(\ell\) tiene un dígito dominante que aparece exactamente \(k\) veces. La condición de dominancia es
$$k>\frac{\ell}{2}.$$
Como la desigualdad es estricta, no puede haber dos dígitos distintos con frecuencia dominante al mismo tiempo. Así, cada número válido tiene un único dígito dominante y aporta a un único valor de \(k\).
Para una longitud fija \(\ell\), los valores permitidos son
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell.$$
Si \(N(\ell,k)\) denota el número de números de \(\ell\) cifras cuyo dígito dominante aparece exactamente \(k\) veces, entonces
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$$
Fijados \(\ell\) y \(k\), primero elegimos qué \(k\) posiciones contienen el dígito dominante. Hay
$$\binom{\ell}{k}$$
conjuntos de posiciones posibles.
Las \(\ell-k\) posiciones restantes deben usar dígitos distintos del dominante. No hace falta imponer una restricción extra para evitar que otro dígito también domine, porque quedan menos posiciones que \(k\):
$$\ell-k<k.$$
Por tanto, el problema se reduce a contar cuántas asignaciones de dígitos son posibles para un conjunto fijo de posiciones dominantes.
El primer dígito de un número decimal de \(\ell\) cifras no puede ser \(0\). Por eso el conteo no es simplemente \(10\cdot 9^{\ell-k}\). Las implementaciones resuelven esto separando dos casos para un conjunto fijo de posiciones dominantes.
Si la primera posición pertenece a las \(k\) posiciones dominantes, entonces el dígito dominante debe ser no nulo. Hay \(9\) opciones para ese dígito, y cada posición no dominante restante tiene \(9\) opciones, porque puede usar cualquier dígito salvo el dominante. Este caso aporta
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$$
Si la primera posición no es dominante, el dígito dominante puede ser cero o no cero. Al sumar ambas posibilidades obtenemos
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2$$
opciones para el par formado por el dígito dominante y el primer dígito: \(9\) dígitos dominantes no nulos con \(8\) primeros dígitos legales cada uno, o el dígito dominante \(0\) con \(9\) primeros dígitos legales. Las otras \(\ell-k-1\) posiciones no dominantes vuelven a tener \(9\) opciones cada una, así que este caso también aporta
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}.$$
Ambos casos producen el mismo valor. Por eso cada conjunto elegido de posiciones aporta exactamente \(9^{\ell-k+1}\).
Multiplicando el número de conjuntos de posiciones por el número de asignaciones válidas para cada conjunto se obtiene
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$$
En consecuencia, el número de números dominantes de longitud \(\ell\) es
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$$
Al sumar las contribuciones de todas las longitudes entre \(1\) y \(n\), llegamos a la fórmula final
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
Eso es exactamente lo que acumulan las implementaciones en C++, Python y Java.
Para \(n=4\), calculamos la contribución de cada longitud por separado.
Para \(\ell=1\), solo es posible \(k=1\):
$$\binom{1}{1}9^1=9.$$
Para \(\ell=2\), solo se permite \(k=2\):
$$\binom{2}{2}9^1=9.$$
Para \(\ell=3\), aparecen \(k=2\) y \(k=3\):
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
Para \(\ell=4\), aparecen \(k=3\) y \(k=4\):
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
Por lo tanto,
$$D(4)=9+9+252+333=603,$$
que coincide con la comprobación pequeña usada por las implementaciones.
Las implementaciones siguen el mismo plan numérico. Primero precalculan factoriales, factoriales inversos y potencias de \(9\) hasta el límite pedido \(n\). Como el módulo
$$M=10^9+7$$
es primo, los inversos se obtienen mediante el pequeño teorema de Fermat:
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
Después de esa preparación, cada coeficiente binomial \(\binom{\ell}{k}\) se obtiene en tiempo constante. Luego la implementación recorre todas las longitudes \(\ell=1,\dots,n\), todos los valores válidos \(k>\ell/2\), evalúa el término \(\binom{\ell}{k}9^{\ell-k+1}\) módulo \(M\) y lo suma al acumulado.
La construcción de las tablas de factoriales, inversos y potencias cuesta \(O(n)\) tiempo y \(O(n)\) memoria. El cálculo principal es una suma doble sobre todos los pares \((\ell,k)\) con \(1\le \ell\le n\) y \(k>\ell/2\), lo que realiza
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2)$$
actualizaciones de tiempo constante. En consecuencia, el tiempo total es \(O(n^2)\) y la memoria total es \(O(n)\).
记 \(D(n)\) 为所有满足 \(x<10^n\) 的正整数中，那些在通常十进制表示里存在某个数字，其出现次数严格超过总位数一半的数的个数。这个数字称为主导数字。题目要求计算 \(D(2022)\bmod (10^9+7)\)。
显然，不可能把小于 \(10^{2022}\) 的所有整数逐个枚举。真正可行的方法是按十进制长度分类，再按主导数字恰好出现多少次来做组合计数。
对每个长度 \(\ell\)，设 \(A(\ell)\) 表示所有主导的 \(\ell\) 位数的个数，则
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
因此核心问题变成：如何为固定长度 \(\ell\) 推导出 \(A(\ell)\) 的闭式。
设一个 \(\ell\) 位数中，主导数字恰好出现 \(k\) 次。根据定义，主导必须满足
$$k>\frac{\ell}{2}.$$
这个严格大于非常关键，因为它意味着不可能有两个不同的数字同时都出现超过一半的位置。换句话说，每个满足条件的数只有唯一的主导数字，也只会对应唯一的 \(k\)。
所以对于固定长度 \(\ell\)，允许的 \(k\) 取值范围是
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell.$$
若记 \(N(\ell,k)\) 为所有 \(\ell\) 位数中，主导数字恰好出现 \(k\) 次的个数，那么就有
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$$
固定 \(\ell\) 和 \(k\) 之后，第一步是从 \(\ell\) 个位置里选出 \(k\) 个位置放主导数字。这样的选法共有
$$\binom{\ell}{k}$$
种。
其余的 \(\ell-k\) 个位置必须填入与主导数字不同的数字。这里不需要额外再去限制“别的数字也不能主导”，因为剩余位置数本身就比 \(k\) 少：
$$\ell-k<k.$$
所以一旦主导位置集合确定，剩下的工作只是数清楚：对这个固定的位置集合，有多少种合法填法。
\(\ell\) 位十进制数的第一位不能是 \(0\)，因此合法填法并不是简单的 \(10\cdot 9^{\ell-k}\)。三个实现实际上都对应同一个两分类推导，只是把结果直接写成了闭式。
如果第一位正好属于那 \(k\) 个主导位置之一，那么主导数字本身必须是非零数字。主导数字有 \(9\) 种选择。剩余每个非主导位置都可以从除主导数字以外的 \(9\) 个数字中任选，所以这一类的贡献是
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$$
如果第一位不在主导位置中，那么主导数字既可能是零，也可能是非零。把两种情况合在一起计算，主导数字与第一位的组合数为
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2.$$
原因是：若主导数字是 \(1\) 到 \(9\) 中的某一个，则第一位必须是非零且不能等于主导数字，所以有 \(8\) 种；这样的主导数字有 \(9\) 个。若主导数字是 \(0\)，则第一位可以是任意非零数字，共 \(9\) 种。其余 \(\ell-k-1\) 个非主导位置每个仍有 \(9\) 种选法，因此这一类的贡献也是
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}.$$
两个分类得到完全相同的结果。因此，不管第一位是否属于主导位置，只要主导位置集合固定，它的总贡献始终都是 \(9^{\ell-k+1}\)。
把位置集合的数量和每个集合对应的合法填法数相乘，就得到
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$$
于是固定长度 \(\ell\) 的主导数个数为
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$$
把长度从 \(1\) 到 \(n\) 的贡献全部加起来，就得到最终公式
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
这正是 C++、Python 和 Java 实现所累加的数学对象。
当 \(n=4\) 时，可以把每个长度的贡献单独算出来。
当 \(\ell=1\) 时，只可能有 \(k=1\)：
$$\binom{1}{1}9^1=9.$$
当 \(\ell=2\) 时，只允许 \(k=2\)：
$$\binom{2}{2}9^1=9.$$
当 \(\ell=3\) 时，允许 \(k=2\) 和 \(k=3\)：
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
当 \(\ell=4\) 时，允许 \(k=3\) 和 \(k=4\)：
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
因此
$$D(4)=9+9+252+333=603,$$
这与实现中的小规模校验结果一致。
三个实现遵循完全相同的数值流程。首先预计算到目标上界 \(n\) 为止的阶乘、逆阶乘以及 \(9\) 的各次幂。由于模数
$$M=10^9+7$$
是质数，所以可以用费马小定理来得到逆元，从而得到逆阶乘：
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
这样一来，每个二项式系数 \(\binom{\ell}{k}\) 在预处理之后都能以 \(O(1)\) 时间取得。随后，程序双重循环枚举 \(\ell=1,\dots,n\) 以及所有满足 \(k>\ell/2\) 的 \(k\)，计算项 \(\binom{\ell}{k}9^{\ell-k+1}\) 在模 \(M\) 下的值，并把它加入答案。
构造阶乘、逆阶乘和幂表需要 \(O(n)\) 时间和 \(O(n)\) 空间。主计算部分是对所有满足 \(1\le \ell\le n\) 且 \(k>\ell/2\) 的 \((\ell,k)\) 做双重求和，其更新次数为
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2).$$
每次更新都是常数时间，因此总时间复杂度是 \(O(n^2)\)，空间复杂度是 \(O(n)\)。
Пусть \(D(n)\) обозначает количество положительных целых чисел \(x<10^n\), в обычной десятичной записи которых есть цифра, встречающаяся более чем в половине позиций. Такую цифру называют доминирующей. Требуется вычислить \(D(2022)\) по модулю \(10^9+7\).
Перебирать все числа меньше \(10^{2022}\) невозможно. Поэтому решение считает подходящие числа по длине записи и по точному числу вхождений доминирующей цифры.
Для каждой длины \(\ell\) обозначим через \(A(\ell)\) число доминирующих \(\ell\)-значных чисел. Тогда
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
Значит, основная задача состоит в том, чтобы вывести явную формулу для \(A(\ell)\).
Пусть в числе длины \(\ell\) доминирующая цифра встречается ровно \(k\) раз. Условие доминирования имеет вид
$$k>\frac{\ell}{2}.$$
Поскольку неравенство строгое, две разные цифры не могут одновременно встречаться чаще половины длины. Значит, у каждого подходящего числа доминирующая цифра единственна, и число попадает ровно в одно значение \(k\).
Следовательно, для фиксированной длины \(\ell\) допустимы именно такие значения:
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell.$$
Если \(N(\ell,k)\) обозначает число \(\ell\)-значных чисел, у которых доминирующая цифра встречается ровно \(k\) раз, то
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$$
Зафиксируем \(\ell\) и \(k\). Сначала выбираем те \(k\) позиций, на которых стоит доминирующая цифра. Число таких наборов равно
$$\binom{\ell}{k}.$$
Оставшиеся \(\ell-k\) позиции должны быть заполнены цифрами, отличными от доминирующей. Дополнительное ограничение, запрещающее другой цифре тоже стать доминирующей, не требуется, потому что свободных позиций уже меньше, чем \(k\):
$$\ell-k<k.$$
Тем самым задача сводится к подсчету числа допустимых заполнений для одного фиксированного набора доминирующих позиций.
Первая цифра \(\ell\)-значного десятичного числа не может быть нулем. Поэтому подсчет не равен просто \(10\cdot 9^{\ell-k}\). Реализованные программы используют эквивалентный разбор на два случая для фиксированного набора доминирующих позиций.
Если первая позиция входит в число доминирующих, то сама доминирующая цифра обязана быть ненулевой. Для нее есть \(9\) вариантов. Каждая оставшаяся недоминирующая позиция имеет \(9\) вариантов, потому что можно выбрать любую цифру, кроме доминирующей. Вклад этого случая равен
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$$
Если первая позиция не доминирующая, то доминирующая цифра может быть нулевой или ненулевой. Суммируя эти возможности, получаем
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2$$
вариантов для пары из доминирующей цифры и первой цифры: \(9\) ненулевых доминирующих цифр, для каждой из которых есть \(8\) допустимых первых цифр, или доминирующая цифра \(0\) и тогда \(9\) допустимых первых цифр. Остальные \(\ell-k-1\) недоминирующие позиции опять дают по \(9\) вариантов, так что вклад этого случая тоже равен
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}.$$
Оба случая дают одно и то же значение. Именно поэтому каждый выбранный набор позиций вносит ровно \(9^{\ell-k+1}\).
Умножая число наборов позиций на число допустимых заполнений для каждого набора, получаем
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$$
Следовательно, число доминирующих чисел длины \(\ell\) равно
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$$
Суммируя вклады всех длин от \(1\) до \(n\), получаем итоговую формулу
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
Именно эту величину накапливают реализации на C++, Python и Java.
При \(n=4\) удобно вычислить вклад каждой длины отдельно.
Для \(\ell=1\) возможно только \(k=1\):
$$\binom{1}{1}9^1=9.$$
Для \(\ell=2\) допустимо только \(k=2\):
$$\binom{2}{2}9^1=9.$$
Для \(\ell=3\) подходят \(k=2\) и \(k=3\):
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
Для \(\ell=4\) подходят \(k=3\) и \(k=4\):
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
Поэтому
$$D(4)=9+9+252+333=603,$$
что совпадает с малой проверкой, используемой в реализациях.
Все реализации следуют одному и тому же численному плану. Сначала предварительно вычисляются факториалы, обратные факториалы и степени числа \(9\) до нужного предела \(n\). Поскольку модуль
$$M=10^9+7$$
является простым числом, обратные значения находятся с помощью малой теоремы Ферма:
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
После этого любой биномиальный коэффициент \(\binom{\ell}{k}\) доступен за \(O(1)\). Затем реализация перебирает все длины \(\ell=1,\dots,n\), все допустимые значения \(k>\ell/2\), вычисляет слагаемое \(\binom{\ell}{k}9^{\ell-k+1}\) по модулю \(M\) и добавляет его к ответу.
Построение таблиц факториалов, обратных факториалов и степеней требует \(O(n)\) времени и \(O(n)\) памяти. Основной расчет представляет собой двойную сумму по всем парам \((\ell,k)\), где \(1\le \ell\le n\) и \(k>\ell/2\); число обновлений равно
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2).$$
Каждое обновление выполняется за константное время, поэтому общая временная сложность равна \(O(n^2)\), а потребление памяти равно \(O(n)\).
لنرمز بـ \(D(n)\) إلى عدد الأعداد الصحيحة الموجبة \(x<10^n\) التي تحتوي كتابتها العشرية المعتادة على رقم يظهر في أكثر من نصف الخانات. يسمى هذا الرقم الرقم المهيمن. المطلوب هو حساب \(D(2022)\) بترديد \(10^9+7\).
من المستحيل تعداد جميع الأعداد الأصغر من \(10^{2022}\) مباشرة. لذلك تعتمد الفكرة على العد التوافقي بحسب طول العدد العشري وبحسب عدد مرات ظهور الرقم المهيمن على وجه الدقة.
لكل طول \(\ell\)، لنكتب \(A(\ell)\) لعدد الأعداد ذات \(\ell\) خانة التي تمتلك رقماً مهيمنًا. عندئذٍ
$$D(n)=\sum_{\ell=1}^{n} A(\ell).$$
إذن المهمة الأساسية هي اشتقاق صيغة مغلقة لـ \(A(\ell)\).
افترض أن عدداً طوله \(\ell\) يحتوي على رقم مهيمن يظهر تماماً \(k\) مرات. شرط الهيمنة هو
$$k>\frac{\ell}{2}.$$
بما أن المتباينة صارمة، فلا يمكن لرقمين مختلفين أن يتجاوزا نصف الخانات في الوقت نفسه. لذلك كل عدد صالح يملك رقماً مهيمنًا وحيدًا، وينتمي إلى قيمة واحدة فقط من \(k\).
ومن ثم، لقيمة \(\ell\) الثابتة تكون القيم المسموح بها هي
$$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell.$$
إذا رمزنا بـ \(N(\ell,k)\) إلى عدد الأعداد ذات \(\ell\) خانة التي يظهر فيها الرقم المهيمن تماماً \(k\) مرات، فلدينا
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$$
ثبت \(\ell\) و\(k\). أولاً نختار المواضع \(k\) التي سيظهر فيها الرقم المهيمن. عدد هذه الاختيارات هو
$$\binom{\ell}{k}.$$
أما الخانات المتبقية وعددها \(\ell-k\) فيجب أن تحتوي على أرقام مختلفة عن الرقم المهيمن. ولا نحتاج إلى قيد إضافي لمنع رقم آخر من أن يصبح مهيمنًا، لأن عدد الخانات المتبقية أصلاً أصغر من \(k\):
$$\ell-k<k.$$
وهكذا تنخفض المسألة إلى عدّ عدد التعبئات الممكنة عندما تكون مجموعة المواضع المهيمنة ثابتة.
الخانة الأولى في عدد عشري ذي \(\ell\) خانات لا يجوز أن تكون \(0\). لذلك لا يكون العد ببساطة \(10\cdot 9^{\ell-k}\). التنفيذات الثلاثة تعتمد فعلياً على نفس البرهان القائم على حالتين لمجموعة مواضع مهيمنة ثابتة.
إذا كانت الخانة الأولى ضمن الخانات المهيمنة، فيجب أن يكون الرقم المهيمن غير صفري. لهذا الرقم \(9\) اختيارات. وكل خانة غير مهيمنة متبقية تملك \(9\) اختيارات، لأنها تستطيع أخذ أي رقم غير الرقم المهيمن. مساهمة هذه الحالة هي
$$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$$
أما إذا لم تكن الخانة الأولى ضمن المواضع المهيمنة، فيمكن أن يكون الرقم المهيمن صفراً أو غير صفر. بجمع الحالتين نحصل على
$$9\cdot 8 + 1\cdot 9 = 81 = 9^2$$
اختياراً للزوج المكوّن من الرقم المهيمن والرقم الموجود في الخانة الأولى: لدينا \(9\) أرقام مهيمنة غير صفرية ولكل منها \(8\) بدايات قانونية، أو الرقم المهيمن \(0\) ومعه \(9\) بدايات قانونية. أما الخانات غير المهيمنة الأخرى وعددها \(\ell-k-1\) فلكل واحدة منها \(9\) اختيارات أيضاً، لذا تكون مساهمة هذه الحالة كذلك
$$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}.$$
إذن الحالتان تعطيان القيمة نفسها. ولهذا فإن كل اختيار ثابت لمواضع الهيمنة يساهم بالضبط بمقدار \(9^{\ell-k+1}\).
بضرب عدد مجموعات المواضع في عدد التعبئات القانونية لكل مجموعة نحصل على
$$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$$
ومن ثم يصبح عدد الأعداد المهيمنة ذات الطول \(\ell\)
$$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$$
بجمع مساهمات جميع الأطوال من \(1\) إلى \(n\) نحصل على الصيغة النهائية
$$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$$
وهذه هي بالضبط الكمية التي تجمعها تنفيذات C++ وPython وJava.
عند \(n=4\)، نحسب مساهمة كل طول على حدة.
عندما \(\ell=1\)، لا يوجد إلا \(k=1\):
$$\binom{1}{1}9^1=9.$$
عندما \(\ell=2\)، القيمة المسموح بها الوحيدة هي \(k=2\):
$$\binom{2}{2}9^1=9.$$
عندما \(\ell=3\)، القيمتان المسموح بهما هما \(k=2\) و\(k=3\):
$$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$$
عندما \(\ell=4\)، القيمتان المسموح بهما هما \(k=3\) و\(k=4\):
$$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$$
إذن
$$D(4)=9+9+252+333=603,$$
وهو نفس الناتج الصغير الذي تستخدمه التنفيذات بوصفه نقطة تحقق.
التنفيذات الثلاثة تتبع الخطة العددية نفسها. فهي تسبق الحساب ببناء جداول العامليات، ومقلوبات العامليات، وقوى العدد \(9\) حتى الحد المطلوب \(n\). وبما أن الترديد
$$M=10^9+7$$
عدد أولي، يمكن الحصول على المقلوبات باستخدام مبرهنة فيرما الصغرى:
$$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$$
بعد هذا التحضير يصبح كل معامل ثنائي \(\binom{\ell}{k}\) متاحاً في زمن ثابت. ثم تدور الشيفرة على جميع الأطوال \(\ell=1,\dots,n\)، وعلى جميع قيم \(k\) التي تحقق \(k>\ell/2\)، وتحسب الحد \(\binom{\ell}{k}9^{\ell-k+1}\) بترديد \(M\)، ثم تضيفه إلى المجموع النهائي.
بناء جداول العامليات والمقلوبات والقوى يحتاج إلى \(O(n)\) زمناً و\(O(n)\) ذاكرة. أما الحساب الرئيسي فهو مجموع مزدوج على جميع الأزواج \((\ell,k)\) التي تحقق \(1\le \ell\le n\) و\(k>\ell/2\)، ويجري
$$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2)$$
تحديثات بزمن ثابت. لذلك يكون الزمن الكلي \(O(n^2)\) واستهلاك الذاكرة \(O(n)\).