For integers \(n\), \(k\), and \(b\), define \(S(n,k,b)\) as the number of \(k\)-tuples \((x_1,\dots,x_k)\) satisfying
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n.$$
The overall task is to evaluate
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
The bounds \(b^m\) grow quickly, while \(n\) can be as large as \(10^{15}\), so a direct dynamic program on the sum would be far too large. The successful approach is to turn the inequality into an equality, apply inclusion-exclusion to the upper bounds, and exploit the fact that \(k\le 15\) is tiny.
The key point is that the number of variables is small even though the target sum is huge. That makes subset enumeration feasible, while any method indexed directly by \(n\) would be wasteful.
Introduce a slack variable \(s\ge 0\) and rewrite the condition as
$$x_1+\cdots+x_k+s=n.$$
Now we are counting nonnegative integer solutions in \(k+1\) variables, with upper bounds only on \(x_1,\dots,x_k\).
If those upper bounds were absent, stars and bars would give
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}.$$
So the whole problem reduces to correcting this unrestricted count for the coordinates that exceed their allowed caps.
For each index \(m\), let \(E_m\) be the event that the upper bound is violated:
$$E_m=\{x_m\ge b^m+1\}.$$
Fix a subset \(A\subseteq\{1,\dots,k\}\). If every event in \(A\) occurs, then for each \(m\in A\) we can offset
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0.$$
After this change of variables, the equation becomes
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1).$$
Therefore the number of solutions contributing to the intersection of all events in \(A\) is
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k},$$
with the usual convention that the term is \(0\) when the upper argument is negative or smaller than \(k\).
Inclusion-exclusion now yields the exact formula
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
This formula is already efficient enough conceptually because there are only \(2^k\) subsets.
Let \(p=10^9+7\). The program always uses \(k\le 15\), so in particular \(k<p\).
Write any upper argument as
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p.$$
Since \(k\) has only one nonzero base-\(p\) digit, Lucas' theorem gives
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}.$$
So only the residue \(N\bmod p\) matters. If \(N_0<k\), then \(\binom{N}{k}\equiv 0\pmod p\). Otherwise we can compute
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod p.$$
Because \(k\) is tiny, the numerator needs only \(k\) modular multiplications, and \(1/k!\) can be precomputed once using Fermat's little theorem.
For each index \(m\), define its violation cost
$$c_m=b^m+1.$$
For a subset \(A\), the inclusion-exclusion formula depends only on the total offset
$$\sigma(A)=\sum_{m\in A} c_m.$$
Rather than recomputing that sum from scratch for every subset, one can build all \(2^k\) values incrementally. If \(A\neq \varnothing\) and we remove one chosen element \(r\in A\), then
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r.$$
This turns the subset enumeration into a simple table build followed by a signed accumulation. The mathematics stays the same; the precomputation only saves repeated work.
Here the bounds are
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14.$$
After adding slack \(s\), the unrestricted count is
$$\binom{14+3}{3}=\binom{17}{3}=680.$$
The single-violation offsets are \(3\), \(5\), and \(9\), so the three single-event terms are
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56.$$
The double intersections use offsets \(8\), \(12\), and \(14\), giving
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1.$$
The triple intersection uses offset \(17\), which leaves a negative remainder, so that term is \(0\).
Hence
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
This is one of the checkpoint values matched by the implementation.
Once \(S(n,k,b)\) can be evaluated quickly, the complete answer is just
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
There are only six queries, and each of them uses \(k\le 15\), so the subset-based method remains easily fast enough.
The C++, Python, and Java implementations follow the same structure. First they precompute factorials and inverse factorials up to \(15\), which is enough for every binomial denominator that appears. Then, for each required value of \(k\), they build the list \(b^1+1,b^2+1,\dots,b^k+1\).
Next, they generate the total offset for every subset of \(\{1,\dots,k\}\) by reusing the previously computed total of a smaller subset. For each subset they check whether that offset already exceeds \(n\); if so, the corresponding inclusion-exclusion term contributes nothing. Otherwise they form the upper argument \(N=(n-\sigma(A))+k\), reduce \(N\) modulo \(10^9+7\), evaluate the binomial coefficient with a short falling product, and add or subtract the result according to the parity of \(|A|\).
After one query \(S(n,k,b)\) is finished, the program moves on to the next \(k\) and finally sums the six query results modulo \(10^9+7\).
For one triple \((n,k,b)\), generating the violation costs takes \(O(k)\) time. Building all subset offsets takes \(O(2^k)\) time and \(O(2^k)\) memory. Evaluating the inclusion-exclusion sum needs \(2^k\) binomial terms, and each term costs \(O(k)\) modular operations because \(k\) is computed by a short falling product.
Therefore one query costs \(O(2^k\cdot k)\) time and \(O(2^k)\) memory. Since the full problem uses only \(k=10,\dots,15\), the total work is just a small constant multiple of that bound.
Für ganze Zahlen \(n\), \(k\) und \(b\) bezeichnet \(S(n,k,b)\) die Anzahl der \(k\)-Tupel \((x_1,\dots,x_k)\) mit
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n.$$
Gesucht ist insgesamt
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
Die Schranken \(b^m\) wachsen schnell, und \(n\) kann bis \(10^{15}\) reichen. Deshalb wäre eine Dynamik über alle Summenwerte viel zu groß. Die Lösung nutzt stattdessen eine Schlupfvariable, Inklusion-Exklusion und die Tatsache, dass \(k\le 15\) sehr klein ist.
Entscheidend ist, dass nicht die Summe klein ist, sondern die Zahl der beschränkten Variablen. Genau deshalb lohnt sich die Aufspaltung nach Teilmengen der verletzten Schranken.
Wir führen eine Schlupfvariable \(s\ge 0\) ein und schreiben
$$x_1+\cdots+x_k+s=n.$$
Damit zählen wir nichtnegative ganzzahlige Lösungen in \(k+1\) Variablen; obere Schranken gibt es nur für \(x_1,\dots,x_k\).
Ohne diese Schranken liefert Stars-and-Bars sofort
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}.$$
Das eigentliche Problem besteht also nur darin, jene Lösungen zu korrigieren, bei denen eine oder mehrere Komponenten über ihre jeweilige Grenze hinausgehen.
Für jeden Index \(m\) definieren wir das Verletzungsereignis
$$E_m=\{x_m\ge b^m+1\}.$$
Sei nun \(A\subseteq\{1,\dots,k\}\). Wenn alle Ereignisse aus \(A\) eintreten, setzen wir für jedes \(m\in A\)
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0.$$
Dann wird die Gleichung zu
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1).$$
Die Anzahl solcher Lösungen ist daher
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k},$$
wobei negative oder zu kleine obere Argumente als \(0\) interpretiert werden.
Mit Inklusion-Exklusion erhält man somit
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
Da \(k\le 15\), ist das Durchlaufen aller \(2^k\) Teilmengen vollkommen praktikabel.
Sei \(p=10^9+7\). In allen Fällen gilt \(k\le 15<p\).
Schreibe das obere Argument in Basis \(p\) als
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p.$$
Da \(k\) in Basis \(p\) nur eine nichtverschwindende Ziffer besitzt, folgt aus dem Satz von Lucas
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}.$$
Es genügt also, den Rest \(N\bmod p\) zu betrachten. Ist \(N_0<k\), dann verschwindet der Term modulo \(p\). Andernfalls gilt
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod{p}.$$
Weil \(k\) so klein ist, reichen \(k\) modulare Multiplikationen. Das Inverse von \(k!\) wird einmal vorab mit dem kleinen Fermat berechnet.
Für jeden Index \(m\) definieren wir die Kosten einer Verletzung durch
$$c_m=b^m+1.$$
Für eine Teilmenge \(A\) hängt die Formel nur von
$$\sigma(A)=\sum_{m\in A} c_m$$
ab. Anstatt diese Summe für jede Teilmenge neu zu bilden, kann man alle Werte inkrementell erzeugen. Entfernt man aus einer nichtleeren Teilmenge \(A\) ein fest gewähltes Element \(r\in A\), so gilt
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r.$$
So entsteht zuerst eine Tabelle aller Verschiebungen und danach nur noch die eigentliche Vorzeichen-Summation.
Hier lauten die Schranken
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14.$$
Mit der Schlupfvariable ist die unbeschränkte Anzahl
$$\binom{14+3}{3}=\binom{17}{3}=680.$$
Die drei Einzelverletzungen haben die Verschiebungen \(3\), \(5\) und \(9\), also die Beiträge
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56.$$
Für die Paar-Schnittmengen ergeben sich die Verschiebungen \(8\), \(12\) und \(14\), also
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1.$$
Die Dreifachschnittmenge benutzt die Verschiebung \(17\), lässt also keinen Rest mehr und trägt \(0\) bei.
Damit folgt
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
Dieser Wert stimmt mit einem Kontrollpunkt der Implementierung überein.
Ist \(S(n,k,b)\) einmal effizient verfügbar, dann lautet die gesuchte Gesamtgröße einfach
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
Es sind nur sechs Auswertungen nötig, und jede davon arbeitet mit \(k\le 15\).
Die C++-, Python- und Java-Implementierungen benutzen denselben Ablauf. Zuerst werden Fakultäten und inverse Fakultäten bis \(15\) vorab berechnet. Danach wird für jedes benötigte \(k\) die Liste \(b^1+1,b^2+1,\dots,b^k+1\) aufgebaut.
Anschließend wird für jede Teilmenge von \(\{1,\dots,k\}\) die Gesamtverschiebung aus einer bereits bekannten kleineren Teilmenge rekonstruiert. Wenn die Verschiebung größer als \(n\) ist, entfällt der entsprechende Inklusion-Exklusion-Term sofort. Andernfalls bildet das Programm \(N=(n-\sigma(A))+k\), reduziert \(N\) modulo \(10^9+7\), berechnet den Binomialkoeffizienten über ein kurzes fallendes Produkt und addiert oder subtrahiert ihn je nach Parität von \(|A|\).
Nach Abschluss einer Anfrage \(S(n,k,b)\) wird der nächste Wert von \(k\) bearbeitet; am Ende werden alle sechs Resultate modulo \(10^9+7\) aufsummiert.
Für ein Tripel \((n,k,b)\) kostet das Erzeugen der Verletzungskosten \(O(k)\) Zeit. Die Tabelle aller Teilmengenverschiebungen benötigt \(O(2^k)\) Zeit und \(O(2^k)\) Speicher. In der eigentlichen Inklusion-Exklusion gibt es \(2^k\) Summanden, und jeder Binomialterm braucht wegen des kurzen fallenden Produkts \(O(k)\) modulare Operationen.
Somit beträgt der Aufwand pro Anfrage \(O(2^k\cdot k)\) Zeit und \(O(2^k)\) Speicher. Für die Gesamtaufgabe kommt nur der konstante Faktor von sechs Auswertungen für \(k=10,\dots,15\) hinzu.
\(n\), \(k\) ve \(b\) tam sayıları için \(S(n,k,b)\),
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n$$
koşullarını sağlayan \(k\)-li tamsayı dizilerinin sayısıdır. Asıl hedef
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}$$
değerini bulmaktır. \(n\) çok büyük olduğu için toplam üzerinden klasik DP kurmak verimli değildir. Çözüm, eşitsizliği eşitliğe çevirip üst sınırları dahil etme-hariç tutma ile ele alır ve \(k\le 15\) olmasını temel avantaj olarak kullanır.
Buradaki kritik gözlem, toplamın büyük ama değişken sayısının küçük olmasıdır. Bu nedenle altkümeleri dolaşmak mümkündür; toplam değerlerine göre tablo doldurmak ise gereksiz derecede pahalıdır.
\(s\ge 0\) olacak bir gevşeklik değişkeni ekleyelim:
$$x_1+\cdots+x_k+s=n.$$
Böylece \(k+1\) tane negatif olmayan değişkenin çözümlerini sayıyoruz; üst sınırlar sadece \(x_1,\dots,x_k\) üzerinde kalıyor.
Eğer bu üst sınırlar hiç olmasaydı, yıldız-çubuk yöntemi doğrudan
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}$$
sonucunu verirdi. Dolayısıyla yapılacak iş, sınırı aşan çözümleri sistemli biçimde düzeltmektir.
Her \(m\) için sınır ihlali olayını
$$E_m=\{x_m\ge b^m+1\}$$
şeklinde tanımlayalım. \(A\subseteq\{1,\dots,k\}\) sabit bir altküme olsun. Eğer \(A\)'daki tüm ihlaller gerçekleşiyorsa, her \(m\in A\) için
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0$$
yazarız. O zaman denklem
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1)$$
haline gelir. Bu kesişimin çözüm sayısı
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k}$$
olur; üst satır negatifse ya da \(k\)'den küçükse terim \(0\) kabul edilir.
Böylece tam formül
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
\(k\le 15\) olduğundan, \(2^k\) altkümenin tamamını dolaşmak rahattır.
\(p=10^9+7\) asalını alalım. Tüm sorgularda \(k\le 15<p\) geçerlidir.
Üst argümanı taban \(p\)'de
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p$$
şeklinde yazalım. \(k\)'nin taban \(p\) gösteriminde yalnızca tek bir sıfır olmayan basamak bulunduğu için Lucas teoremi
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}$$
sonucunu verir. Yani yalnızca \(N\bmod p\) önemlidir. Eğer \(N_0<k\) ise katkı sıfırdır; aksi halde
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod{p}$$
kullanılır. \(k\) küçük olduğu için bu hesap sadece kısa bir çarpım zinciri gerektirir ve \(1/k!\) değeri önceden hazırlanabilir.
Her indeks için ihlal maliyetini
$$c_m=b^m+1$$
olarak tanımlayalım. Formülde her altküme için gereken büyüklük
$$\sigma(A)=\sum_{m\in A} c_m$$
değeridir. Bu toplamı her defasında baştan hesaplamak yerine tüm altkümeler için artımlı biçimde üretmek daha iyidir. Boş olmayan bir \(A\) altkümesinden seçilmiş bir \(r\in A\) elemanını çıkarırsak
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r$$
olur. Böylece önce tüm kaydırmalar tablo halinde elde edilir, sonra işaretli toplam hızlıca yapılır.
Bu örnekte sınırlar
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14$$
şeklindedir. Gevşeklik değişkeni eklendiğinde sınırsız çözüm sayısı
$$\binom{14+3}{3}=\binom{17}{3}=680$$
olur. Tekil ihlallerin kaydırmaları \(3\), \(5\) ve \(9\) olduğundan çıkarılan terimler
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56$$
olur. İkili kesişimler için kaydırmalar \(8\), \(12\) ve \(14\) verir; eklenen terimler de
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1$$
şeklindedir. Üçlü kesişimde kaydırma \(17\) olduğundan geriye negatif toplam kalır ve katkı \(0\)'dır.
Sonuç olarak
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
Bu değer, uygulamanın kullandığı kontrol noktalarından biriyle aynıdır.
Bir kez \(S(n,k,b)\) hızlı hesaplanınca, istenen son değer sadece
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}$$
olur. Yalnızca altı sorgu vardır ve her biri \(k\le 15\) koşulunu korur.
C++, Python ve Java uygulamaları aynı fikri izler. Önce \(15\)'e kadar faktöriyeller ve ters faktöriyeller hazırlanır. Daha sonra her gerekli \(k\) değeri için \(b^1+1,b^2+1,\dots,b^k+1\) listesi oluşturulur.
Ardından \(\{1,\dots,k\}\) kümesinin her altkümesi için toplam kaydırma, daha önce hesaplanmış daha küçük bir altkümeyi kullanarak elde edilir. Kaydırma \(n\)'den büyükse o dahil et-çıkar terimi doğrudan atlanır. Aksi halde \(N=(n-\sigma(A))+k\) oluşturulur, \(10^9+7\) moduna indirgenir, kısa düşen çarpım formülüyle binom katsayısı hesaplanır ve \(|A|\)'nın tek veya çift olmasına göre çıkarılır ya da eklenir.
Bir sorgu tamamlandıktan sonra sıradaki \(k\) işlenir; en sonunda altı sonucun hepsi \(10^9+7\) modunda toplanır.
Tek bir \((n,k,b)\) üçlüsü için ihlal maliyetlerini üretmek \(O(k)\) zaman alır. Tüm altküme kaydırmalarının tablosu \(O(2^k)\) zamanda ve \(O(2^k)\) bellekte kurulur. Dahil et-çıkar toplamında \(2^k\) terim vardır ve her binom hesabı kısa düşen çarpım nedeniyle \(O(k)\) modüler işlem gerektirir.
Dolayısıyla bir sorgunun toplam maliyeti \(O(2^k\cdot k)\) zaman ve \(O(2^k)\) bellektir. Tüm problem bunun yalnızca altı farklı \(k\) için alınmış küçük bir sabit katıdır.
Para enteros \(n\), \(k\) y \(b\), definimos \(S(n,k,b)\) como el número de \(k\)-tuplas \((x_1,\dots,x_k)\) tales que
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n.$$
La cantidad final pedida es
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
Como \(n\) puede ser enorme, no conviene construir una DP sobre todos los valores posibles de la suma. El método correcto convierte la desigualdad en una igualdad, corrige los excesos con inclusión-exclusión y aprovecha que \(k\le 15\) es pequeño.
La estructura del problema favorece recorrer subconjuntos de índices, no valores de suma. Esa es la razón por la que el método funciona incluso cuando \(n\) es muy grande.
Introducimos una variable de holgura \(s\ge 0\) y escribimos
$$x_1+\cdots+x_k+s=n.$$
Ahora contamos soluciones enteras no negativas en \(k+1\) variables, con cotas superiores solo para \(x_1,\dots,x_k\).
Si esas cotas no existieran, el método de stars and bars daría
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}.$$
Por tanto, la tarea real consiste en eliminar exactamente las soluciones donde alguna coordenada supera su límite.
Para cada índice \(m\), definimos el evento de violación
$$E_m=\{x_m\ge b^m+1\}.$$
Sea \(A\subseteq\{1,\dots,k\}\). Si todos los eventos de \(A\) ocurren, hacemos el cambio
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0,\qquad m\in A.$$
La ecuación pasa a ser
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1).$$
Así, el número de soluciones en la intersección correspondiente es
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k},$$
entendiendo que el término vale \(0\) si el argumento superior es negativo o menor que \(k\).
El principio de inclusión-exclusión produce entonces
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
Como \(k\) nunca supera \(15\), recorrer todos los \(2^k\) subconjuntos es totalmente manejable.
Sea \(p=10^9+7\). En todos los casos tenemos \(k\le 15<p\).
Escribimos el argumento superior como
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p.$$
Puesto que \(k\) tiene una sola cifra no nula en base \(p\), el teorema de Lucas implica
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}.$$
Solo importa, por tanto, el residuo \(N\bmod p\). Si \(N_0<k\), el término es \(0\) módulo \(p\). En caso contrario, se usa
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod{p}.$$
Como \(k\) es muy pequeño, el numerador se evalúa con apenas \(k\) multiplicaciones modulares, y \(1/k!\) se precalcula una sola vez.
Para cada \(m\), definimos el coste de violación
$$c_m=b^m+1.$$
La fórmula depende del total
$$\sigma(A)=\sum_{m\in A} c_m.$$
En lugar de recomputarlo desde cero para cada subconjunto, se construyen todos los valores de forma incremental. Si \(A\neq \varnothing\) y quitamos un elemento elegido \(r\in A\), entonces
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r.$$
Con esto, el recorrido de subconjuntos se reduce a rellenar una tabla y luego sumar con el signo adecuado.
Aquí las restricciones son
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14.$$
Tras añadir la holgura \(s\), el conteo sin cotas es
$$\binom{14+3}{3}=\binom{17}{3}=680.$$
Las violaciones simples tienen desplazamientos \(3\), \(5\) y \(9\), por lo que se restan
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56.$$
Las intersecciones dobles usan desplazamientos \(8\), \(12\) y \(14\), y aportan
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1.$$
La intersección triple emplea desplazamiento \(17\), lo que deja total negativo; por eso su contribución es \(0\).
En consecuencia,
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
Ese valor coincide con uno de los puntos de comprobación usados por la implementación.
Una vez que \(S(n,k,b)\) se calcula rápido, la respuesta final es simplemente
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
Solo hay seis consultas y en todas ellas \(k\) sigue siendo muy pequeño.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero precalculan factoriales e inversos factoriales hasta \(15\). Después, para cada valor requerido de \(k\), generan la lista \(b^1+1,b^2+1,\dots,b^k+1\).
Luego construyen el desplazamiento total de cada subconjunto de \(\{1,\dots,k\}\) reutilizando el valor ya conocido de un subconjunto más pequeño. Si el desplazamiento ya supera a \(n\), ese término de inclusión-exclusión se descarta. En caso contrario, se forma \(N=(n-\sigma(A))+k\), se reduce \(N\) módulo \(10^9+7\), se evalúa el binomio mediante un producto descendente corto y se suma o resta según la paridad de \(|A|\).
Al terminar una consulta \(S(n,k,b)\), el programa pasa a la siguiente y al final acumula los seis resultados módulo \(10^9+7\).
Para un triple \((n,k,b)\), construir los costes de violación cuesta \(O(k)\). La tabla de desplazamientos de todos los subconjuntos requiere \(O(2^k)\) tiempo y \(O(2^k)\) memoria. La suma de inclusión-exclusión tiene \(2^k\) términos, y cada binomio necesita \(O(k)\) operaciones modulares porque se evalúa con un producto descendente de longitud \(k\).
Por lo tanto, cada consulta cuesta \(O(2^k\cdot k)\) tiempo y \(O(2^k)\) memoria. La tarea completa solo multiplica ese coste por una constante, ya que se evalúan seis valores de \(k\).
对整数 \(n\)、\(k\)、\(b\)，记 \(S(n,k,b)\) 为满足
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n$$
的整数 \(k\) 元组 \((x_1,\dots,x_k)\) 的个数。最终要求的是
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
这里最大的困难不是变量个数，而是 \(n\) 的规模很大。若按总和做常规动态规划，状态空间会直接爆炸。真正可行的方法是先把不等式改写成等式，再用容斥原理处理每个坐标的上界，并利用 \(k\le 15\) 这一点把复杂度压到很低。
这个问题最适合从“哪些上界被突破”来分类，而不是从“当前总和是多少”来分类。因为上界的个数只有 \(k\) 个，而 \(k\) 非常小。
引入一个松弛变量 \(s\ge 0\)，把条件改写为
$$x_1+\cdots+x_k+s=n.$$
这样我们就在计数 \(k+1\) 个非负整数变量的解，其中只有 \(x_1,\dots,x_k\) 带有上界。
如果暂时忽略这些上界，那么由隔板法可得
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}.$$
因此，问题的本质就是从这个无约束计数中，准确扣除那些某些坐标超出允许范围的解。
对每个 \(m\)，定义“第 \(m\) 个上界被突破”的事件
$$E_m=\{x_m\ge b^m+1\}.$$
固定一个子集 \(A\subseteq\{1,\dots,k\}\)。如果 \(A\) 中所有事件都发生，那么对每个 \(m\in A\) 做平移
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0.$$
原方程就变成
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1).$$
于是，这个交集中的解数就是
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k},$$
其中当上方参数为负数或者小于 \(k\) 时，该项按 \(0\) 处理。
把所有子集按容斥原理组合起来，就得到
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
这一步已经把问题压缩成了对 \(2^k\) 个子集的求和。由于 \(k\le 15\)，这是完全可行的。
设 \(p=10^9+7\)。程序中始终有 \(k\le 15<p\)。
把上方参数写成 \(p\) 进制：
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p.$$
因为 \(k\) 在 \(p\) 进制下只有最低位可能非零，所以 Lucas 定理直接给出
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}.$$
这说明真正需要的只是 \(N\bmod p\)。如果 \(N_0<k\)，那么该二项式系数在模 \(p\) 下就是 \(0\)。否则可以用
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod{p}$$
来计算。由于 \(k\) 很小，分子只需要做 \(k\) 次模乘，而 \(1/k!\) 可以事先预处理出来。
对每个下标 \(m\)，定义它对应的“违规成本”
$$c_m=b^m+1.$$
容斥公式中真正反复出现的是
$$\sigma(A)=\sum_{m\in A} c_m.$$
如果每次都从头求和，会产生很多重复工作。更好的做法是把所有子集的 \(\sigma(A)\) 一次性递推出来。若 \(A\neq\varnothing\)，并从中取出某个固定元素 \(r\in A\)，则有
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r.$$
这样就可以先建立一张完整的子集平移表，再做最终的正负号累加。
此时约束为
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14.$$
加入松弛变量后，无上界解数为
$$\binom{14+3}{3}=\binom{17}{3}=680.$$
单个上界违规对应的平移分别是 \(3\)、\(5\)、\(9\)，所以要减去
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56.$$
两两交集的平移分别是 \(8\)、\(12\)、\(14\)，所以要加回
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1.$$
三重交集的平移是 \(17\)，已经把总和全部耗尽，因此对应项为 \(0\)。
于是
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
这正好与实现中使用的检查值一致，也验证了公式本身。
一旦能够快速求出 \(S(n,k,b)\)，最后答案就只是
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
总共只需要计算六次，而每一次都保持 \(k\le 15\)，因此整体计算量很小。
C++、Python 和 Java 三个实现的结构完全一致。第一步先预处理到 \(15\) 为止的阶乘与逆阶乘，因为所有二项式系数的下标都不会超过 \(15\)。随后，对每个需要的 \(k\)，构造序列 \(b^1+1,b^2+1,\dots,b^k+1\)。
接下来，程序为 \(\{1,\dots,k\}\) 的每个子集生成对应的总平移量，并且复用较小子集已经算出的结果。若某个子集的总平移已经超过 \(n\)，那么这个容斥项必然没有贡献，可以直接跳过。否则就形成 \(N=(n-\sigma(A))+k\)，取其模 \(10^9+7\) 的余数，再用短小的下降乘积计算二项式系数，最后根据子集大小的奇偶性决定加上还是减去该项。
每个 \(S(n,k,b)\) 算完之后，程序继续处理下一个 \(k\)，最终把六个结果在模 \(10^9+7\) 下相加得到答案。
对于单个 \((n,k,b)\)，构造违规成本需要 \(O(k)\) 时间。预处理全部子集平移量需要 \(O(2^k)\) 时间与 \(O(2^k)\) 空间。真正的容斥求和共有 \(2^k\) 项，而每项中的二项式计算由于只做长度为 \(k\) 的下降乘积，因此代价为 \(O(k)\)。
所以单次查询的总复杂度是 \(O(2^k\cdot k)\)，空间复杂度是 \(O(2^k)\)。整个题目只是在 \(k=10,\dots,15\) 上重复六次，因此总耗时只是这一复杂度的一个很小常数倍。
Для целых \(n\), \(k\) и \(b\) обозначим через \(S(n,k,b)\) число \(k\)-кортежей \((x_1,\dots,x_k)\), удовлетворяющих условиям
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n.$$
Итоговая величина, которую нужно найти, равна
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
Здесь трудно не количество переменных, а огромный размер \(n\). Поэтому методы, зависящие от всех промежуточных сумм, не подходят. Рабочее решение использует добавочную переменную, формулу включений-исключений и тот факт, что \(k\le 15\) очень мало.
Главная идея состоит в том, чтобы классифицировать решения по множеству нарушенных верхних границ. Количество таких множеств мало, а потому перебор по подмножествам оказывается эффективным.
Введем переменную запаса \(s\ge 0\) и перепишем условие как
$$x_1+\cdots+x_k+s=n.$$
Теперь мы считаем неотрицательные целочисленные решения в \(k+1\) переменных, причем верхние ограничения есть только у \(x_1,\dots,x_k\).
Если бы этих ограничений не было, формула stars and bars давала бы
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}.$$
Значит, остается аккуратно вычесть решения, в которых хотя бы одна координата превышает допустимую границу.
Для каждого индекса \(m\) введем событие нарушения
$$E_m=\{x_m\ge b^m+1\}.$$
Пусть \(A\subseteq\{1,\dots,k\}\). Если все события из \(A\) выполняются, то для каждого \(m\in A\) заменим переменную по правилу
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0.$$
После этого получаем уравнение
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1).$$
Следовательно, число решений в соответствующем пересечении равно
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k},$$
где принято считать этот член равным \(0\), если верхний аргумент отрицателен или меньше \(k\).
Формула включений-исключений дает точное выражение
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
Так как \(k\le 15\), перебор всех \(2^k\) подмножеств вполне реалистичен.
Обозначим \(p=10^9+7\). Во всех запросах выполнено \(k\le 15<p\).
Запишем верхний аргумент в системе счисления по основанию \(p\):
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p.$$
Поскольку у числа \(k\) в этой системе только один ненулевой разряд, из теоремы Люка следует
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}.$$
Значит, важен только остаток \(N\bmod p\). Если \(N_0<k\), соответствующий член равен нулю по модулю \(p\). Иначе можно использовать формулу
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod{p}.$$
Так как \(k\) мало, здесь нужно всего \(k\) модульных умножений, а обратный к \(k!\) элемент удобно предвычислить заранее.
Для каждого индекса \(m\) введем стоимость нарушения
$$c_m=b^m+1.$$
В формуле многократно встречается величина
$$\sigma(A)=\sum_{m\in A} c_m.$$
Вычислять ее заново для каждого подмножества невыгодно. Лучше построить все значения рекуррентно. Если \(A\neq\varnothing\) и мы удалим из него некоторый выбранный элемент \(r\in A\), то
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r.$$
После этого остается только пройти по готовой таблице и выполнить знакопеременную сумму.
Здесь ограничения таковы:
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14.$$
После добавления переменной \(s\) число решений без верхних границ равно
$$\binom{14+3}{3}=\binom{17}{3}=680.$$
Одиночные нарушения дают сдвиги \(3\), \(5\) и \(9\), поэтому нужно вычесть
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56.$$
Попарные пересечения соответствуют сдвигам \(8\), \(12\) и \(14\), так что нужно прибавить
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1.$$
Для тройного пересечения сдвиг равен \(17\), и после него допустимого остатка уже не остается, так что вклад равен \(0\).
Получаем
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
Это один из проверочных результатов, который воспроизводит реализация.
Как только процедура вычисления \(S(n,k,b)\) готова, полный ответ записывается как
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
Всего требуется шесть вызовов, и во всех из них \(k\) остается маленьким.
Реализации на C++, Python и Java устроены одинаково. Сначала они заранее считают факториалы и обратные факториалы до \(15\). Затем для каждого нужного значения \(k\) строят последовательность \(b^1+1,b^2+1,\dots,b^k+1\).
После этого для каждого подмножества множества \(\{1,\dots,k\}\) вычисляется суммарный сдвиг, причем используется уже известный результат для меньшего подмножества. Если этот сдвиг превышает \(n\), соответствующий член включений-исключений сразу отбрасывается. Иначе программа формирует \(N=(n-\sigma(A))+k\), берет его остаток по модулю \(10^9+7\), вычисляет биномиальный коэффициент через короткое нисходящее произведение и прибавляет либо вычитает его в зависимости от четности \(|A|\).
После завершения одного значения \(S(n,k,b)\) программа переходит к следующему \(k\), а в конце суммирует все шесть результатов по модулю \(10^9+7\).
Для одного набора \((n,k,b)\) построение стоимостей нарушения занимает \(O(k)\) времени. Таблица сдвигов для всех подмножеств требует \(O(2^k)\) времени и \(O(2^k)\) памяти. В сумме включений-исключений имеется \(2^k\) членов, и каждый биномиальный коэффициент вычисляется за \(O(k)\) модульных операций благодаря короткому нисходящему произведению.
Следовательно, одна обработка стоит \(O(2^k\cdot k)\) по времени и \(O(2^k)\) по памяти. Полная задача отличается только постоянным множителем, потому что рассматриваются лишь шесть значений \(k\).
لأعداد صحيحة \(n\) و\(k\) و\(b\)، نرمز بـ \(S(n,k,b)\) إلى عدد المتجهات \((x_1,\dots,x_k)\) التي تحقق
$$0\le x_m\le b^m \quad (1\le m\le k),\qquad \sum_{m=1}^{k} x_m \le n.$$
والكمية النهائية المطلوبة هي
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
الصعوبة هنا ليست في عدد المتغيرات، بل في أن \(n\) قد يكون ضخمًا جدًا. لذلك فإن أي خوارزمية تعتمد على بناء حالات لكل مجموع ممكن ستكون غير عملية. الفكرة الصحيحة هي تحويل المتباينة إلى مساواة، ثم معالجة الحدود العليا بمبدأ الاحتواء والاستبعاد، مع الاستفادة من أن \(k\le 15\) صغير جدًا.
المفتاح هو أن عدد القيود محدود جدًا. ولهذا يصبح من المنطقي أن نصنف الحلول بحسب مجموعة الحدود التي تم تجاوزها، بدلًا من تصنيفها بحسب قيمة المجموع نفسها.
نضيف متغير سماح \(s\ge 0\) ونكتب
$$x_1+\cdots+x_k+s=n.$$
بهذا نكون قد حوّلنا الشرط إلى عدّ حلول صحيحة غير سالبة في \(k+1\) متغيرات، مع بقاء الحدود العليا على \(x_1,\dots,x_k\) فقط.
إذا تجاهلنا تلك الحدود مؤقتًا، فإن طريقة النجوم والقضبان تعطي
$$\#\{(x_1,\dots,x_k,s)\in \mathbb{Z}_{\ge 0}^{k+1}:x_1+\cdots+x_k+s=n\}=\binom{n+k}{k}.$$
إذن العمل الحقيقي هو تصحيح هذا العدد العام بحذف الحلول التي تتجاوز فيها بعض الإحداثيات حدودها المسموح بها.
لكل فهرس \(m\)، نعرّف حدث تجاوز الحد الأعلى على أنه
$$E_m=\{x_m\ge b^m+1\}.$$
ولتكن \(A\subseteq\{1,\dots,k\}\). إذا تحققت جميع الأحداث في \(A\)، فإننا نكتب لكل \(m\in A\)
$$x_m=y_m+(b^m+1),\qquad y_m\ge 0.$$
بعد هذا الإزاحة يصبح لدينا
$$\sum_{m\notin A} x_m+\sum_{m\in A} y_m+s=n-\sum_{m\in A}(b^m+1).$$
ومن ثم فإن عدد الحلول في هذا التقاطع يساوي
$$\binom{n-\sum_{m\in A}(b^m+1)+k}{k},$$
مع اعتبار هذا الحد مساويًا للصفر إذا كان الوسيط العلوي سالبًا أو أصغر من \(k\).
وبذلك نحصل من الاحتواء والاستبعاد على الصيغة الدقيقة
$$\boxed{S(n,k,b)=\sum_{A\subseteq\{1,\dots,k\}} (-1)^{|A|}\binom{n-\sum_{m\in A}(b^m+1)+k}{k}.}$$
وبما أن \(k\le 15\)، فإن المرور على جميع المجموعات الجزئية وعددها \(2^k\) يبقى صغيرًا.
لنأخذ \(p=10^9+7\). في جميع الحالات لدينا \(k\le 15<p\).
نكتب الوسيط العلوي بالشكل
$$N=N_0+N_1p+N_2p^2+\cdots,\qquad 0\le N_0<p.$$
وبما أن \(k\) يملك خانة غير صفرية واحدة فقط في التمثيل بالأساس \(p\)، فإن مبرهنة لوكاس تعطي
$$\binom{N}{k}\equiv \binom{N_0}{k}\pmod{p}.$$
إذن لا نحتاج إلا إلى الباقي \(N\bmod p\). فإذا كان \(N_0<k\) كان الحد مساويًا للصفر بترديد \(p\). أما إذا كان \(N_0\ge k\) فنستخدم
$$\binom{N}{k}\equiv \frac{N_0(N_0-1)\cdots(N_0-k+1)}{k!}\pmod{p}.$$
وبما أن \(k\) صغير جدًا، فإن هذا الحساب يتطلب عددًا قليلًا من الضربات المعيارية، بينما يمكن تجهيز معكوس \(k!\) مرة واحدة مسبقًا.
لكل فهرس \(m\)، نعرّف تكلفة المخالفة بأنها
$$c_m=b^m+1.$$
والكمية المتكررة في الصيغة هي
$$\sigma(A)=\sum_{m\in A} c_m.$$
بدلًا من إعادة جمع هذه القيم من البداية لكل مجموعة جزئية، يمكن بناؤها تدريجيًا. فإذا كانت \(A\neq\varnothing\) وأخرجنا منها عنصرًا مختارًا \(r\in A\)، فلدينا
$$\sigma(A)=\sigma(A\setminus\{r\})+c_r.$$
وهكذا نبني جدولًا كاملًا لكل الإزاحات مرة واحدة، ثم ننجز مجموع الاحتواء والاستبعاد بسرعة.
في هذا المثال تكون القيود
$$x_1\le 2,\qquad x_2\le 4,\qquad x_3\le 8,\qquad x_1+x_2+x_3\le 14.$$
بعد إضافة متغير السماح \(s\)، يصبح العدد غير المقيد
$$\binom{14+3}{3}=\binom{17}{3}=680.$$
الإزاحات الخاصة بالمخالفات المفردة هي \(3\) و\(5\) و\(9\)، لذا نطرح
$$\binom{14}{3}=364,\qquad \binom{12}{3}=220,\qquad \binom{8}{3}=56.$$
أما التقاطعات الثنائية فتعطي الإزاحات \(8\) و\(12\) و\(14\)، ولذلك نضيف
$$\binom{9}{3}=84,\qquad \binom{5}{3}=10,\qquad \binom{3}{3}=1.$$
وبالنسبة للتقاطع الثلاثي فإزاحته \(17\)، أي لا يبقى مجموع موجب يمكن توزيعه، ولهذا تكون مساهمته \(0\).
إذن
$$S(14,3,2)=680-(364+220+56)+(84+10+1)=135.$$
وهذه القيمة هي نفسها إحدى قيم التحقق التي تعيدها التطبيقات.
بعد أن يصبح حساب \(S(n,k,b)\) سريعًا، فإن الجواب النهائي ليس إلا
$$\sum_{k=10}^{15} S(10^k,k,k)\pmod{10^9+7}.$$
يوجد ستة استعلامات فقط، وكل واحد منها يبقى ضمن المجال الصغير \(k\le 15\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. تبدأ بحساب القيم المسبقة للعوامل \(0!,1!,\dots,15!\) ومعكوساتها المعيارية، لأن جميع المقامات في معاملات ثنائية الحدين تقع ضمن هذا المجال. بعد ذلك، ولكل قيمة مطلوبة من \(k\)، تُبنى القائمة \(b^1+1,b^2+1,\dots,b^k+1\).
ثم يُحسب لكل مجموعة جزئية من \(\{1,\dots,k\}\) مجموع الإزاحة الكلي بالاستفادة من مجموعة أصغر سبق حسابها. إذا تجاوزت الإزاحة القيمة \(n\)، فإن حد الاحتواء والاستبعاد المقابل يساوي صفرًا ويمكن تجاوزه مباشرة. وإلا يُشكَّل العدد \(N=(n-\sigma(A))+k\)، ويؤخذ باقِيه بترديد \(10^9+7\)، ثم يُحسب معامل ثنائية الحدين بواسطة حاصل ضرب تنازلي قصير، وبعدها يُضاف الحد أو يُطرح وفقًا لفردية أو زوجية \(|A|\).
بعد إنهاء قيمة واحدة من \(S(n,k,b)\)، ينتقل البرنامج إلى القيمة التالية من \(k\)، وفي النهاية يجمع النتائج الستة كلها بترديد \(10^9+7\).
بالنسبة إلى ثلاثية واحدة \((n,k,b)\)، فإن تجهيز تكاليف المخالفة يحتاج إلى \(O(k)\) من الزمن. أما جدول إزاحات جميع المجموعات الجزئية فيحتاج إلى \(O(2^k)\) زمنًا و\(O(2^k)\) ذاكرة. وفي مجموع الاحتواء والاستبعاد يوجد \(2^k\) حدًا، وكل حد يتطلب \(O(k)\) عمليات معيارية لحساب معامل ثنائية الحدين.
إذًا التعقيد الكلي للاستعلام الواحد هو \(O(2^k\cdot k)\) زمنًا و\(O(2^k)\) ذاكرة. والمسألة الكاملة لا تزيد على ذلك إلا بعامل ثابت صغير، لأنها تحسب ست قيم فقط.