Define
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
The task is to evaluate \(F(10^9,10^9)\) modulo \(1234567891\). The published checkpoints are
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$$
A direct enumeration of \(10^9\)-tuples is impossible, so the solution has to exploit the multiplicative structure of the product bound.
For a fixed tuple length \(t\), let
$$P_t(v)=F(v,t).$$
When \(t=0\), there is exactly one admissible tuple: the empty tuple. Therefore
$$P_0(v)=1\qquad (v\ge 1).$$
For \(t\ge 1\), choose the first entry \(x=a_1\). Once \(x\) is fixed, the remaining \(t-1\) entries must satisfy
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor.$$
This gives the exact recurrence
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
That identity is the backbone of all three implementations: the problem is transformed into repeated sums over floor quotients.
For fixed \(m\), define the compressed state set
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$$
This set contains only \(O(\sqrt{m})\) distinct values. The usual reason is that quotients larger than \(\sqrt{m}\) can occur only for \(i\le \sqrt{m}\), while every quotient at most \(\sqrt{m}\) lies in the small tail. Hence \(|\mathcal{V}(m)|\le 2\sqrt{m}\).
The crucial closure property is that every transition in the recurrence stays inside the same compressed set. If \(v=\lfloor m/i\rfloor\), then
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
So the dynamic program never needs values outside \(\mathcal{V}(m)\).
For each state \(v\in\mathcal{V}(m)\), the terms \(\lfloor v/x\rfloor\) are constant on intervals. If
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$$
then the same quotient persists for all \(x\) in
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor.$$
Therefore the transition can be grouped by quotient blocks:
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
The implementation precomputes these blocks once and then reuses them for every DP layer.
Remove every entry equal to \(1\) from an admissible tuple. The remaining ordered core tuple has length \(r\), every entry is at least \(2\), and its product is still at most \(m\). Hence
$$2^r \le m,$$
so
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
Now let \(C_r(m)\) be the number of ordered \(r\)-tuples \((b_1,\dots,b_r)\) with each \(b_i\ge 2\) and \(b_1\cdots b_r\le m\). Once such a core tuple is fixed, we obtain an \(n\)-tuple by choosing which \(r\) of the \(n\) positions carry the non-1 entries. That contributes exactly \(\binom{n}{r}\) placements. Therefore
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
So for fixed \(m\), the answer is a polynomial in \(n\) of degree at most \(d\), written in the binomial basis. For \(m=10^9\), we have \(d=29\), which is why the implementation only needs the values for \(n=0,1,\dots,29\).
Let \(Q(n)=F(m,n)\). Any polynomial of degree at most \(d\) has the Newton expansion
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$$
where \(\Delta\) denotes the forward-difference operator. In this problem the coefficients \(\Delta^r Q(0)\) coincide with the binomial-basis coefficients \(C_r(m)\).
The DP is used only to compute the sample values
$$Q(0),Q(1),\dots,Q(d).$$
After that, a short forward-difference table recovers the coefficients, and the polynomial is evaluated at the huge target \(n=10^9\).
The modulus \(1234567891\) is composite, so the program does not rely on Fermat-style modular inverses for \(\binom{n}{r}\). Instead it builds the numerator
$$\frac{n(n-1)\cdots(n-r+1)}{r!}$$
with exact integer cancellation by gcd, and only then reduces the result modulo \(1234567891\). Since \(r\le 29\), this step is tiny.
Here \(d=\lfloor \log_2 10\rfloor=3\). The dynamic program gives
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$$
The forward differences are
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$$
Hence
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
This also has a direct combinatorial meaning:
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
The eight ordered pairs with product at most \(10\) are \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\), and the only ordered triple is \((2,2,2)\). Evaluating at \(n=10\) gives
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
which matches the checkpoint exactly.
The implementation first builds the compressed list of distinct quotients \(\lfloor m/i\rfloor\). For every compressed state it precomputes the quotient blocks \([\ell,r]\) together with the target compressed state and the multiplicity \(r-\ell+1\). It then runs the recurrence for tuple lengths \(0\) through \(d\), keeping only the previous and current DP layers, and records the values at the state \(v=m\).
Those sampled values are converted into forward differences, and the final Newton series is evaluated at the requested \(n\). The C++, Python, and Java implementations all follow that same mathematical pipeline, so the checkpoints agree across languages.
The compressed state count is \(S=|\mathcal{V}(m)|=O(\sqrt{m})\). For a state \(v\), the number of quotient blocks is \(O(\sqrt{v})\), so the total precomputed transition size is
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$$
Running the DP for \(d=\lfloor \log_2 m\rfloor\) layers therefore costs \(O(Bd)\) time after precomputation, and the memory usage is \(O(B+S)\). The forward-difference table and the final binomial evaluation are only \(O(d^2)\) and \(O(d)\), negligible here because \(d=29\) for \(m=10^9\).
Definiert sei
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
Gesucht ist \(F(10^9,10^9)\) modulo \(1234567891\). Als Kontrollwerte sind gegeben
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$$
Eine direkte Enumeration aller Tupel ist hoffnungslos; man muss die Struktur der Produktbedingung algebraisch ausnutzen.
Für feste Tupellänge \(t\) setzen wir
$$P_t(v)=F(v,t).$$
Für \(t=0\) gibt es genau ein zulässiges Tupel, nämlich das leere Tupel. Also gilt
$$P_0(v)=1\qquad (v\ge 1).$$
Für \(t\ge 1\) wählen wir das erste Element \(x=a_1\). Dann müssen die restlichen \(t-1\) Elemente die Bedingung
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor$$
erfüllen. Daraus folgt unmittelbar die Rekursion
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
Genau diese Formel wird in der Implementierung schichtweise ausgewertet.
Für festes \(m\) betrachten wir die Menge
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$$
Diese Menge besitzt nur \(O(\sqrt{m})\) verschiedene Werte. Quotienten größer als \(\sqrt{m}\) können nur für \(i\le \sqrt{m}\) auftreten, und alle kleineren Quotienten liegen im unteren Bereich. Daher gilt \(|\mathcal{V}(m)|\le 2\sqrt{m}\).
Wichtig ist, dass die Rekursion in dieser Menge abgeschlossen bleibt. Ist \(v=\lfloor m/i\rfloor\), so gilt
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
Man muss also nur Werte auf dieser komprimierten Zustandsmenge speichern.
Für ein festes \(v\) bleibt \(\lfloor v/x\rfloor\) auf ganzen Intervallen konstant. Setzt man
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$$
so gilt derselbe Quotient für alle \(x\) mit
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor.$$
Damit lässt sich die Summe blockweise schreiben:
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
Diese Blockzerlegung wird einmal vorab berechnet und anschließend in allen DP-Schichten wiederverwendet.
Entfernt man aus einem zulässigen Tupel alle Einsen, bleibt ein geordnetes Kerntupel der Länge \(r\), dessen Einträge sämtlich mindestens \(2\) sind. Da das Produkt weiter höchstens \(m\) ist, folgt
$$2^r \le m,$$
also
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
Bezeichne nun mit \(C_r(m)\) die Anzahl geordneter \(r\)-Tupel \((b_1,\dots,b_r)\) mit \(b_i\ge 2\) und \(b_1\cdots b_r\le m\). Ist ein solches Kerntupel fest, dann erhält man ein \(n\)-Tupel genau dadurch, dass man die \(r\) Nicht-Einsen auf \(r\) der \(n\) Positionen setzt. Dafür gibt es \(\binom{n}{r}\) Möglichkeiten. Also
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
Für festes \(m\) ist die Antwort also ein Polynom in \(n\) vom Grad höchstens \(d\), geschrieben in der Binomialbasis. Bei \(m=10^9\) ist \(d=29\), deshalb genügen die Werte für \(n=0,1,\dots,29\).
Schreibe \(Q(n)=F(m,n)\). Jedes Polynom vom Grad höchstens \(d\) besitzt die Newton-Darstellung
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$$
wobei \(\Delta\) der Operator der Vorwärtsdifferenz ist. In diesem Problem sind die Koeffizienten \(\Delta^r Q(0)\) genau die Binomialbasis-Koeffizienten \(C_r(m)\).
Die DP berechnet also nur die Stichprobenwerte
$$Q(0),Q(1),\dots,Q(d).$$
Daraus wird eine kurze Differenztabelle aufgebaut, und anschließend wird das Polynom an der sehr großen Stelle \(n=10^9\) ausgewertet.
Der Modul \(1234567891\) ist nicht prim. Deshalb verwendet das Programm für \(\binom{n}{r}\) keine Fermat-Inversen, sondern exakte ganzzahlige Kürzungen mit ggT im Ausdruck
$$\frac{n(n-1)\cdots(n-r+1)}{r!}.$$
Da \(r\le 29\), ist dieser Schritt sehr klein.
Hier ist \(d=\lfloor \log_2 10\rfloor=3\). Die DP liefert
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$$
Die Vorwärtsdifferenzen lauten
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$$
Somit gilt
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
Kombinatorisch bedeutet das
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
Die acht geordneten Paare mit Produkt höchstens \(10\) sind \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\), und als einziges geordnetes Tripel bleibt \((2,2,2)\). Für \(n=10\) erhält man
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
genau den angegebenen Kontrollwert.
Die Implementierung erzeugt zuerst die komprimierte Liste der verschiedenen Werte \(\lfloor m/i\rfloor\). Für jeden Zustand werden die Quotientenblöcke \([\ell,r]\), der zugehörige Zielzustand und die Blocklänge \(r-\ell+1\) vorab gespeichert. Danach wird die Rekursion für Tupellängen von \(0\) bis \(d\) mit zwei rollierenden DP-Ebenen ausgewertet, und jeweils der Wert zum Zustand \(v=m\) aufgezeichnet.
Aus dieser Folge entstehen per Vorwärtsdifferenzen die Newton-Koeffizienten. Anschließend wird die Reihe bei der gewünschten Länge \(n\) ausgewertet. Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Abfolge und stimmen daher bei den Kontrollwerten überein.
Die Zahl der komprimierten Zustände ist \(S=|\mathcal{V}(m)|=O(\sqrt{m})\). Für einen Zustand \(v\) gibt es \(O(\sqrt{v})\) Quotientenblöcke, also ist die gesamte vorab gespeicherte Übergangsgröße
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$$
Die DP über \(d=\lfloor \log_2 m\rfloor\) Schichten benötigt damit nach der Vorberechnung \(O(Bd)\) Zeit und \(O(B+S)\) Speicher. Die Differenztabelle und die abschließende Binomialauswertung kosten nur \(O(d^2)\) beziehungsweise \(O(d)\) und sind hier vernachlässigbar, weil für \(m=10^9\) nur \(d=29\) ist.
Şu fonksiyonu tanımlayalım:
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
İstenen değer \(F(10^9,10^9)\) mod \(1234567891\)'dir. Verilen kontrol sonuçları
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}$$
şeklindedir. \(10^9\) uzunluklu dizileri doğrudan saymak mümkün olmadığından, çözüm çarpım kısıtının yapısını kullanır.
Sabit bir \(t\) uzunluğu için
$$P_t(v)=F(v,t)$$
tanımını yapalım. \(t=0\) iken tek uygun dizi boş dizidir; dolayısıyla
$$P_0(v)=1\qquad (v\ge 1).$$
\(t\ge 1\) olduğunda ilk elemanı \(x=a_1\) seçelim. O zaman kalan \(t-1\) elemanın çarpımı
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor$$
olmalıdır. Böylece temel bağıntı elde edilir:
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
Üç uygulamanın da dayandığı esas formül budur.
Sabit \(m\) için
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}$$
kümesini tanımlayalım. Bu kümede yalnızca \(O(\sqrt{m})\) farklı değer vardır. \(\sqrt{m}\)'den büyük bölümler ancak \(i\le \sqrt{m}\) için ortaya çıkar; \(\sqrt{m}\)'den küçük olanlar ise alt tarafta toplanır. Bu yüzden \(|\mathcal{V}(m)|\le 2\sqrt{m}\).
Daha önemlisi, geçişler aynı küme içinde kalır. Eğer \(v=\lfloor m/i\rfloor\) ise
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
Yani dinamik program yalnızca bu sıkıştırılmış durum kümesi üzerinde yürütülebilir.
Sabit bir \(v\) için \(\lfloor v/x\rfloor\) değeri aralıklar boyunca sabittir. Eğer
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor$$
ise aynı bölüm tüm
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor$$
değerleri için geçerlidir. Böylece toplam bloklara ayrılır:
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
Uygulama bu blokları bir kez önceden hesaplar ve sonra her katmanda yeniden kullanır.
Uygun bir diziden tüm \(1\) değerlerini çıkaralım. Geriye uzunluğu \(r\) olan sıralı bir çekirdek dizi kalır; bu dizideki her eleman en az \(2\)'dir ve çarpım yine en fazla \(m\)'dir. Bu nedenle
$$2^r \le m,$$
dolayısıyla
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
Şimdi \(C_r(m)\), her elemanı en az \(2\) olan ve çarpımı \(m\)'yi geçmeyen sıralı \(r\)-li çekirdek dizilerin sayısı olsun. Böyle bir çekirdek sabitlenince, bu \(r\) adet \(1\) olmayan elemanı \(n\) konum arasına yerleştirme sayısı tam olarak \(\binom{n}{r}\)'dir. Sonuç olarak
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
Yani sabit \(m\) için cevap, binom tabanında yazılmış ve derecesi en fazla \(d\) olan bir polinomdur. \(m=10^9\) için \(d=29\) olduğundan, uygulama yalnızca \(n=0,1,\dots,29\) değerlerini hesaplar.
\(Q(n)=F(m,n)\) yazalım. Derecesi en fazla \(d\) olan her polinom için Newton açılımı
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r}$$
şeklindedir. Burada \(\Delta\) ileri fark operatörüdür. Bu problemde \(\Delta^r Q(0)\) katsayıları, az önceki \(C_r(m)\) değerleriyle aynıdır.
Bu yüzden dinamik program yalnızca
$$Q(0),Q(1),\dots,Q(d)$$
örneklerini üretir. Ardından kısa bir fark tablosu kurulur ve polinom çok büyük olan \(n=10^9\) noktasında değerlendirilir.
Modül \(1234567891\) asal değildir. Bu nedenle \(\binom{n}{r}\) hesabında Fermat tipi tersler kullanılmaz. Onun yerine
$$\frac{n(n-1)\cdots(n-r+1)}{r!}$$
ifadesinde pay ve payda gcd ile tam olarak sadeleştirilir, sonra mod alınır. \(r\le 29\) olduğu için bu adım çok küçüktür.
Bu durumda \(d=\lfloor \log_2 10\rfloor=3\) olur. Dinamik program
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53$$
değerlerini verir. İleri farklar ise
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1$$
şeklindedir. Dolayısıyla
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
Bunun kombinatorik yorumu da nettir:
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
Çarpımı \(10\)'u aşmayan sekiz sıralı ikili dizi \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\) olur; tek sıralı üçlü ise \((2,2,2)\)'dir. \(n=10\) için
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
yani kontrol sonucu tam olarak elde edilir.
Uygulama önce \(\lfloor m/i\rfloor\) biçimindeki farklı bölüm değerlerini tek bir sıkıştırılmış listede toplar. Sonra her durum için blok aralıklarını \([\ell,r]\), bu aralıkların hedef durumlarını ve çokluklarını önceden kaydeder. Ardından iki dönen DP katmanı kullanılarak uzunluk \(0\)'dan \(d\)'ye kadar ilerlenir ve her adımda \(v=m\) durumundaki değer saklanır.
Bu örnek değerler sonlu fark katsayılarına dönüştürülür, en sonunda da Newton açılımı hedef \(n\) üzerinde hesaplanır. C++, Python ve Java uygulamaları aynı matematiksel akışı izlediği için kontrol değerleri her dilde aynıdır.
Sıkıştırılmış durum sayısı \(S=|\mathcal{V}(m)|=O(\sqrt{m})\)'dir. Bir \(v\) durumu için bölüm bloklarının sayısı \(O(\sqrt{v})\) olduğundan, toplam geçiş tablosu büyüklüğü
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4})$$
olur. Böylece \(d=\lfloor \log_2 m\rfloor\) katmanlı DP'nin zamanı \(O(Bd)\), belleği ise \(O(B+S)\) olur. Sonlu fark tablosu ve son binom hesapları yalnızca \(O(d^2)\) ve \(O(d)\) düzeyindedir; burada \(d=29\) olduğu için ihmal edilebilir.
Se define
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
Hay que calcular \(F(10^9,10^9)\) módulo \(1234567891\). Los valores de control publicados son
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$$
Enumerar directamente todas las \(10^9\)-tuplas es imposible; la solución reorganiza el conteo a partir de cocientes enteros y de una interpolación polinómica corta.
Para una longitud fija \(t\), escribimos
$$P_t(v)=F(v,t).$$
Cuando \(t=0\), solo existe una tupla válida: la tupla vacía. Por tanto
$$P_0(v)=1\qquad (v\ge 1).$$
Si \(t\ge 1\), elegimos el primer factor \(x=a_1\). Entonces los \(t-1\) factores restantes deben satisfacer
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor.$$
De aquí sale la recurrencia exacta
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
La implementación no hace otra cosa que evaluar esta identidad de forma eficiente.
Para un \(m\) fijo consideramos
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$$
Este conjunto tiene solo \(O(\sqrt{m})\) valores distintos. Los cocientes mayores que \(\sqrt{m}\) solo pueden aparecer para \(i\le \sqrt{m}\), y los menores o iguales a \(\sqrt{m}\) forman la cola pequeña. En consecuencia \(|\mathcal{V}(m)|\le 2\sqrt{m}\).
Además, la recurrencia nunca sale de ese conjunto. Si \(v=\lfloor m/i\rfloor\), entonces
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
Así, basta con almacenar la DP en estados comprimidos.
Para un valor fijo \(v\), el cociente \(\lfloor v/x\rfloor\) permanece constante por bloques. Si
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$$
entonces ese mismo cociente vale para todo
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor.$$
Por tanto
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
Los bloques se precomputan una sola vez y se reutilizan en todas las capas.
Tomemos una tupla válida y eliminemos todas las entradas iguales a \(1\). Queda una tupla núcleo ordenada de longitud \(r\), con todos sus elementos al menos \(2\), y con producto todavía acotado por \(m\). Entonces
$$2^r \le m,$$
de modo que
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
Sea \(C_r(m)\) el número de \(r\)-tuplas ordenadas \((b_1,\dots,b_r)\) con \(b_i\ge 2\) y \(b_1\cdots b_r\le m\). Una vez fijada la tupla núcleo, formar una \(n\)-tupla solo requiere elegir qué \(r\) posiciones contienen los valores distintos de \(1\). Eso da exactamente \(\binom{n}{r}\) opciones. Luego
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
Para \(m\) fijo, la respuesta es un polinomio de grado a lo sumo \(d\), expresado en base binomial. Cuando \(m=10^9\), se tiene \(d=29\), y por eso la implementación solo necesita \(n=0,1,\dots,29\).
Escribamos \(Q(n)=F(m,n)\). Todo polinomio de grado a lo sumo \(d\) admite la expansión de Newton
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$$
donde \(\Delta\) es el operador de diferencia hacia adelante. En este problema, los coeficientes \(\Delta^r Q(0)\) coinciden con los coeficientes \(C_r(m)\) de la base binomial.
Por eso la DP solo calcula los valores
$$Q(0),Q(1),\dots,Q(d).$$
Luego se construye la tabla corta de diferencias y finalmente se evalúa el polinomio en el enorme valor \(n=10^9\).
El módulo \(1234567891\) es compuesto, así que no conviene usar inversos modulares del tipo de Fermat para \(\binom{n}{r}\). En su lugar, el programa arma
$$\frac{n(n-1)\cdots(n-r+1)}{r!}$$
cancelando exactamente numerador y denominador mediante gcd antes de reducir módulo \(1234567891\). Como \(r\le 29\), este paso es muy pequeño.
Aquí \(d=\lfloor \log_2 10\rfloor=3\). La DP produce
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$$
Las diferencias hacia adelante son
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$$
En consecuencia
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
También puede verse de forma combinatoria:
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
Las ocho parejas ordenadas con producto a lo sumo \(10\) son \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\), y la única terna ordenada es \((2,2,2)\). Para \(n=10\) resulta
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
exactamente el valor de comprobación.
La implementación empieza construyendo la lista comprimida de valores distintos \(\lfloor m/i\rfloor\). Para cada estado precomputa los bloques \([\ell,r]\), el estado de destino correspondiente y la multiplicidad \(r-\ell+1\). Después ejecuta la recurrencia para longitudes desde \(0\) hasta \(d\), manteniendo solo dos capas de DP, y guarda en cada paso el valor asociado al estado \(v=m\).
Con esa secuencia forma la tabla de diferencias finitas y evalúa al final la serie de Newton en el \(n\) pedido. Las implementaciones en C++, Python y Java siguen exactamente esa misma cadena matemática, por eso comparten los mismos checkpoints.
El número de estados comprimidos es \(S=|\mathcal{V}(m)|=O(\sqrt{m})\). Para cada estado \(v\), el número de bloques de cociente es \(O(\sqrt{v})\), así que el tamaño total de la tabla de transiciones cumple
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$$
Ejecutar la DP durante \(d=\lfloor \log_2 m\rfloor\) capas cuesta entonces \(O(Bd)\) tiempo tras la precomputación, con memoria \(O(B+S)\). La tabla de diferencias y la evaluación final de binomios cuestan solo \(O(d^2)\) y \(O(d)\), despreciables aquí porque para \(m=10^9\) se tiene \(d=29\).
定义
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
题目要求计算 \(F(10^9,10^9)\bmod 1234567891\)。已知校验值为
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$$
直接枚举长度为 \(10^9\) 的正整数序列完全不可行，因此必须把乘积约束改写成可以压缩和插值的形式。
对固定长度 \(t\)，记
$$P_t(v)=F(v,t).$$
当 \(t=0\) 时，唯一合法对象是空序列，所以
$$P_0(v)=1\qquad (v\ge 1).$$
若 \(t\ge 1\)，先选第一个因子 \(x=a_1\)。剩余 \(t-1\) 个因子的乘积必须满足
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor.$$
于是得到精确递推式
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
整个算法的核心，就是把这个递推式高效地算出来。
对固定的 \(m\)，定义状态集合
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$$
这个集合只有 \(O(\sqrt{m})\) 个不同取值。原因是：大于 \(\sqrt{m}\) 的商只会在 \(i\le \sqrt{m}\) 时出现，而不超过 \(\sqrt{m}\) 的商全部落在小值尾部，因此 \(|\mathcal{V}(m)|\le 2\sqrt{m}\)。
更关键的是，递推中的下一层状态仍然落在同一个集合里。若 \(v=\lfloor m/i\rfloor\)，则
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
因此动态规划只需要在这组压缩状态上进行。
对固定 \(v\)，值 \(\lfloor v/x\rfloor\) 会在整段区间上保持不变。若
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$$
那么对所有
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor$$
都有相同的商。于是递推可以改写成分块求和：
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
实现中把这些分块一次性预处理出来，之后每一层都直接复用。
把一个合法序列中所有等于 \(1\) 的项删掉，剩下的是一个长度为 \(r\) 的有序核心序列，每一项都至少为 \(2\)，而且乘积仍然不超过 \(m\)。因此
$$2^r \le m,$$
所以
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
记 \(C_r(m)\) 为满足“每项至少为 \(2\)、总乘积不超过 \(m\)”的有序 \(r\) 元核心序列个数。固定一个核心序列以后，只需从 \(n\) 个位置中选出 \(r\) 个位置放置这些非 \(1\) 项，其余位置全放 \(1\)，方案数正好是 \(\binom{n}{r}\)。因此
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
也就是说，对固定 \(m\)，答案是关于 \(n\) 的一个次数不超过 \(d\) 的多项式，而且天然写成二项式基底形式。对于 \(m=10^9\)，有 \(d=29\)，所以只需要先算出 \(n=0,1,\dots,29\) 的值。
设 \(Q(n)=F(m,n)\)。任何次数不超过 \(d\) 的多项式都可以写成 Newton 展开式
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$$
其中 \(\Delta\) 是前向差分算子。在本题中，\(\Delta^r Q(0)\) 正好就是前面二项式基底中的系数 \(C_r(m)\)。
所以动态规划只需要得到
$$Q(0),Q(1),\dots,Q(d)$$
这一小段数值，然后通过差分表恢复系数，再在极大的 \(n=10^9\) 处求值。
模数 \(1234567891\) 不是素数，因此计算 \(\binom{n}{r}\) 时不能依赖费马小定理型的逆元。实现采用的是整数层面的精确约分：先构造
$$\frac{n(n-1)\cdots(n-r+1)}{r!}$$
并用 gcd 把分子分母完全约掉，最后再取模。因为这里 \(r\le 29\)，这一步非常轻量。
此时 \(d=\lfloor \log_2 10\rfloor=3\)。动态规划得到
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$$
前向差分为
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$$
因此
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
这也有直接的组合解释：
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
乘积不超过 \(10\) 的有序二元核心序列共有八个： \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\)，而唯一的三元核心序列是 \((2,2,2)\)。代入 \(n=10\) 得到
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
与题目给出的校验值完全一致。
实现先生成所有不同的 \(\lfloor m/i\rfloor\) 压缩状态。然后对每个状态预处理整除分块区间 \([\ell,r]\)、对应的目标状态以及块长度 \(r-\ell+1\)。接着只用两层滚动数组执行长度从 \(0\) 到 \(d\) 的动态规划，并在每一层记录状态 \(v=m\) 的取值。
这些采样值再被转成前向差分系数，最后利用 Newton 展开在目标 \(n\) 处求值。C++、Python 和 Java 实现遵循同一条数学流水线，因此校验结果完全一致。
压缩状态数为 \(S=|\mathcal{V}(m)|=O(\sqrt{m})\)。对单个状态 \(v\)，整除分块个数是 \(O(\sqrt{v})\)，因此总的转移表大小满足
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$$
在预处理之后，进行 \(d=\lfloor \log_2 m\rfloor\) 层动态规划的总时间为 \(O(Bd)\)，空间为 \(O(B+S)\)。而差分表与最终的二项式求值仅需 \(O(d^2)\) 和 \(O(d)\)，对本题来说可以忽略，因为 \(m=10^9\) 时只有 \(d=29\)。
Определим
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
Нужно вычислить \(F(10^9,10^9)\) по модулю \(1234567891\). Контрольные значения таковы:
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$$
Прямой перебор невозможен, поэтому решение строится на рекуррентном счете, сжатии состояний по целым частям и последующей полиномиальной интерполяции.
Для фиксированной длины \(t\) положим
$$P_t(v)=F(v,t).$$
При \(t=0\) существует ровно один допустимый объект: пустой кортеж. Следовательно,
$$P_0(v)=1\qquad (v\ge 1).$$
Пусть теперь \(t\ge 1\). Выберем первый множитель \(x=a_1\). Тогда для оставшихся \(t-1\) координат нужно выполнить условие
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor.$$
Отсюда получается точная рекурсия
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
Именно эта формула лежит в основе вычисления.
Для фиксированного \(m\) рассмотрим множество
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$$
У него всего \(O(\sqrt{m})\) различных значений. Частные больше \(\sqrt{m}\) появляются только при \(i\le \sqrt{m}\), а все малые частные собираются в хвосте. Поэтому \(|\mathcal{V}(m)|\le 2\sqrt{m}\).
Важно, что все переходы рекурсии остаются внутри того же множества. Если \(v=\lfloor m/i\rfloor\), то
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
Значит, хранить значения динамики достаточно только на сжатом наборе состояний.
Для фиксированного \(v\) выражение \(\lfloor v/x\rfloor\) постоянно на целых интервалах. Если
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$$
то тот же частный сохраняется при всех
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor.$$
Поэтому переход переписывается как сумма по блокам:
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
Эти блоки предварительно строятся один раз и затем используются на каждом слое DP.
Удалим из допустимого кортежа все единицы. Останется упорядоченное ядро длины \(r\), в котором каждый элемент не меньше \(2\), а произведение по-прежнему не превосходит \(m\). Следовательно,
$$2^r \le m,$$
то есть
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
Обозначим через \(C_r(m)\) число упорядоченных \(r\)-кортежей \((b_1,\dots,b_r)\) с \(b_i\ge 2\) и \(b_1\cdots b_r\le m\). Если такое ядро зафиксировано, то для построения \(n\)-кортежа нужно лишь выбрать, в какие \(r\) из \(n\) позиций поставить элементы ядра; остальные позиции займут единицы. Это дает ровно \(\binom{n}{r}\) вариантов. Поэтому
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
Значит, при фиксированном \(m\) ответ является полиномом по \(n\) степени не выше \(d\), записанным в биномиальном базисе. Для \(m=10^9\) получаем \(d=29\), и потому достаточно вычислить значения только для \(n=0,1,\dots,29\).
Пусть \(Q(n)=F(m,n)\). Любой полином степени не выше \(d\) имеет разложение Ньютона
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$$
где \(\Delta\) обозначает оператор конечной разности вперед. В этой задаче коэффициенты \(\Delta^r Q(0)\) совпадают с коэффициентами \(C_r(m)\) в биномиальном базисе.
Поэтому динамика нужна только для вычисления короткой последовательности
$$Q(0),Q(1),\dots,Q(d).$$
После этого строится таблица конечных разностей, и затем полином подставляется в огромную точку \(n=10^9\).
Модуль \(1234567891\) составной, поэтому для \(\binom{n}{r}\) нельзя безопасно опираться на обратные элементы по модулю через малую теорему Ферма. Вместо этого программа вычисляет
$$\frac{n(n-1)\cdots(n-r+1)}{r!}$$
с точным сокращением числителя и знаменателя по gcd в целых числах, а уже потом берет остаток по модулю. Так как \(r\le 29\), этот шаг очень дешев.
Здесь \(d=\lfloor \log_2 10\rfloor=3\). Динамика дает
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$$
Первые конечные разности равны
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$$
Следовательно,
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
Это имеет и прямой комбинаторный смысл:
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
Восемь упорядоченных пар с произведением не больше \(10\) таковы: \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\), а единственная упорядоченная тройка равна \((2,2,2)\). При \(n=10\) получаем
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
то есть ровно контрольное значение.
Сначала строится сжатый список всех различных значений \(\lfloor m/i\rfloor\). Для каждого состояния заранее вычисляются блоки \([\ell,r]\), соответствующее целевое состояние и кратность \(r-\ell+1\). Затем рекурсия прогоняется для длин от \(0\) до \(d\) с использованием двух циклически переиспользуемых слоев DP, а значение в состоянии \(v=m\) сохраняется после каждого шага.
Из полученной последовательности формируются коэффициенты через конечные разности, после чего выполняется вычисление ряда Ньютона в требуемой точке \(n\). Реализации на C++, Python и Java следуют одной и той же математической схеме, поэтому контрольные результаты совпадают.
Число сжатых состояний равно \(S=|\mathcal{V}(m)|=O(\sqrt{m})\). Для состояния \(v\) количество блоков частного равно \(O(\sqrt{v})\), поэтому общий размер предвычисленной таблицы переходов удовлетворяет оценке
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$$
После предвычисления выполнение DP на \(d=\lfloor \log_2 m\rfloor\) слоях требует \(O(Bd)\) времени и \(O(B+S)\) памяти. Таблица конечных разностей и заключительное вычисление биномиальных коэффициентов стоят лишь \(O(d^2)\) и \(O(d)\); здесь это несущественно, поскольку для \(m=10^9\) имеем всего \(d=29\).
نعرّف
$$F(m,n)=\left|\left\{(a_1,\dots,a_n)\in \mathbb{Z}_{>0}^n:\prod_{i=1}^{n} a_i \le m\right\}\right|.$$
المطلوب هو حساب \(F(10^9,10^9)\) بترديد \(1234567891\). وقيم التحقق المعطاة هي
$$F(10,10)=571,\qquad F(10^6,10^6)\equiv 252903833 \pmod{1234567891}.$$
العد المباشر لجميع السلاسل ذات الطول \(10^9\) غير ممكن عمليًا، لذا تعتمد الفكرة على إعادة صياغة شرط حاصل الضرب في صورة يمكن ضغطها ثم تقييمها بكفاءة.
لطول ثابت \(t\) نكتب
$$P_t(v)=F(v,t).$$
عندما يكون \(t=0\) يوجد ترتيب وحيد مقبول، وهو الترتيب الفارغ، ولذلك
$$P_0(v)=1\qquad (v\ge 1).$$
إذا كان \(t\ge 1\)، نختار العامل الأول \(x=a_1\). عندئذ يجب أن يحقق حاصل ضرب العوامل المتبقية
$$a_2a_3\cdots a_t \le \left\lfloor \frac{v}{x}\right\rfloor.$$
ومن ثم نحصل على العلاقة الدقيقة
$$P_t(v)=\sum_{x=1}^{v} P_{t-1}\!\left(\left\lfloor \frac{v}{x}\right\rfloor\right).$$
هذه هي العلاقة الأساسية التي تبني عليها جميع التطبيقات الحساب الفعلي.
لـ \(m\) ثابت نعرّف المجموعة
$$\mathcal{V}(m)=\left\{\left\lfloor \frac{m}{i}\right\rfloor : 1\le i\le m\right\}.$$
هذه المجموعة لا تحتوي إلا على \(O(\sqrt{m})\) قيمة مختلفة. فالقيم الأكبر من \(\sqrt{m}\) لا تظهر إلا عندما يكون \(i\le \sqrt{m}\)، أما القيم الصغيرة فتتجمع في الذيل السفلي، ولذلك \(|\mathcal{V}(m)|\le 2\sqrt{m}\).
والأهم أن الانتقالات تبقى داخل المجموعة نفسها. فإذا كان \(v=\lfloor m/i\rfloor\)، فإن
$$\left\lfloor \frac{v}{x}\right\rfloor=\left\lfloor \frac{\lfloor m/i\rfloor}{x}\right\rfloor=\left\lfloor \frac{m}{ix}\right\rfloor \in \mathcal{V}(m).$$
إذن يكفي تخزين قيم البرمجة الديناميكية على هذه الحالات المضغوطة فقط.
ولقيمة ثابتة \(v\)، فإن \(\lfloor v/x\rfloor\) يبقى ثابتًا على فترات متجاورة. فإذا كان
$$q=\left\lfloor \frac{v}{\ell}\right\rfloor,$$
فإن هذا الخارج نفسه يستمر لكل
$$\ell \le x \le r=\left\lfloor \frac{v}{q}\right\rfloor.$$
ولهذا يمكن كتابة الانتقال على شكل مجموع كتل:
$$P_t(v)=\sum_{[\ell,r]} (r-\ell+1)\,P_{t-1}\!\left(\left\lfloor \frac{v}{\ell}\right\rfloor\right).$$
التنفيذ يحسب هذه الكتل مسبقًا مرة واحدة ثم يعيد استخدامها في كل طبقة من طبقات DP.
خذ أي سلسلة مقبولة واحذف منها كل القيم المساوية لـ \(1\). يتبقى ترتيب جوهري طوله \(r\)، وجميع عناصره لا تقل عن \(2\)، وما زال حاصل الضرب لا يتجاوز \(m\). لذلك
$$2^r \le m,$$
ومن ثم
$$r \le d=\left\lfloor \log_2 m \right\rfloor.$$
ولنرمز بـ \(C_r(m)\) إلى عدد التراتيب المرتبة ذات الطول \(r\) التي كل عنصر فيها \(\ge 2\) وحاصل ضربها \(\le m\). بعد تثبيت هذا الترتيب الجوهري، يصبح تكوين سلسلة بطول \(n\) مجرد اختيار أي \(r\) مواضع من أصل \(n\) لوضع العناصر غير الواحدة، وعدد ذلك يساوي تمامًا \(\binom{n}{r}\). وبالتالي
$$F(m,n)=\sum_{r=0}^{d} C_r(m)\binom{n}{r}.$$
أي أن الجواب، عند تثبيت \(m\)، هو كثيرة حدود في \(n\) درجتها على الأكثر \(d\)، ومكتوبة طبيعيًا في أساس معاملات ثنائية الحد. وعندما \(m=10^9\) نحصل على \(d=29\)، ولذلك يكفي حساب القيم عند \(n=0,1,\dots,29\) فقط.
اكتب \(Q(n)=F(m,n)\). كل كثيرة حدود درجتها على الأكثر \(d\) تملك توسعة نيوتن
$$Q(n)=\sum_{r=0}^{d} \Delta^r Q(0)\binom{n}{r},$$
حيث \(\Delta\) هو مؤثر الفرق الأمامي. وفي هذه المسألة تحديدًا، فإن المعاملات \(\Delta^r Q(0)\) هي نفسها معاملات الأساس الثنائي \(C_r(m)\).
إذًا لا تحتاج البرمجة الديناميكية إلا إلى إنتاج القيم
$$Q(0),Q(1),\dots,Q(d).$$
بعد ذلك تُبنى جدول فروق قصير، ثم تُقيَّم كثيرة الحدود عند القيمة الكبيرة جدًا \(n=10^9\).
العدد \(1234567891\) مودول مركب، ولذلك لا يصح الاعتماد على مقلوبات نمط فيرما لحساب \(\binom{n}{r}\). بدلًا من ذلك، يحسب البرنامج المقدار
$$\frac{n(n-1)\cdots(n-r+1)}{r!}$$
مع اختزال صحيح بين البسط والمقام بواسطة gcd، ثم يأخذ الباقي مودولو \(1234567891\). وبما أن \(r\le 29\)، فهذا الجزء صغير جدًا.
هنا \(d=\lfloor \log_2 10\rfloor=3\). تعطي البرمجة الديناميكية
$$Q(0)=1,\qquad Q(1)=10,\qquad Q(2)=27,\qquad Q(3)=53.$$
أما الفروق الأمامية فهي
$$\Delta Q(0)=9,\qquad \Delta^2 Q(0)=8,\qquad \Delta^3 Q(0)=1.$$
ومن ثم
$$F(10,n)=1+9\binom{n}{1}+8\binom{n}{2}+\binom{n}{3}.$$
ولهذا أيضًا تفسير تعدادي مباشر:
$$C_0(10)=1,\quad C_1(10)=9,\quad C_2(10)=8,\quad C_3(10)=1.$$
الأزواج المرتبة الثمانية التي لا يتجاوز حاصل ضربها \(10\) هي \((2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(4,2),(5,2)\)، أما الثلاثي المرتب الوحيد فهو \((2,2,2)\). وعند \(n=10\) نحصل على
$$F(10,10)=1+9\binom{10}{1}+8\binom{10}{2}+\binom{10}{3}=571,$$
وهو تمامًا مقدار التحقق المذكور.
تبدأ الشيفرة ببناء القائمة المضغوطة للقيم المختلفة \(\lfloor m/i\rfloor\). ثم تسبق لكل حالة بحساب الكتل \([\ell,r]\)، والحالة الهدف المقابلة، وطول الكتلة \(r-\ell+1\). بعد ذلك تُشغَّل العلاقة العودية للأطوال من \(0\) إلى \(d\) باستخدام طبقتين دوارتين فقط من مصفوفات DP، مع تسجيل قيمة الحالة \(v=m\) بعد كل طبقة.
ثم تتحول هذه القيم إلى معاملات فروق أمامية، وفي النهاية تُقيَّم سلسلة نيوتن عند الطول المطلوب \(n\). تطبيقات C++ وPython وJava تتبع التسلسل الرياضي نفسه، ولهذا تتطابق قيم التحقق بينها.
عدد الحالات المضغوطة هو \(S=|\mathcal{V}(m)|=O(\sqrt{m})\). ولكل حالة \(v\) يوجد \(O(\sqrt{v})\) كتلة خارج قسمة، لذا فإن الحجم الكلي لجدول الانتقالات المسبق يحقق
$$B=\sum_{v\in \mathcal{V}(m)} O(\sqrt{v})=O(m^{3/4}).$$
وبالتالي فإن تشغيل البرمجة الديناميكية عبر \(d=\lfloor \log_2 m\rfloor\) طبقات يحتاج إلى \(O(Bd)\) زمنًا بعد مرحلة التمهيد، وإلى \(O(B+S)\) ذاكرة. أما جدول الفروق وتقييم معاملات ثنائية الحد فيكلفان فقط \(O(d^2)\) و\(O(d)\)، وهو أمر مهمل هنا لأن \(d=29\) عندما \(m=10^9\).