A double pandigital number uses each digit \(0,1,\dots,9\) exactly twice, so every valid candidate has 20 digits. We must count those 20-digit numbers that do not start with \(0\) and are divisible by \(11\). Directly permuting a multiset of size 20 is far too expensive, so the solution reorganizes the search around how many copies of each digit are placed in odd positions and how many are forced into even positions.
The divisibility test for \(11\) is the key. For a 20-digit number, let positions \(1,3,5,\dots,19\) be the odd positions and \(2,4,6,\dots,20\) be the even positions. A number is divisible by \(11\) exactly when the alternating digit sum is a multiple of \(11\).
For each digit \(d\in\{0,1,\dots,9\}\), define \(k_d\) to be the number of copies of \(d\) placed in odd positions. Since each digit appears twice, we always have
$$k_d\in\{0,1,2\}.$$
There are 10 odd positions in total, so the first global constraint is
$$\sum_{d=0}^{9} k_d = 10.$$
Once the values \(k_0,\dots,k_9\) are fixed, the even positions are also fixed automatically: digit \(d\) appears
$$2-k_d$$
times in even positions.
Let
$$W=\sum_{d=0}^{9} d\,k_d$$
be the sum of the digits occupying odd positions. The sum of all digits \(0+1+\cdots+9\) is
$$45,$$
so the total sum of all 20 digits is
$$2\cdot 45=90.$$
Therefore the sum of digits in even positions is
$$90-W.$$
The divisibility rule for \(11\) requires
$$W-(90-W)\equiv 0 \pmod{11}.$$
Simplifying gives
$$2W-90\equiv 0 \pmod{11},$$
which is equivalent to
$$W-45\equiv 0 \pmod{11}.$$
So a vector \((k_0,\dots,k_9)\) is admissible precisely when
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Fix an admissible vector \((k_0,\dots,k_9)\). If we momentarily ignore the leading-zero restriction, the odd positions contain a multiset with multiplicities \(k_0,\dots,k_9\), so the number of arrangements is the multinomial count
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}.$$
However, position 1 is an odd position, and the number may not start with \(0\). If \(k_0=0\), no correction is needed. If \(k_0\ge 1\), then the invalid arrangements with leading zero are obtained by fixing one zero in the first position and arranging the remaining 9 odd positions:
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$$
Hence the valid odd-position count is
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$$
where \(N_{\mathrm{odd,lead0}}=0\) when \(k_0=0\).
The even positions contain the complementary multiset with multiplicities \(2-k_d\). There is no leading-digit restriction on even positions, so the count is simply
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$$
Once the odd and even arrangements are chosen independently, they interleave uniquely into one 20-digit number. Therefore the contribution of the fixed vector is
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$$
Each \(k_d\) can only be \(0\), \(1\), or \(2\), so there are at most
$$3^{10}=59{,}049$$
possible vectors to inspect. The final answer is
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$$
This formula is exactly what the implementations evaluate.
A smaller version makes the counting transparent. Suppose we only use digits \(0,1,2\), each twice, so the number has 6 digits. Then there are 3 odd positions and 3 even positions, and we need
$$k_0+k_1+k_2=3.$$
The sum of the distinct digits is
$$0+1+2=3,$$
so the divisibility condition becomes
$$k_1+2k_2-3\equiv 0 \pmod{11}.$$
Because the left-hand side lies between \(-3\) and \(3\), it must actually be \(0\), hence
$$k_1+2k_2=3.$$
With \(k_d\in\{0,1,2\}\), the only solution is
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$$
So odd positions contain one copy each of \(0,1,2\), and even positions do as well. The counts are
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
Therefore this miniature problem has
$$4\cdot 6=24$$
valid numbers. The full problem is the same counting argument with digits \(0\) through \(9\).
The C++, Python, and Java implementations precompute factorials from \(0!\) through \(20!\) so that every multinomial count can be formed by exact integer division. They then enumerate the ten values \(k_0,\dots,k_9\) with a depth-first search. During that search, the implementation keeps track of two running quantities: how many odd positions have already been filled and the current weighted odd-position sum \(\sum d\,k_d\).
When the search reaches digit \(9\), it first checks whether exactly 10 odd slots were used. If not, that branch is discarded immediately. It then checks the congruence
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Only terminal states satisfying both conditions contribute. For each such state, the implementation computes the unrestricted odd multinomial, subtracts the leading-zero cases when necessary, computes the even multinomial from the complementary counts \(2-k_d\), and adds the product to the running total.
The search space is already tiny, but the recursion still prunes many branches early because any partial assignment that has already used more than 10 odd slots cannot lead to a valid completion.
For the actual problem there are at most \(3^{10}=59{,}049\) vectors \((k_0,\dots,k_9)\). Each completed vector requires only \(O(10)\) arithmetic operations to evaluate the multinomial factors, so the overall running time is \(O(3^{10}\cdot 10)\), which is effectively constant for this fixed input size. The memory usage is \(O(10)\) for the current count vector and the small factorial table.
Eine doppelt pandigitale Zahl verwendet jede Ziffer \(0,1,\dots,9\) genau zweimal und besitzt daher immer 20 Stellen. Gesucht ist die Anzahl derjenigen 20-stelligen Zahlen, die nicht mit \(0\) beginnen und durch \(11\) teilbar sind. Eine direkte Permutation eines Multimengensatzes mit 20 Elementen wäre viel zu teuer, daher zählt die Lösung stattdessen, wie viele Kopien jeder Ziffer auf ungeraden Positionen liegen und wie viele dadurch automatisch auf gerade Positionen fallen.
Der zentrale Hebel ist die Teilbarkeitsregel für \(11\). Bei einer 20-stelligen Zahl seien die Positionen \(1,3,5,\dots,19\) ungerade und \(2,4,6,\dots,20\) gerade. Eine Zahl ist genau dann durch \(11\) teilbar, wenn ihre alternierende Ziffernsumme ein Vielfaches von \(11\) ist.
Für jede Ziffer \(d\in\{0,1,\dots,9\}\) sei \(k_d\) die Anzahl der Kopien von \(d\), die auf ungeraden Positionen liegen. Weil jede Ziffer zweimal vorkommt, gilt stets
$$k_d\in\{0,1,2\}.$$
Es gibt insgesamt 10 ungerade Positionen, also lautet die erste globale Bedingung
$$\sum_{d=0}^{9} k_d = 10.$$
Sobald \(k_0,\dots,k_9\) feststehen, sind die geraden Positionen automatisch bestimmt: Die Ziffer \(d\) erscheint dort genau
$$2-k_d$$
Mal.
Setze
$$W=\sum_{d=0}^{9} d\,k_d$$
für die Ziffernsumme auf den ungeraden Positionen. Die Summe der verschiedenen Ziffern ist
$$45,$$
also ist die Summe aller 20 verwendeten Ziffern
$$90.$$
Damit ist die Ziffernsumme auf den geraden Positionen gleich
$$90-W.$$
Die Teilbarkeitsregel liefert
$$W-(90-W)\equiv 0 \pmod{11}.$$
Nach Umformen ergibt sich
$$2W-90\equiv 0 \pmod{11},$$
und wegen der Invertierbarkeit von \(2\) modulo \(11\) ist das äquivalent zu
$$W-45\equiv 0 \pmod{11}.$$
Ein Vektor \((k_0,\dots,k_9)\) ist also genau dann zulässig, wenn
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Fixiere nun einen zulässigen Vektor \((k_0,\dots,k_9)\). Ignoriert man zunächst die führende Null, dann bilden die ungeraden Positionen eine Multimenge mit Häufigkeiten \(k_0,\dots,k_9\), also gibt es
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}$$
solche Anordnungen.
Da Position 1 ungerade ist, darf sie nicht \(0\) sein. Für \(k_0=0\) gibt es nichts abzuziehen. Für \(k_0\ge 1\) fixiert man eine Null an erster Stelle und permutiert die restlichen 9 ungeraden Positionen. Das ergibt
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$$
Somit ist die gültige Anzahl ungerader Anordnungen
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$$
wobei \(N_{\mathrm{odd,lead0}}=0\) gilt, falls \(k_0=0\).
Auf den geraden Positionen liegt die komplementäre Multimenge mit Häufigkeiten \(2-k_d\). Dort gibt es keine Einschränkung durch eine führende Ziffer, daher ist die Anzahl einfach
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$$
Wählt man unabhängig eine gültige ungerade und eine gerade Anordnung, dann verweben sie sich eindeutig zu genau einer 20-stelligen Zahl. Der Beitrag des festen Vektors lautet also
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$$
Jedes \(k_d\) kann nur \(0\), \(1\) oder \(2\) sein. Daher müssen höchstens
$$3^{10}=59{,}049$$
Vektoren geprüft werden. Die gesuchte Anzahl ist
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$$
Genau diese Summe werten die Implementierungen aus.
Ein kleines Beispiel macht die Idee sichtbar. Verwenden wir nur die Ziffern \(0,1,2\), jeweils zweimal, so entstehen 6-stellige Zahlen. Dann gibt es 3 ungerade und 3 gerade Positionen, also
$$k_0+k_1+k_2=3.$$
Die Summe der verschiedenen Ziffern ist
$$0+1+2=3,$$
daher lautet die Teilbarkeitsbedingung
$$k_1+2k_2-3\equiv 0 \pmod{11}.$$
Da die linke Seite nur zwischen \(-3\) und \(3\) liegen kann, muss sie tatsächlich \(0\) sein, also
$$k_1+2k_2=3.$$
Mit \(k_d\in\{0,1,2\}\) bleibt nur die Lösung
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$$
Die ungeraden Positionen enthalten also je eine Kopie von \(0,1,2\), und die geraden Positionen ebenso. Damit erhält man
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
Also gibt es in diesem Miniaturproblem genau
$$4\cdot 6=24$$
gültige Zahlen. Das echte Problem ist dieselbe Argumentation mit den Ziffern \(0\) bis \(9\).
Die C++-, Python- und Java-Implementierungen berechnen zunächst alle Fakultäten von \(0!\) bis \(20!\) vor, damit jede Multinomialzahl durch exakte ganzzahlige Division gebildet werden kann. Anschließend enumerieren sie die zehn Werte \(k_0,\dots,k_9\) per Tiefensuche. Während dieser Rekursion hält die Implementierung zwei laufende Größen fest: die bisher belegte Anzahl ungerader Positionen und die aktuelle gewichtete Summe \(\sum d\,k_d\) der ungeraden Ziffern.
Sobald die Rekursion die letzte Ziffer erreicht, wird zuerst geprüft, ob genau 10 ungerade Positionen belegt wurden. Falls nicht, wird der Zweig verworfen. Danach wird die Kongruenz
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}$$
überprüft. Nur wenn beide Bedingungen erfüllt sind, wird der Beitrag berechnet: die uneingeschränkte ungerade Multinomialzahl, gegebenenfalls minus die Fälle mit führender Null, multipliziert mit der geraden Multinomialzahl aus den komplementären Häufigkeiten \(2-k_d\).
Der Zustandsraum ist ohnehin klein, aber die Rekursion schneidet trotzdem viele Zweige früh ab, weil jede Teilbelegung mit mehr als 10 bereits belegten ungeraden Positionen unmöglich zu einer gültigen Lösung ergänzt werden kann.
Für das eigentliche Problem gibt es höchstens \(3^{10}=59{,}049\) Vektoren \((k_0,\dots,k_9)\). Für jeden vollständigen Vektor sind nur \(O(10)\) arithmetische Operationen nötig, um die Multinomialfaktoren auszuwerten. Die gesamte Laufzeit ist daher \(O(3^{10}\cdot 10)\) und für diese feste Eingabe praktisch konstant. Der Speicherbedarf ist \(O(10)\) für den aktuellen Zählvektor und die kleine Fakultätentabelle.
Çift pandijital bir sayı, \(0,1,\dots,9\) rakamlarının her birini tam iki kez kullanır; dolayısıyla her aday sayı 20 basamaklıdır. Bizden istenen, baştaki basamağı \(0\) olmayan ve \(11\) ile tam bölünebilen bu sayıların adedidir. 20 elemanlı bir çoklu kümenin tüm permütasyonlarını doğrudan denemek pratik değildir; bunun yerine çözüm, her rakamın tek konumlarda kaç kez göründüğünü sayarak problemi küçük bir kombinatorik toplam haline indirger.
Ana fikir, \(11\)'e bölünebilme kuralını tek ve çift konumlara ayrılmış bir sayma problemine dönüştürmektir. 20 basamaklı bir sayıda soldan sayınca \(1,3,5,\dots,19\) tek konumlar, \(2,4,6,\dots,20\) çift konumlardır. Bir sayının \(11\) ile bölünebilmesi için alternatif işaretli rakam toplamının \(11\)'in katı olması gerekir.
Her \(d\in\{0,1,\dots,9\}\) rakamı için, \(k_d\) değerini \(d\) rakamının tek konumlara yerleştirilen kopya sayısı olarak tanımlayalım. Her rakam iki kez bulunduğu için
$$k_d\in\{0,1,2\}.$$
Toplam 10 tek konum olduğundan ilk küresel koşul
$$\sum_{d=0}^{9} k_d = 10$$
şeklindedir. \(k_0,\dots,k_9\) seçildiğinde çift konumlardaki adetler artık otomatik belirlenir; \(d\) rakamı çift konumlarda
$$2-k_d$$
kez görünür.
Tek konumlardaki rakamların toplamını
$$W=\sum_{d=0}^{9} d\,k_d$$
olarak tanımlayalım. Farklı rakamların toplamı
$$45$$
olduğundan, tüm 20 rakamın toplamı
$$90$$
olur. O halde çift konumlardaki rakamların toplamı
$$90-W$$
olmalıdır.
\(11\)'e bölünebilme kuralı bize
$$W-(90-W)\equiv 0 \pmod{11}$$
koşulunu verir. Bu ifade
$$2W-90\equiv 0 \pmod{11}$$
ve dolayısıyla
$$W-45\equiv 0 \pmod{11}$$
ile eşdeğerdir. Sonuç olarak geçerli bir dağılım vektörü şu iki koşulu sağlamalıdır:
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Şimdi geçerli bir \((k_0,\dots,k_9)\) vektörü sabitleyelim. Baştaki sıfır yasağını bir an için yok sayarsak, tek konumlarda \(k_0,\dots,k_9\) çokluklarına sahip bir çoklu küme bulunur. Bu yerleşimlerin sayısı çokterimli katsayıyla
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}$$
olur.
Fakat 1. basamak tek konumdur ve \(0\) olamaz. Eğer \(k_0=0\) ise düzeltme gerekmez. Eğer \(k_0\ge 1\) ise, ilk basamağa bir \(0\) sabitlenir ve kalan 9 tek konum permüte edilir. Geçersiz durum sayısı
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}$$
olur. Böylece geçerli tek konum düzenlemeleri
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}}$$
şeklinde elde edilir; burada \(k_0=0\) ise \(N_{\mathrm{odd,lead0}}=0\) alınır.
Çift konumlarda tamamlayıcı çoklu küme bulunur ve çokluklar \(2-k_d\) olur. Çift konumlarda baştaki basamak kısıtı olmadığı için sayı doğrudan
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}$$
olur. Tek konumlar için geçerli bir düzenleme ile çift konumlar için bir düzenleme bağımsız olarak seçildiğinde, bunlar bir tek 20 basamaklı sayıya benzersiz biçimde iç içe geçer. Bu yüzden sabit vektörün katkısı
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}$$
olur.
Her \(k_d\) yalnızca \(0\), \(1\) veya \(2\) olabilir. Bu nedenle incelenecek en fazla
$$3^{10}=59{,}049$$
vektör vardır. Nihai toplam
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}$$
şeklindedir. Uygulamalar tam olarak bu toplamı hesaplar.
Küçük bir örnek yöntemi netleştirir. Sadece \(0,1,2\) rakamlarını ikişer kez kullandığımızı düşünelim; bu durumda sayılar 6 basamaklıdır. 3 tek ve 3 çift konum vardır, dolayısıyla
$$k_0+k_1+k_2=3$$
olmalıdır. Farklı rakamların toplamı
$$0+1+2=3$$
olduğundan, bölünebilme koşulu
$$k_1+2k_2-3\equiv 0 \pmod{11}$$
şeklindedir. Sol taraf yalnızca \(-3\) ile \(3\) arasında kalabildiği için aslında
$$k_1+2k_2=3$$
olmalıdır. \(k_d\in\{0,1,2\}\) kısıtı altında tek çözüm
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right)$$
olur. Böylece hem tek hem çift konumlarda \(0,1,2\) rakamlarının birer kopyası vardır. Sayılar:
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
Dolayısıyla bu küçük problemde geçerli sayı adedi
$$4\cdot 6=24$$
olur. Asıl problem aynı mantığın \(0\) ile \(9\) arasındaki tüm rakamlara uygulanmış halidir.
C++, Python ve Java uygulamaları önce \(0!\) ile \(20!\) arasındaki faktöriyelleri önceden hesaplar; böylece tüm çokterimli sayımlar tam sayı bölmeleriyle elde edilir. Daha sonra \(k_0,\dots,k_9\) değerleri derinlik öncelikli bir aramayla dolaşılır. Bu arama sırasında uygulama iki koşulu kademeli olarak izler: şu ana kadar kaç tek konum doldurulduğu ve tek konumlar için oluşan ağırlıklı toplam \(\sum d\,k_d\).
Arama son rakama ulaştığında önce tam olarak 10 tek konum kullanılıp kullanılmadığı kontrol edilir. Bu sağlanmıyorsa dal hemen elenir. Ardından
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}$$
koşulu test edilir. Yalnızca iki şartı da sağlayan son durumlar toplam cevaba katkı verir. Katkı hesaplanırken serbest tek konum çokterimli sayısı alınır, gerekirse başta sıfır bulunan durumlar çıkarılır, sonra tamamlayıcı çift konum çokterimli sayısı ile çarpılır.
Durum uzayı zaten küçüktür, ancak yine de arama, 10'dan fazla tek konum kullanmış kısmi atamaları erken aşamada bırakarak gereksiz dalları keser.
Gerçek problem için en fazla \(3^{10}=59{,}049\) adet \((k_0,\dots,k_9)\) vektörü vardır. Her tamamlanmış vektörde çokterimli katsayıları hesaplamak için yalnızca \(O(10)\) aritmetik işlem gerekir. Bu nedenle toplam süre \(O(3^{10}\cdot 10)\) olur ve sabit boyutlu bu problem için pratikte çok küçüktür. Bellek kullanımı, mevcut sayım vektörü ve küçük faktöriyel tablosu nedeniyle \(O(10)\) düzeyindedir.
Un número doble pandigital usa cada dígito \(0,1,\dots,9\) exactamente dos veces, así que todo candidato tiene 20 cifras. Debemos contar cuántos de esos números de 20 cifras no empiezan con \(0\) y además son divisibles por \(11\). Enumerar directamente todas las permutaciones del multiconjunto de 20 elementos es inviable; la solución cuenta en cambio cuántas copias de cada dígito van a posiciones impares y cuántas quedan forzadas en posiciones pares.
La herramienta decisiva es la regla de divisibilidad por \(11\). En un número de 20 cifras, tomamos como posiciones impares \(1,3,5,\dots,19\) y como posiciones pares \(2,4,6,\dots,20\). Un número es divisible por \(11\) exactamente cuando su suma alternada de cifras es múltiplo de \(11\).
Para cada dígito \(d\in\{0,1,\dots,9\}\), definimos \(k_d\) como el número de copias de \(d\) colocadas en posiciones impares. Como cada dígito aparece dos veces, siempre se cumple
$$k_d\in\{0,1,2\}.$$
Hay 10 posiciones impares en total, por lo que la primera restricción global es
$$\sum_{d=0}^{9} k_d = 10.$$
Una vez fijados \(k_0,\dots,k_9\), las posiciones pares quedan determinadas automáticamente: el dígito \(d\) aparece en ellas
$$2-k_d$$
veces.
Sea
$$W=\sum_{d=0}^{9} d\,k_d$$
la suma de las cifras situadas en posiciones impares. La suma de los dígitos distintos es
$$45,$$
de modo que la suma de las 20 cifras usadas es
$$90.$$
Por tanto, la suma de las cifras en posiciones pares es
$$90-W.$$
La regla de divisibilidad por \(11\) exige
$$W-(90-W)\equiv 0 \pmod{11}.$$
Al simplificar se obtiene
$$2W-90\equiv 0 \pmod{11},$$
lo cual es equivalente a
$$W-45\equiv 0 \pmod{11}.$$
Así, un vector \((k_0,\dots,k_9)\) es admisible exactamente cuando
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Fijemos ahora un vector admisible \((k_0,\dots,k_9)\). Si ignoramos momentáneamente la restricción del cero inicial, las posiciones impares contienen un multiconjunto con multiplicidades \(k_0,\dots,k_9\), y su número de disposiciones es
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}.$$
Sin embargo, la primera cifra está en una posición impar y no puede ser \(0\). Si \(k_0=0\), no hay nada que restar. Si \(k_0\ge 1\), fijamos un cero al principio y permutamos las 9 posiciones impares restantes, obteniendo
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$$
Por tanto, el número válido en posiciones impares es
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$$
donde \(N_{\mathrm{odd,lead0}}=0\) cuando \(k_0=0\).
Las posiciones pares contienen el multiconjunto complementario, con multiplicidades \(2-k_d\). Como ahí no existe restricción de cifra inicial, el conteo es directamente
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$$
Una disposición válida de las posiciones impares y una disposición de las posiciones pares se entrelazan de forma única para formar un solo número de 20 cifras. Así, la contribución del vector fijo es
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$$
Cada \(k_d\) solo puede ser \(0\), \(1\) o \(2\), por lo que como máximo hay
$$3^{10}=59{,}049$$
vectores que revisar. La respuesta final es
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$$
Esa es exactamente la expresión que evalúan las implementaciones.
Una versión pequeña deja ver toda la mecánica. Supongamos que solo usamos los dígitos \(0,1,2\), cada uno dos veces, de modo que el número tiene 6 cifras. Entonces hay 3 posiciones impares y 3 pares, así que
$$k_0+k_1+k_2=3.$$
La suma de los dígitos distintos es
$$0+1+2=3,$$
y la condición de divisibilidad queda
$$k_1+2k_2-3\equiv 0 \pmod{11}.$$
Como el lado izquierdo solo puede estar entre \(-3\) y \(3\), en realidad debe valer \(0\), luego
$$k_1+2k_2=3.$$
Bajo la restricción \(k_d\in\{0,1,2\}\), la única solución es
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$$
Así, tanto las posiciones impares como las pares contienen una copia de \(0\), \(1\) y \(2\). Los conteos son
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
Por lo tanto, este problema reducido tiene exactamente
$$4\cdot 6=24$$
números válidos. El problema real usa el mismo argumento con los dígitos \(0\) a \(9\).
Las implementaciones en C++, Python y Java precalculan los factoriales desde \(0!\) hasta \(20!\) para formar cada conteo multinomial mediante divisiones enteras exactas. Después enumeran los diez valores \(k_0,\dots,k_9\) con una búsqueda en profundidad. Durante esa búsqueda, la implementación mantiene dos cantidades acumuladas: cuántas posiciones impares ya fueron ocupadas y la suma ponderada \(\sum d\,k_d\) de las cifras puestas en posiciones impares.
Cuando la búsqueda llega al último dígito, primero comprueba si se usaron exactamente 10 posiciones impares. Si no, esa rama se descarta. Luego verifica la congruencia
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Solo los estados terminales que cumplen ambas condiciones aportan al total. Para cada uno, la implementación calcula el multinomial impar sin restricción, resta los casos con cero inicial cuando hace falta, calcula el multinomial par a partir de las cuentas complementarias \(2-k_d\), y acumula el producto.
El espacio de estados ya es pequeño, pero aun así la recursión poda muchas ramas pronto porque cualquier asignación parcial que ya use más de 10 posiciones impares no puede completarse de manera válida.
Para el problema real hay como mucho \(3^{10}=59{,}049\) vectores \((k_0,\dots,k_9)\). Evaluar un vector completo requiere solo \(O(10)\) operaciones aritméticas para los factores multinomiales, de modo que el tiempo total es \(O(3^{10}\cdot 10)\), prácticamente constante para este tamaño fijo. El uso de memoria es \(O(10)\) por el vector actual de cuentas y la pequeña tabla de factoriales.
所谓“双重全数字”数，是指数字 \(0,1,\dots,9\) 每个都恰好出现两次，因此任何候选数都必然是 20 位。题目要求统计其中首位不为 \(0\) 且能被 \(11\) 整除的个数。若直接对 20 个元素的多重集合做全排列，规模过大而不可行，所以解法改为按“每个数字有多少份落在奇数位上”来分类计数。
核心在于把 \(11\) 的整除判定转化成一个小型组合枚举问题。对一个 20 位数，从左到右将位置 \(1,3,5,\dots,19\) 视为奇数位，将位置 \(2,4,6,\dots,20\) 视为偶数位。一个十进制整数能被 \(11\) 整除，当且仅当奇偶位数字和的差是 \(11\) 的倍数。
对每个数字 \(d\in\{0,1,\dots,9\}\)，定义 \(k_d\) 为数字 \(d\) 放入奇数位的份数。因为每个数字总共只出现两次，所以恒有
$$k_d\in\{0,1,2\}.$$
20 位数中共有 10 个奇数位，因此第一条总约束是
$$\sum_{d=0}^{9} k_d = 10.$$
一旦 \(k_0,\dots,k_9\) 确定，偶数位上的数量也随之确定，因为数字 \(d\) 在偶数位上出现的次数必然是
$$2-k_d.$$
也就是说，我们只需要决定每个数字的两份中有几份去奇数位，剩下的自动去偶数位。
设奇数位上的数字总和为
$$W=\sum_{d=0}^{9} d\,k_d.$$
单个集合 \(0+1+\cdots+9\) 的和是
$$45,$$
所以全部 20 个数字的总和是
$$90.$$
因此偶数位上的数字和必然为
$$90-W.$$
按 \(11\) 的整除规则，需要满足
$$W-(90-W)\equiv 0 \pmod{11}.$$
整理后得到
$$2W-90\equiv 0 \pmod{11},$$
进一步等价于
$$W-45\equiv 0 \pmod{11}.$$
因此一个分配向量 \((k_0,\dots,k_9)\) 合法，当且仅当它同时满足
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
这一步非常关键，因为它把整除判定完全压缩成了对 10 个小整数的约束。
固定一个满足条件的向量 \((k_0,\dots,k_9)\)。若暂时忽略首位不能为 \(0\) 的限制，那么奇数位上构成了一个重数分别为 \(k_0,\dots,k_9\) 的多重集合，所以奇数位的排列数是
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}.$$
但第 1 位本身就是奇数位，所以还必须去掉首位为 \(0\) 的非法排列。
如果 \(k_0=0\)，说明奇数位上根本没有 \(0\)，自然无需修正。
如果 \(k_0\ge 1\)，那么首位放一个 \(0\) 以后，还剩下 9 个奇数位需要排列，其中数字 \(0\) 还剩 \(k_0-1\) 份，其余数字分别有 \(k_1,\dots,k_9\) 份，于是非法排列数为
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$$
因此，真正有效的奇数位排列数是
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$$
并约定当 \(k_0=0\) 时 \(N_{\mathrm{odd,lead0}}=0\)。
偶数位上的数字重数是互补的 \(2-k_d\)。偶数位不存在前导零问题，因为整个数的首位只来自第 1 位，也就是奇数位。因此偶数位排列数直接是
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$$
一旦选定一个奇数位的有效排列，再选定一个偶数位的排列，它们按位置交错后就唯一对应一个 20 位整数。因此固定向量的贡献为
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$$
这一步把“构造 20 位数”的问题彻底拆成了两个独立的多重集合排列问题。
因为每个 \(k_d\) 只有 3 种可能值 \(0,1,2\)，所以待检查的向量总数最多只有
$$3^{10}=59{,}049.$$
这已经非常小，可以直接枚举。最终答案就是
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$$
这就是程序实际计算的组合公式。
为了看清整个计数过程，可以先看一个缩小版问题。假设只使用数字 \(0,1,2\)，每个数字仍然出现两次，那么总长度是 6 位，其中有 3 个奇数位和 3 个偶数位，因此
$$k_0+k_1+k_2=3.$$
不同数字之和为
$$0+1+2=3,$$
所以整除条件化为
$$k_1+2k_2-3\equiv 0 \pmod{11}.$$
由于左边的取值范围只能在 \(-3\) 到 \(3\) 之间，所以它只能等于 \(0\)，也就是
$$k_1+2k_2=3.$$
再结合 \(k_d\in\{0,1,2\}\)，唯一解是
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$$
这说明奇数位上恰好各放一个 \(0,1,2\)，偶数位上也恰好各放一个。于是
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
因此这个缩小版问题的答案为
$$4\cdot 6=24.$$
原题只是把这个思路从 3 个数字扩展到 10 个数字而已。
C++、Python 和 Java 实现都会先预计算 \(0!\) 到 \(20!\)，这样后续所有多项式系数都能通过精确整数除法直接得到。然后程序用深度优先搜索枚举 \(k_0,\dots,k_9\) 的取值。搜索过程中持续维护两个量：当前已经放入奇数位的总份数，以及奇数位数字和的加权值 \(\sum d\,k_d\)。
当搜索走到最后一个数字时，程序先检查是否恰好用了 10 个奇数位；如果不是，这个分支立即丢弃。然后再检查是否满足
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
只有同时通过这两关的终止状态才会产生贡献。对每个合法状态，程序计算奇数位的多重集合排列数，必要时减去首位为 \(0\) 的部分，再计算偶数位的排列数，最后把两者乘积加入答案。
虽然总状态数本来就不大，但搜索仍然会提前剪枝，因为任何部分分配一旦已经使用超过 10 个奇数位，就不可能补成合法方案。
对于原题，最多只需检查 \(3^{10}=59{,}049\) 个向量 \((k_0,\dots,k_9)\)。每个完整向量只需要 \(O(10)\) 次算术操作来形成阶乘比值，因此总时间复杂度为 \(O(3^{10}\cdot 10)\)，在这个固定规模下几乎可以视为常数。空间复杂度为 \(O(10)\)，主要来自当前计数向量和很小的阶乘表。
Дважды пандиджитальное число использует каждую цифру \(0,1,\dots,9\) ровно два раза, поэтому любой кандидат имеет 20 цифр. Нужно посчитать, сколько таких 20-значных чисел не начинаются с \(0\) и делятся на \(11\). Полный перебор перестановок мультимножества из 20 элементов слишком дорог, поэтому решение считает иначе: для каждой цифры выбирается, сколько из двух её копий попадает на нечётные позиции.
Решающую роль играет признак делимости на \(11\). В 20-значном числе позиции \(1,3,5,\dots,19\) считаем нечётными, а \(2,4,6,\dots,20\) — чётными. Число делится на \(11\) тогда и только тогда, когда разность сумм цифр на нечётных и чётных позициях кратна \(11\).
Для каждой цифры \(d\in\{0,1,\dots,9\}\) обозначим через \(k_d\) число копий цифры \(d\), стоящих на нечётных позициях. Поскольку каждая цифра встречается ровно дважды, всегда верно
$$k_d\in\{0,1,2\}.$$
Всего нечётных позиций 10, поэтому первое глобальное условие имеет вид
$$\sum_{d=0}^{9} k_d = 10.$$
Как только выбраны \(k_0,\dots,k_9\), чётные позиции определяются автоматически: цифра \(d\) встречается там
$$2-k_d$$
раз.
Обозначим через
$$W=\sum_{d=0}^{9} d\,k_d$$
сумму цифр, стоящих на нечётных позициях. Сумма различных цифр \(0+1+\cdots+9\) равна
$$45,$$
поэтому сумма всех 20 использованных цифр равна
$$90.$$
Значит, сумма цифр на чётных позициях равна
$$90-W.$$
Признак делимости на \(11\) требует
$$W-(90-W)\equiv 0 \pmod{11}.$$
После упрощения получаем
$$2W-90\equiv 0 \pmod{11},$$
а это эквивалентно условию
$$W-45\equiv 0 \pmod{11}.$$
Итак, вектор \((k_0,\dots,k_9)\) допустим тогда и только тогда, когда выполняются обе связи:
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Зафиксируем допустимый вектор \((k_0,\dots,k_9)\). Если временно забыть про запрет ведущего нуля, то на нечётных позициях стоит мультимножество с кратностями \(k_0,\dots,k_9\). Число его перестановок равно
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}.$$
Но первая цифра числа тоже находится на нечётной позиции и не может быть нулём. Если \(k_0=0\), исправление не нужно. Если \(k_0\ge 1\), фиксируем один ноль в первой позиции и переставляем оставшиеся 9 нечётных мест. Получаем число запрещённых конфигураций
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$$
Следовательно, число корректных размещений на нечётных позициях равно
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$$
где при \(k_0=0\) полагается \(N_{\mathrm{odd,lead0}}=0\).
На чётных позициях стоит дополняющее мультимножество с кратностями \(2-k_d\). Здесь ограничения на ведущий разряд нет, поэтому число размещений просто равно
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$$
Выбор корректного размещения на нечётных позициях и произвольного размещения на чётных позициях однозначно задаёт одно 20-значное число. Значит, вклад фиксированного вектора равен
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$$
Каждый \(k_d\) принимает только значения \(0\), \(1\) или \(2\), поэтому всего нужно проверить не более
$$3^{10}=59{,}049$$
векторов. Итоговая формула имеет вид
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$$
Именно эту сумму вычисляют реализации.
На маленьком примере весь механизм особенно прозрачен. Пусть используются только цифры \(0,1,2\), каждая ровно дважды. Тогда число имеет 6 цифр, из них 3 стоят на нечётных позициях и 3 на чётных, поэтому
$$k_0+k_1+k_2=3.$$
Сумма различных цифр равна
$$0+1+2=3,$$
и условие делимости принимает вид
$$k_1+2k_2-3\equiv 0 \pmod{11}.$$
Левая часть может лежать только в диапазоне от \(-3\) до \(3\), значит она обязана быть нулём, то есть
$$k_1+2k_2=3.$$
С учётом ограничения \(k_d\in\{0,1,2\}\) единственное решение —
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$$
Следовательно, и на нечётных, и на чётных позициях стоит по одной копии каждой цифры. Тогда
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
Значит, в этой уменьшенной задаче число допустимых чисел равно
$$4\cdot 6=24.$$
В исходной задаче используется тот же самый аргумент, только для цифр \(0\)–\(9\).
Реализации на C++, Python и Java заранее вычисляют факториалы от \(0!\) до \(20!\), чтобы затем получать все мультиномиальные коэффициенты точными целочисленными делениями. После этого программа глубинным перебором перечисляет значения \(k_0,\dots,k_9\). Во время перебора поддерживаются две накопленные величины: сколько нечётных позиций уже занято и какова текущая взвешенная сумма \(\sum d\,k_d\) для нечётных позиций.
Когда перебор доходит до последней цифры, сначала проверяется, использовано ли ровно 10 нечётных позиций. Если нет, ветвь сразу отбрасывается. Затем проверяется сравнение
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
Только конечные состояния, удовлетворяющие обоим условиям, дают вклад в ответ. Для каждого такого состояния вычисляется мультиномиальный коэффициент для нечётных позиций, при необходимости вычитаются случаи с ведущим нулём, затем вычисляется коэффициент для чётных позиций по дополнительным кратностям \(2-k_d\), и произведение добавляется к общей сумме.
Пространство состояний и так мало, но рекурсия дополнительно отсекает многие ветви заранее: если в частичном распределении уже занято больше 10 нечётных мест, завершить его корректно невозможно.
Для исходной задачи существует не более \(3^{10}=59{,}049\) векторов \((k_0,\dots,k_9)\). Для каждого полного вектора требуется всего \(O(10)\) арифметических действий, чтобы вычислить факториальные отношения. Следовательно, общая временная сложность равна \(O(3^{10}\cdot 10)\), что для фиксированного размера входа практически является константой. Память имеет порядок \(O(10)\): хранится текущий вектор счётчиков и небольшая таблица факториалов.
العدد المزدوج البانديجيتال يستعمل كل رقم من \(0,1,\dots,9\) مرتين بالضبط، ولذلك يكون كل مرشح مكوّنًا من 20 خانة. المطلوب هو عدّ هذه الأعداد ذات العشرين خانة التي لا تبدأ بـ \(0\) وتقبل القسمة على \(11\). التعداد المباشر لكل تبديلات متعدد المجموعة ذي 20 عنصرًا غير عملي، لذلك تعيد الفكرة تنظيم المسألة بحسب عدد نسخ كل رقم الموضوعة في الخانات الفردية.
المفتاح هو قاعدة القسمة على \(11\). في عدد من 20 خانة نعدّ المواضع \(1,3,5,\dots,19\) خانات فردية، والمواضع \(2,4,6,\dots,20\) خانات زوجية. يكون العدد قابلاً للقسمة على \(11\) إذا وفقط إذا كان الفرق بين مجموع أرقام الخانات الفردية ومجموع أرقام الخانات الزوجية مضاعفًا لـ \(11\).
لكل رقم \(d\in\{0,1,\dots,9\}\)، نرمز بـ \(k_d\) إلى عدد نسخ الرقم \(d\) التي توضع في الخانات الفردية. وبما أن كل رقم يظهر مرتين، فلدينا دائمًا
$$k_d\in\{0,1,2\}.$$
وهناك 10 خانات فردية في المجموع، لذا يكون الشرط الكلي الأول
$$\sum_{d=0}^{9} k_d = 10.$$
وبمجرد تثبيت \(k_0,\dots,k_9\)، تصبح أعداد الخانات الزوجية محسومة تلقائيًا، لأن الرقم \(d\) يظهر في الخانات الزوجية عدد
$$2-k_d$$
من المرات.
لنعرّف
$$W=\sum_{d=0}^{9} d\,k_d$$
ليكون مجموع الأرقام الموضوعة في الخانات الفردية. مجموع الأرقام المميزة \(0+1+\cdots+9\) يساوي
$$45,$$
وبالتالي فإن مجموع الأرقام العشرين كلها يساوي
$$90.$$
ومن ثم يكون مجموع أرقام الخانات الزوجية مساويًا لـ
$$90-W.$$
شرط القسمة على \(11\) يعطينا
$$W-(90-W)\equiv 0 \pmod{11}.$$
وبالتبسيط نحصل على
$$2W-90\equiv 0 \pmod{11},$$
وهو مكافئ لـ
$$W-45\equiv 0 \pmod{11}.$$
إذن يكون المتجه \((k_0,\dots,k_9)\) صالحًا إذا وفقط إذا حقق الشرطين
$$\sum_{d=0}^{9} k_d = 10,\qquad \sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
لنثبت الآن متجهًا صالحًا \((k_0,\dots,k_9)\). إذا تجاهلنا مؤقتًا منع الصفر في البداية، فإن الخانات الفردية تحتوي على متعدد مجموعة بتكرارات \(k_0,\dots,k_9\)، ولذلك يكون عدد ترتيباتها
$$N_{\mathrm{odd,all}}=\frac{10!}{\prod_{d=0}^{9} k_d!}.$$
لكن الخانة الأولى نفسها فردية، فلا يجوز أن تحمل الرقم \(0\). إذا كان \(k_0=0\) فلا توجد حاجة لأي تصحيح. وإذا كان \(k_0\ge 1\)، فنثبت صفرًا واحدًا في الخانة الأولى ثم نرتب الخانات الفردية التسع المتبقية، فنحصل على عدد الحالات غير الصالحة
$$N_{\mathrm{odd,lead0}}=\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}.$$
ومن ثم يصبح عدد ترتيبات الخانات الفردية الصالحة
$$N_{\mathrm{odd,valid}}=N_{\mathrm{odd,all}}-N_{\mathrm{odd,lead0}},$$
مع اعتبار \(N_{\mathrm{odd,lead0}}=0\) عندما يكون \(k_0=0\).
الخانات الزوجية تحتوي على متعدد المجموعة المتمم ذي التكرارات \(2-k_d\). ولا توجد فيها مشكلة رقم أول، لأن بداية العدد تحددها الخانة الأولى فقط. لذلك يكون عدد الترتيبات مباشرة
$$N_{\mathrm{even}}=\frac{10!}{\prod_{d=0}^{9} (2-k_d)!}.$$
وعندما نختار ترتيبًا صالحًا للخانات الفردية وترتيبًا للخانات الزوجية، فإن دمجهما بالتناوب يعطي عددًا واحدًا من 20 خانة بشكل وحيد. لذا تكون مساهمة المتجه الثابت هي
$$N(k)=N_{\mathrm{odd,valid}}\cdot N_{\mathrm{even}}.$$
كل \(k_d\) لا يأخذ إلا القيم \(0\) أو \(1\) أو \(2\)، ولهذا يوجد في الحد الأقصى
$$3^{10}=59{,}049$$
متجهًا فقط يجب فحصه. وعليه فإن الجواب النهائي هو
$$\boxed{\sum_{\substack{k_d\in\{0,1,2\}\\ \sum k_d=10\\ \sum d\,k_d\equiv 45\!\!\!\pmod{11}}} \left(\frac{10!}{\prod_{d=0}^{9} k_d!}-\mathbf{1}_{k_0\ge 1}\frac{9!}{(k_0-1)!\prod_{d=1}^{9} k_d!}\right) \frac{10!}{\prod_{d=0}^{9} (2-k_d)!}}.$$
وهذه هي الصيغة التي تحسبها التطبيقات فعليًا.
لفهم الفكرة عمليًا، لنأخذ نسخة مصغرة من المسألة نستعمل فيها الأرقام \(0,1,2\) فقط، مع ظهور كل رقم مرتين. عندئذ يصبح العدد مكوّنًا من 6 خانات، منها 3 فردية و3 زوجية، وبالتالي
$$k_0+k_1+k_2=3.$$
ومجموع الأرقام المميزة هو
$$0+1+2=3,$$
لذلك يتحول شرط القسمة إلى
$$k_1+2k_2-3\equiv 0 \pmod{11}.$$
وبما أن الطرف الأيسر لا يمكن أن يخرج عن المجال من \(-3\) إلى \(3\)، فلا بد أن يساوي \(0\)، أي
$$k_1+2k_2=3.$$
ومع الشرط \(k_d\in\{0,1,2\}\)، يكون الحل الوحيد هو
$$\left(k_0,k_1,k_2\right)=\left(1,1,1\right).$$
إذن تحتوي الخانات الفردية على نسخة واحدة من كل من \(0,1,2\)، وكذلك الخانات الزوجية. عندها نحصل على
$$N_{\mathrm{odd,all}}=\frac{3!}{1!\,1!\,1!}=6,$$
$$N_{\mathrm{odd,lead0}}=\frac{2!}{0!\,1!\,1!}=2,$$
$$N_{\mathrm{odd,valid}}=6-2=4,$$
$$N_{\mathrm{even}}=\frac{3!}{1!\,1!\,1!}=6.$$
وبالتالي يكون عدد الأعداد الصالحة في هذه النسخة المصغرة
$$4\cdot 6=24.$$
المسألة الأصلية تطبق الحجة نفسها تمامًا ولكن على الأرقام من \(0\) إلى \(9\).
تقوم تطبيقات C++ وPython وJava أولًا بحساب القيم \(0!\) حتى \(20!\) مسبقًا حتى يمكن تكوين كل معاملات التعددية بقسمة صحيحة دقيقة. بعد ذلك تُعدَّد القيم \(k_0,\dots,k_9\) بواسطة بحث عمقي. وخلال هذا البحث تحتفظ الشيفرة بكمّيتين جاريتين: عدد الخانات الفردية التي استُخدمت حتى الآن، والمجموع الموزون \(\sum d\,k_d\) لأرقام الخانات الفردية.
عندما يصل البحث إلى الرقم الأخير، يتحقق أولًا من أن عدد الخانات الفردية المستعملة يساوي 10 بالضبط. وإذا لم يتحقق ذلك تُهمَل هذه الشعبة فورًا. ثم يُفحَص الشرط
$$\sum_{d=0}^{9} d\,k_d \equiv 45 \pmod{11}.$$
فقط الحالات النهائية التي تحقق الشرطين معًا تضيف مساهمة إلى الجواب. ولكل حالة من هذا النوع، تحسب الشيفرة عدد ترتيبات الخانات الفردية دون قيد، ثم تطرح عند الحاجة الحالات التي تبدأ بصفر، ثم تحسب عدد ترتيبات الخانات الزوجية من التكرارات المتممة \(2-k_d\)، وأخيرًا تضيف حاصل الضرب إلى المجموع الكلي.
حيز الحالات صغير أصلًا، لكن البحث يقطع أيضًا كثيرًا من الفروع مبكرًا، لأن أي تعيين جزئي استعمل أكثر من 10 خانات فردية لا يمكن إكماله إلى توزيع صالح.
في المسألة الفعلية يوجد على الأكثر \(3^{10}=59{,}049\) متجهًا من الشكل \((k_0,\dots,k_9)\). وكل متجه كامل يحتاج فقط إلى \(O(10)\) عملية حسابية لتقييم عوامل التعددية. لذلك يكون الزمن الكلي \(O(3^{10}\cdot 10)\)، وهو فعليًا ثابت لهذه المعطيات المحددة. أما الذاكرة فهي \(O(10)\) بسبب متجه العدّ الحالي وجدول المضروبات الصغير.