Let \(R_{n,m}(x)\) be the remainder when \(x^n\) is divided by \((x-1)^m\). For integers \(0 \le d \lt m \le n\), the quantity of interest is the absolute value of the coefficient of \(x^d\) in that remainder. The real input is enormous, so the solution cannot expand polynomials term by term; it must turn the coefficient into a direct combinatorial formula and then evaluate that formula modulo the prime \(p=999999937\).
The key observation is that the remainder modulo \((x-1)^m\) is exactly the Taylor expansion of \(x^n\) around \(x=1\), truncated after degree \(m-1\).
Since \(x=1+(x-1)\), the binomial theorem gives
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k.$$
When we divide by \((x-1)^m\), every term with \(k \ge m\) is a multiple of \((x-1)^m\). Therefore the unique remainder of degree less than \(m\) is
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k.$$
This already explains why the code never performs polynomial long division: the remainder has a closed form immediately.
Inside one term \((x-1)^k\), the coefficient of \(x^d\) is
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d.$$
So if \(a_d\) denotes the coefficient of \(x^d\) in the remainder, then
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}.$$
The problem asks for \(|a_d|\), not the signed coefficient itself.
Use the standard identity
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}.$$
After substituting \(t=k-d\), the coefficient becomes
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}.$$
Now the whole problem is reduced to one alternating partial sum of binomial coefficients.
For \(0 \le r \lt N\), the identity
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}$$
applies. With \(N=n-d\) and \(r=m-d-1\), we obtain
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}.$$
Hence the absolute value is
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
This closed formula is the central mathematical fact used by the implementation.
The exact coefficient is far too large to build directly, so the computation is done in \(\mathbb{F}_p\) with
$$p=999999937.$$
For a prime modulus, Lucas's theorem says that if
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i,$$
then
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
Each digit-level binomial is small enough to evaluate with the multiplicative formula
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!},$$
and the division by \(v!\) is performed modulo \(p\) using Fermat's little theorem, namely
$$q^{-1}\equiv q^{p-2}\pmod{p} \qquad (q \not\equiv 0 \pmod{p}).$$
So the final answer is
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}.$$
The truncated expansion is
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2.$$
Substituting the values gives
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10.$$
The coefficient of \(x^1\) is \(-24\), so the required absolute value is \(24\).
The closed formula gives exactly the same result:
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
The implementation first handles the invalid range: if \(d \ge m\) or \(m > n\), the desired coefficient is zero. Otherwise it computes the two binomial factors from the closed formula separately modulo \(p\), and then multiplies them together modulo \(p\).
To evaluate a binomial coefficient modulo the prime, the C++, Python, and Java implementations apply Lucas's theorem digit by digit in base \(p\). For each digit pair they form the numerator and denominator multiplicatively, replace division by a modular inverse obtained from fast exponentiation, and accumulate the digit contributions into the full Lucas product.
The C++ implementation also checks the formula on small cases by comparing it with direct coefficient expansion of the truncated remainder, which confirms both the combinatorial identity and the modular computation.
Let \(L=\lfloor \log_p n \rfloor + 1\), the number of base-\(p\) digits. Lucas's theorem reduces each large binomial to \(L\) digit-level binomials. If a digit pair is \((u,v)\), the multiplicative evaluation costs \(O(\min(v,u-v))\) modular multiplications, plus \(O(\log p)\) time for the modular inverse by fast exponentiation. Therefore the overall running time is
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right)$$
for each large binomial, with only \(O(1)\) extra memory. In the actual problem, \(p\) is close to \(10^9\), so the number of base-\(p\) digits is extremely small.
Sei \(R_{n,m}(x)\) der Rest bei der Division von \(x^n\) durch \((x-1)^m\). Für ganze Zahlen \(0 \le d \lt m \le n\) ist der Betrag des Koeffizienten von \(x^d\) in diesem Rest gesucht. Die echten Eingaben sind riesig, daher kann man den Rest nicht symbolisch ausmultiplizieren; stattdessen muss man den Koeffizienten in eine geschlossene kombinatorische Formel überführen und diese modulo der Primzahl \(p=999999937\) auswerten.
Die zentrale Beobachtung ist, dass der Rest modulo \((x-1)^m\) genau der bei Grad \(m-1\) abgeschnittenen Taylorentwicklung von \(x^n\) um \(x=1\) entspricht.
Aus \(x=1+(x-1)\) und dem binomischen Lehrsatz folgt
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k.$$
Bei der Division durch \((x-1)^m\) sind alle Summanden mit \(k \ge m\) Vielfache von \((x-1)^m\). Deshalb ist der eindeutige Rest vom Grad kleiner als \(m\)
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k.$$
Damit ist sofort klar, warum das Programm keine klassische Polynomdivision benötigt: Der Rest liegt bereits in geschlossener Form vor.
Im Summanden \((x-1)^k\) ist der Koeffizient von \(x^d\)
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d.$$
Bezeichnet \(a_d\) den Koeffizienten von \(x^d\) im Rest, dann gilt also
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}.$$
Gefragt ist am Ende \(|a_d|\), also der Betrag dieses möglicherweise negativen Koeffizienten.
Mit der Standardidentität
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}$$
und der Substitution \(t=k-d\) wird daraus
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}.$$
Damit bleibt nur noch eine partielle alternierende Summe von Binomialkoeffizienten übrig.
Für \(0 \le r \lt N\) gilt die Identität
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}.$$
Setzt man \(N=n-d\) und \(r=m-d-1\), erhält man
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}.$$
Für den gesuchten Betrag folgt daher
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
Genau diese Formel ist das mathematische Herzstück der Implementierung.
Der exakte Koeffizient ist viel zu groß für direkte Ganzzahlarithmetik. Deshalb wird in \(\mathbb{F}_p\) mit
$$p=999999937$$
gerechnet. Für eine Primzahl als Modulus sagt der Satz von Lucas: Wenn
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i,$$
dann gilt
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
Jeder ziffernweise Binomialkoeffizient wird mit der multiplikativen Formel
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!}$$
berechnet; die Division durch \(v!\) erfolgt modulo \(p\) über Fermats kleinen Satz, also
$$q^{-1}\equiv q^{p-2}\pmod{p}\qquad (q \not\equiv 0 \pmod{p}).$$
Damit lautet die Endformel für das Ergebnis
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}.$$
Die abgeschnittene Entwicklung lautet
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2.$$
Einsetzen ergibt
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10.$$
Der Koeffizient von \(x\) ist also \(-24\), sein Betrag folglich \(24\).
Die geschlossene Formel liefert denselben Wert:
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
Die Implementierung behandelt zuerst den ungültigen Bereich: Falls \(d \ge m\) oder \(m > n\), ist der gesuchte Koeffizient gleich null. Andernfalls werden die beiden Binomialfaktoren aus der geschlossenen Formel separat modulo \(p\) berechnet und anschließend modulo \(p\) miteinander multipliziert.
Zur Berechnung eines Binomialkoeffizienten modulo der Primzahl verwenden die C++-, Python- und Java-Implementierungen den Satz von Lucas ziffernweise zur Basis \(p\). Für jedes Ziffernpaar wird Zähler und Nenner multiplikativ aufgebaut, die Division durch einen modularen Inversen per schneller Potenzierung ersetzt und das Ergebnis in das Lucas-Produkt eingearbeitet.
Die C++-Implementierung überprüft die Formel zusätzlich an kleinen Beispielen durch direkten Koeffizientenvergleich der abgeschnittenen Restentwicklung; damit werden sowohl die kombinatorische Identität als auch die modulare Rechnung abgesichert.
Sei \(L=\lfloor \log_p n \rfloor + 1\) die Anzahl der Ziffern zur Basis \(p\). Lucas zerlegt jeden großen Binomialkoeffizienten in \(L\) ziffernweise Teilprobleme. Für ein Ziffernpaar \((u,v)\) kostet die multiplikative Auswertung \(O(\min(v,u-v))\) modulare Multiplikationen, dazu \(O(\log p)\) Zeit für den modularen Inversen per schneller Potenzierung. Insgesamt ergibt das
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right)$$
pro großem Binomialkoeffizienten bei nur \(O(1)\) zusätzlichem Speicher. Da \(p\) in dieser Aufgabe fast \(10^9\) groß ist, hat die Lucas-Zerlegung in der Praxis nur sehr wenige Ziffern.
\(R_{n,m}(x)\), \(x^n\)'in \((x-1)^m\)'e bölünmesinden kalan polinom olsun. \(0 \le d \lt m \le n\) için istenen değer, bu kalandaki \(x^d\) katsayısının mutlak değeridir. Gerçek giriş çok büyük olduğundan kalanı açıkça üretmek mümkün değildir; çözüm, katsayıyı kapalı bir kombinatorik formüle indirger ve bu formülü \(p=999999937\) asalına göre hesaplar.
Ana gözlem şudur: \((x-1)^m\) modundaki kalan, \(x^n\)'in \(x=1\) etrafındaki Taylor açılımının \(m-1\). derecede kesilmiş halidir.
\(x=1+(x-1)\) olduğundan binom açılımı
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k$$
şeklindedir. \((x-1)^m\)'e bölündüğünde \(k \ge m\) olan tüm terimler \((x-1)^m\)'in katıdır. Bu nedenle derecesi \(m\)'den küçük tek kalan
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k$$
olur. Böylece kodun neden doğrudan polinom bölmesi yapmadığı da açıklanmış olur.
Tek bir \((x-1)^k\) teriminde \(x^d\)'nin katsayısı
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d$$
olduğundan, kalandaki \(x^d\) katsayısı \(a_d\) için
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}$$
elde edilir. Sorunun istediği şey işaretli değer değil, \(|a_d|\) mutlak değeridir.
Standart özdeşlik
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}$$
kullanılırsa ve \(t=k-d\) dönüşümü yapılırsa
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}$$
elde edilir. Böylece problem tek bir alternanslı binom toplamına indirgenmiş olur.
\(0 \le r \lt N\) için
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}$$
özdeşliği geçerlidir. Burada \(N=n-d\) ve \(r=m-d-1\) seçilirse
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}$$
bulunur. Dolayısıyla aranan mutlak değer
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
Uygulamanın kullandığı temel matematiksel sonuç tam olarak budur.
Tam katsayı doğrudan üretilemeyecek kadar büyüktür; bu yüzden hesap
$$p=999999937$$
asallısı altında \(\mathbb{F}_p\) içinde yapılır. Lucas teoremine göre, eğer
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i$$
ise
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
Her basamaktaki binom katsayısı
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!}$$
çarpımsal formülüyle hesaplanır; \(v!\) ile bölme ise Fermat'nın küçük teoremi sayesinde
$$q^{-1}\equiv q^{p-2}\pmod{p}\qquad (q \not\equiv 0 \pmod{p})$$
şeklindeki modüler tersle yapılır. Sonuç olarak cevap
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}$$
olur.
Kesilmiş açılım
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2$$
şeklindedir. Sayıları yerine koyarsak
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10$$
elde edilir. Burada \(x^1\) katsayısı \(-24\) olduğundan istenen mutlak değer \(24\)'tür.
Kapalı formül de aynı sonucu verir:
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
Uygulama önce geçersiz aralığı kontrol eder: \(d \ge m\) veya \(m > n\) ise istenen katsayı sıfırdır. Aksi halde kapalı formüldeki iki binom katsayısı ayrı ayrı \(p\) modunda hesaplanır ve son adımda çarpılıp tekrar \(p\) moduna indirgenir.
C++, Python ve Java uygulamaları büyük binom katsayılarını hesaplamak için Lucas teoremini taban \(p\) basamakları üzerinde uygular. Her basamak çifti için pay ve payda çarpımsal olarak kurulur, bölme işlemi hızlı üs alma ile elde edilen modüler ters üzerinden yapılır ve basamak katkıları çarpılarak genel sonuç elde edilir.
C++ uygulaması ayrıca küçük örneklerde kapalı formülü doğrudan katsayı açılımıyla karşılaştıran denetimler içerir; böylece hem kombinatorik özdeşlik hem de modüler hesap doğrulanmış olur.
\(L=\lfloor \log_p n \rfloor + 1\), yani taban \(p\) basamak sayısı olsun. Lucas teoremi her büyük binom katsayısını \(L\) adet basamak düzeyi alt probleme ayırır. Bir \((u,v)\) basamak çifti için çarpımsal hesap \(O(\min(v,u-v))\) modüler çarpım, modüler ters hesabı ise hızlı üs alma ile \(O(\log p)\) zaman ister. Dolayısıyla bir büyük binom katsayısı için toplam süre
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right)$$
olur ve ek bellek yalnızca \(O(1)\)'dir. Bu problemde \(p\) yaklaşık \(10^9\) büyüklüğünde olduğundan taban \(p\) basamak sayısı pratikte çok küçüktür.
Sea \(R_{n,m}(x)\) el resto de dividir \(x^n\) entre \((x-1)^m\). Para enteros \(0 \le d \lt m \le n\), se pide el valor absoluto del coeficiente de \(x^d\) en ese resto. Como la entrada real es gigantesca, no se puede expandir el polinomio de forma directa; la solución transforma el coeficiente en una fórmula combinatoria cerrada y luego la evalúa módulo el primo \(p=999999937\).
La observación decisiva es que el resto módulo \((x-1)^m\) coincide con la expansión de Taylor de \(x^n\) alrededor de \(x=1\), truncada después del grado \(m-1\).
Como \(x=1+(x-1)\), el teorema binomial da
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k.$$
Al dividir por \((x-1)^m\), todos los términos con \(k \ge m\) son múltiplos de \((x-1)^m\). Por tanto, el resto único de grado menor que \(m\) es
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k.$$
Esto explica por qué la implementación no hace división polinómica explícita: el resto ya aparece en forma cerrada.
En un término \((x-1)^k\), el coeficiente de \(x^d\) es
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d.$$
Si \(a_d\) denota el coeficiente de \(x^d\) en el resto, entonces
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}.$$
El problema pide \(|a_d|\), no el coeficiente con signo.
Usamos la identidad
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}.$$
Con el cambio \(t=k-d\), se obtiene
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}.$$
Así, toda la dificultad queda concentrada en una suma parcial alternante de coeficientes binomiales.
Para \(0 \le r \lt N\), vale la identidad
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}.$$
Aplicándola con \(N=n-d\) y \(r=m-d-1\), resulta
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}.$$
Por lo tanto, el valor absoluto buscado es
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
Esta es exactamente la fórmula combinatoria usada por la implementación.
El coeficiente exacto es demasiado grande para construirse directamente, así que el cálculo se hace en \(\mathbb{F}_p\) con
$$p=999999937.$$
Si
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i,$$
el teorema de Lucas afirma que
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
Cada binomial de un dígito se evalúa con la fórmula multiplicativa
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!},$$
y la división por \(v!\) se sustituye por el inverso modular obtenido mediante el pequeño teorema de Fermat:
$$q^{-1}\equiv q^{p-2}\pmod{p}\qquad (q \not\equiv 0 \pmod{p}).$$
En consecuencia, la respuesta final es
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}.$$
La expansión truncada es
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2.$$
Sustituyendo valores se obtiene
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10.$$
El coeficiente de \(x\) es \(-24\), así que el valor absoluto pedido es \(24\).
La fórmula cerrada produce exactamente lo mismo:
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
La implementación primero maneja el rango inválido: si \(d \ge m\) o \(m > n\), el coeficiente buscado es cero. En caso contrario, calcula por separado los dos factores binomiales de la fórmula cerrada módulo \(p\) y al final los multiplica también módulo \(p\).
Para evaluar un binomial módulo el primo, las implementaciones en C++, Python y Java aplican el teorema de Lucas dígito por dígito en base \(p\). En cada par de dígitos construyen numerador y denominador de forma multiplicativa, reemplazan la división por un inverso modular obtenido mediante exponenciación rápida y acumulan la contribución de cada dígito al producto final.
La implementación en C++ además contrasta la fórmula con una expansión directa del resto en ejemplos pequeños, lo que confirma tanto la identidad combinatoria como el cálculo modular.
Sea \(L=\lfloor \log_p n \rfloor + 1\) el número de dígitos en base \(p\). El teorema de Lucas reduce cada binomial grande a \(L\) binomiales de un solo dígito. Si un par de dígitos es \((u,v)\), su evaluación multiplicativa cuesta \(O(\min(v,u-v))\) multiplicaciones modulares, más \(O(\log p)\) tiempo para el inverso modular mediante exponenciación rápida. Por ello, el coste total es
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right)$$
por cada binomial grande, con solo \(O(1)\) memoria adicional. Como \(p\) es cercano a \(10^9\), en esta tarea el número de dígitos en base \(p\) es muy pequeño.
设 \(R_{n,m}(x)\) 是 \(x^n\) 除以 \((x-1)^m\) 时得到的余式。对整数 \(0 \le d \lt m \le n\)，题目要求的是这个余式中 \(x^d\) 项系数的绝对值。真正的输入规模极大，因此不能把余式完整展开后再读出系数；必须先把问题化成封闭的组合恒等式，再在素数 \(p=999999937\) 下完成计算。
核心想法是：模 \((x-1)^m\) 的余式，正好就是 \(x^n\) 在 \(x=1\) 附近的 Taylor 展开中保留到 \(m-1\) 次项的那一段。
因为 \(x=1+(x-1)\)，由二项式定理可得
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k.$$
当我们对 \((x-1)^m\) 取模时，所有 \(k \ge m\) 的项都含有因子 \((x-1)^m\)，因此都会落入商的部分。于是次数小于 \(m\) 的唯一余式就是
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k.$$
这一步已经说明，程序完全不需要做传统的多项式长除法，因为余式本身已经有了直接的闭式表达。
对单个项 \((x-1)^k\) 来说，\(x^d\) 的系数为
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d.$$
如果把余式中 \(x^d\) 的系数记为 \(a_d\)，那么
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}.$$
题目真正要求的是 \(|a_d|\)，也就是这个系数的绝对值，而不是带符号的原值。
使用恒等式
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}$$
再令 \(t=k-d\)，上式就化为
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}.$$
现在问题的难点已经从“多项式余式”变成了“一个交错的部分二项式和”。这一步是整个推导中最重要的整理。
对 \(0 \le r \lt N\)，有经典恒等式
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}.$$
把 \(N=n-d\)、\(r=m-d-1\) 代入，就得到
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}.$$
因此题目要求的绝对值恰好是
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
这就是三个实现共同依赖的核心封闭公式。也就是说，余式系数问题最终被完全转化成了两个大二项式系数的乘积。
虽然封闭公式已经得到，但它的精确值依然大得无法直接构造，所以必须转到模运算。这里使用的模数是
$$p=999999937.$$
若把任意整数 \(N\) 与 \(K\) 写成 \(p\) 进制展开
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i,$$
那么 Lucas 定理告诉我们
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
因此，大二项式系数可以拆成若干个“小位数二项式系数”的乘积。对于每一位上的 \(\binom{u}{v}\)，实现采用乘法形式
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!}$$
来构造分子和分母，然后用 Fermat 小定理把除法变成模逆：
$$q^{-1}\equiv q^{p-2}\pmod{p}\qquad (q \not\equiv 0 \pmod{p}).$$
最后分别算出 \(\binom{n}{d}\) 与 \(\binom{n-d-1}{m-d-1}\) 在模 \(p\) 下的值，再把它们相乘，即可得到最终答案：
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}.$$
先写出截断余式：
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2.$$
代入具体数值后得到
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10.$$
所以 \(x^1\) 的系数是 \(-24\)，其绝对值为 \(24\)。
用封闭公式核对：
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
两种做法完全一致，这个小例子也很好地说明了符号来自交错和，而绝对值正好就是两个组合数的乘积。
实现首先处理无效参数：如果 \(d \ge m\) 或 \(m > n\)，那么所求系数直接为零。否则，它按照闭式公式分别计算两个大二项式系数在模 \(p\) 下的值，最后再做一次模乘。
C++、Python 和 Java 三个实现都采用相同的结构。它们先把大整数按 \(p\) 进制逐位拆开，利用 Lucas 定理把整体二项式系数写成各位小二项式系数的乘积。对于每一位上的小二项式系数，代码通过连乘构造分子与分母，再用快速幂求模逆，从而完成除法。
其中 C++ 实现还额外加入了小规模自检：一方面用闭式公式计算小样例，另一方面直接把截断余式展开并读取系数，两者逐项比对，确认推导公式和模运算过程都没有偏差。
记 \(L=\lfloor \log_p n \rfloor + 1\) 为 \(n\) 的 \(p\) 进制位数。Lucas 定理会把每个大二项式系数分解成 \(L\) 个单独的位级二项式系数。若某一位对应 \((u,v)\)，那么用乘法公式计算这一位需要 \(O(\min(v,u-v))\) 次模乘，再加上 \(O(\log p)\) 的快速幂时间来求模逆。因此单个大二项式系数的总时间为
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right),$$
额外空间仅为 \(O(1)\)。由于本题的模数 \(p\) 已经接近 \(10^9\)，所以 \(10^{13}\) 量级的输入在 \(p\) 进制下只有极少数位，Lucas 分解在实际运行中非常短。
Пусть \(R_{n,m}(x)\) обозначает остаток от деления \(x^n\) на \((x-1)^m\). Для целых \(0 \le d \lt m \le n\) требуется найти абсолютную величину коэффициента при \(x^d\) в этом остатке. При реальных параметрах входа прямое раскрытие полинома невозможно, поэтому решение сначала выводит замкнутую комбинаторную формулу для нужного коэффициента, а затем вычисляет её по модулю простого числа \(p=999999937\).
Главное наблюдение состоит в том, что остаток по модулю \((x-1)^m\) совпадает с усечённым рядом Тейлора для \(x^n\) в точке \(x=1\).
Поскольку \(x=1+(x-1)\), биномиальная формула даёт
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k.$$
При делении на \((x-1)^m\) все слагаемые с \(k \ge m\) уже содержат множитель \((x-1)^m\), поэтому уходят в частное. Следовательно, единственный остаток степени меньше \(m\) равен
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k.$$
Именно поэтому программе не нужна обычная полиномиальная делёжка: остаток сразу выражается в явном виде.
В одном слагаемом \((x-1)^k\) коэффициент при \(x^d\) равен
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d.$$
Если обозначить коэффициент при \(x^d\) в остатке через \(a_d\), то
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}.$$
В задаче нужен не знак этого коэффициента, а его модуль \(|a_d|\).
Используем тождество
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}.$$
После замены \(t=k-d\) получаем
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}.$$
Теперь задача сводится к вычислению частичной знакопеременной суммы биномиальных коэффициентов.
Для \(0 \le r \lt N\) выполняется формула
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}.$$
Подставляя \(N=n-d\) и \(r=m-d-1\), получаем
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}.$$
Следовательно, искомый модуль равен
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
Это и есть основная формула, на которой строятся все три реализации.
Точное значение коэффициента слишком велико, поэтому вычисление ведётся в поле \(\mathbb{F}_p\), где
$$p=999999937.$$
Если представить числа \(N\) и \(K\) в системе счисления по основанию \(p\),
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i,$$
то теорема Лукаса утверждает:
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
Каждый «цифровой» биномиальный коэффициент считается по мультипликативной формуле
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!},$$
а деление на \(v!\) заменяется умножением на модульный обратный, полученный из малой теоремы Ферма:
$$q^{-1}\equiv q^{p-2}\pmod{p}\qquad (q \not\equiv 0 \pmod{p}).$$
Итак, окончательный ответ вычисляется как
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}.$$
Усечённое разложение имеет вид
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2.$$
Подставляя значения, получаем
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10.$$
Коэффициент при \(x\) равен \(-24\), значит его абсолютная величина равна \(24\).
Замкнутая формула даёт тот же результат:
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
Сначала реализация обрабатывает недопустимую область параметров: если \(d \ge m\) или \(m > n\), искомый коэффициент равен нулю. Во всех остальных случаях отдельно вычисляются два биномиальных множителя из замкнутой формулы по модулю \(p\), после чего они перемножаются по тому же модулю.
Реализации на C++, Python и Java используют одну и ту же схему: большой биномиальный коэффициент раскладывается по теореме Лукаса на произведение коэффициентов по цифрам в системе счисления с основанием \(p\). Для каждой пары цифр числитель и знаменатель строятся последовательным перемножением, а деление заменяется модульным обратным, найденным быстрым возведением в степень.
В реализации на C++ дополнительно есть проверки на малых примерах: замкнутая формула сравнивается с прямым раскрытием усечённого остатка, что подтверждает и саму комбинаторную формулу, и корректность вычислений по модулю.
Пусть \(L=\lfloor \log_p n \rfloor + 1\) — число цифр числа \(n\) в записи по основанию \(p\). Теорема Лукаса сводит каждый большой биномиальный коэффициент к \(L\) маленьким коэффициентам по отдельным цифрам. Для пары цифр \((u,v)\) мультипликативное вычисление требует \(O(\min(v,u-v))\) модульных умножений, а нахождение обратного элемента быстрым возведением в степень занимает \(O(\log p)\) времени. Значит, общая сложность для одного большого биномиального коэффициента равна
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right),$$
а дополнительная память составляет всего \(O(1)\). Поскольку в этой задаче \(p\) почти равно \(10^9\), число цифр в записи по основанию \(p\) очень мало, и метод работает крайне быстро.
ليكن \(R_{n,m}(x)\) هو باقي قسمة \(x^n\) على \((x-1)^m\). عندما تكون \(0 \le d \lt m \le n\)، فالمطلوب هو القيمة المطلقة لمعامل \(x^d\) داخل هذا الباقي. بما أن قيم الإدخال الحقيقية ضخمة جدًا، فلا يمكن توسيع كثير الحدود مباشرة ثم قراءة المعامل؛ لذلك يحول الحل المسألة إلى صيغة توافقية مغلقة ثم يحسبها بترديد العدد الأولي \(p=999999937\).
الفكرة الأساسية هي أن الباقي modulo \((x-1)^m\) يساوي بالضبط متسلسلة Taylor لـ \(x^n\) حول \(x=1\) بعد قطعها عند الدرجة \(m-1\).
بما أن \(x=1+(x-1)\)، فإن نظرية ذي الحدين تعطي
$$x^n=(1+(x-1))^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k.$$
وعند القسمة على \((x-1)^m\)، فإن كل حد يحقق \(k \ge m\) يحتوي أصلًا على العامل \((x-1)^m\)، ولذلك يختفي داخل خارج القسمة. ومن ثم فإن الباقي الوحيد الذي درجته أصغر من \(m\) هو
$$R_{n,m}(x)=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k.$$
هذه الخطوة تشرح مباشرة لماذا لا تحتاج الخوارزمية إلى تنفيذ قسمة كثيرة حدود حرفية: فالباقي نفسه معروف بصيغة مغلقة منذ البداية.
في الحد الواحد \((x-1)^k\)، يكون معامل \(x^d\) مساويًا لـ
$$[x^d](x-1)^k=\binom{k}{d}(-1)^{k-d},\qquad k \ge d.$$
إذا رمزنا لمعامل \(x^d\) في الباقي بالرمز \(a_d\)، فإن
$$a_d=\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}.$$
لكن المطلوب في المسألة ليس هذا المعامل بإشارته، بل القيمة المطلقة \(|a_d|\).
نستعمل الهوية القياسية
$$\binom{n}{k}\binom{k}{d}=\binom{n}{d}\binom{n-d}{k-d}.$$
ثم نضع \(t=k-d\)، فنحصل على
$$a_d=\binom{n}{d}\sum_{t=0}^{m-d-1}(-1)^t\binom{n-d}{t}.$$
وبذلك تنتقل المسألة من شكلها الأصلي المتعلق ببواقي كثيرات الحدود إلى مجموع ثنائي متناوب يمكن تبسيطه مباشرة.
لأي \(0 \le r \lt N\) لدينا الهوية
$$\sum_{t=0}^{r}(-1)^t\binom{N}{t}=(-1)^r\binom{N-1}{r}.$$
وبالتعويض بـ \(N=n-d\) و \(r=m-d-1\) ينتج
$$a_d=(-1)^{m-d-1}\binom{n}{d}\binom{n-d-1}{m-d-1}.$$
إذن القيمة المطلقة المطلوبة هي
$$\boxed{|a_d|=\binom{n}{d}\binom{n-d-1}{m-d-1}.}$$
هذه هي الصيغة الرياضية الجوهرية التي تعتمد عليها جميع التطبيقات.
حتى بعد الوصول إلى الصيغة المغلقة، يبقى المقدار الحقيقي هائلًا جدًا، لذلك يُجرى الحساب داخل الحقل \(\mathbb{F}_p\) حيث
$$p=999999937.$$
إذا كتبنا
$$N=\sum_i N_i p^i,\qquad K=\sum_i K_i p^i,$$
فإن مبرهنة Lucas تعطي
$$\binom{N}{K}\equiv \prod_i \binom{N_i}{K_i}\pmod{p}.$$
وهكذا ينقسم كل معامل ثنائي ضخم إلى حاصل ضرب معاملات ثنائية صغيرة على مستوى الأرقام. ولكل معامل رقمي \(\binom{u}{v}\)، تستخدم الخوارزمية الصيغة الضربية
$$\binom{u}{v}=\frac{u(u-1)\cdots(u-v+1)}{v!},$$
ثم تستبدل القسمة على \(v!\) بمعكوس معياري يُحسب من خلال مبرهنة فيرما الصغرى:
$$q^{-1}\equiv q^{p-2}\pmod{p}\qquad (q \not\equiv 0 \pmod{p}).$$
وفي النهاية نحسب معاملي \(\binom{n}{d}\) و \(\binom{n-d-1}{m-d-1}\) modulo \(p\) ثم نضربهما، فنحصل على
$$|a_d| \bmod p \equiv \binom{n}{d}\binom{n-d-1}{m-d-1}\pmod{p}.$$
التوسيع المقطوع هو
$$R_{6,3}(x)=\binom{6}{0}+\binom{6}{1}(x-1)+\binom{6}{2}(x-1)^2.$$
وبالتعويض نحصل على
$$R_{6,3}(x)=1+6(x-1)+15(x-1)^2=15x^2-24x+10.$$
إذن معامل \(x\) يساوي \(-24\)، وبالتالي فقيمته المطلقة هي \(24\).
أما الصيغة المغلقة فتعطي النتيجة نفسها تمامًا:
$$\binom{6}{1}\binom{6-1-1}{3-1-1}=\binom{6}{1}\binom{4}{1}=6\cdot 4=24.$$
تبدأ الخوارزمية بمعالجة المجال غير الصالح: إذا كان \(d \ge m\) أو \(m > n\)، فالمعامل المطلوب يساوي صفرًا. في غير ذلك، تحسب العاملين الثنائيين في الصيغة المغلقة كلًا على حدة modulo \(p\)، ثم تضرب النتيجتين في النهاية مع أخذ الترديد نفسه.
تتبع تطبيقات C++ وPython وJava البنية نفسها. فهي تفكك الأعداد الكبيرة إلى أرقام في الأساس \(p\)، ثم تطبق مبرهنة Lucas رقمًا رقمًا. عند كل رقم، يُبنى البسط والمقام بطريقة ضربية، ثم تتحول القسمة إلى ضرب في المعكوس المعياري المحسوب بالرفع السريع للأس.
ويضيف تنفيذ C++ أيضًا فحوصًا صغيرة الحجم تقارن الصيغة المغلقة مع التوسيع المباشر للباقي المقطوع، مما يؤكد صحة الاشتقاق الرياضي وصحة الحساب المعياري معًا.
لنرمز بـ \(L=\lfloor \log_p n \rfloor + 1\) إلى عدد الأرقام في تمثيل \(n\) بالأساس \(p\). عندئذٍ تختزل مبرهنة Lucas كل معامل ثنائي كبير إلى \(L\) معاملات رقمية صغيرة. وإذا كانت إحدى هذه الأزواج الرقمية هي \((u,v)\)، فإن الحساب الضربي يحتاج إلى \(O(\min(v,u-v))\) عملية ضرب معيارية، إضافة إلى \(O(\log p)\) زمنًا لحساب المعكوس المعياري بواسطة الرفع السريع للأس. لذلك يكون الزمن الكلي لكل معامل ثنائي كبير
$$O\left(\sum_{i=0}^{L-1}\min(K_i,N_i-K_i)+L\log p\right),$$
بينما تبقى الذاكرة الإضافية عند \(O(1)\) فقط. وبما أن \(p\) في هذه المسألة قريب جدًا من \(10^9\)، فإن عدد الأرقام في الأساس \(p\) صغير جدًا عمليًا، ولذلك تكون الطريقة سريعة للغاية.