The sequence \(a(n)\) is defined by
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),$$
together with the boundary rule
$$a(n)=1\qquad(n<0).$$
The problem states that every term can be written in the form
$$a(n)=\frac{A(n)e+B(n)}{n!},$$
where \(A(n)\) and \(B(n)\) are integers, and asks for
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777}.$$
The modulus factors as
$$77{,}777{,}777=7\cdot 11\cdot 73\cdot 101\cdot 137.$$
1) Split the infinite sum into a finite part plus an \(e\)-tail.
For fixed \(n\ge 0\), the terms with \(i\le n\) refer to already-defined values \(a(n-i)\), while the terms with \(i>n\) hit the boundary region \(n-i<0\), where \(a(n-i)=1\). Therefore
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac{1}{i!}.$$
Using \(e=\sum_{i=0}^{\infty}1/i!\), the tail becomes
$$\sum_{i=n+1}^{\infty}\frac{1}{i!}=e-\sum_{k=0}^{n}\frac{1}{k!}.$$
So the recurrence is really an inhomogeneous linear relation with one \(e\)-term and one rational term.
2) Insert the decomposition \(a(n)=\frac{A(n)e+B(n)}{n!}\).
Write \(A_n=A(n)\), \(B_n=B(n)\). For \(k=n-i\), the finite part becomes
$$\sum_{i=1}^{n}\frac{a(n-i)}{i!} =\sum_{k=0}^{n-1}\frac{A_k e+B_k}{k!(n-k)!}.$$
Multiply the whole identity by \(n!\):
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}.$$
Now the coefficient of \(e\) and the constant part must match separately.
3) This gives two exact integer recurrences.
Comparing the coefficient of \(e\):
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k.$$
Comparing the constant term:
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
These are exactly the two formulas implemented in the checkpoint routine compute_exact_ab.
4) Small values show the pattern.
From the recurrences:
$$A_0=1,\qquad B_0=-1,$$
$$A_1=2,\qquad B_1=-3,$$
$$A_2=7,\qquad B_2=-12.$$
So
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!},$$
which matches the problem statement. The code also checks the much larger checkpoint
$$A_{10}=328161643,\qquad B_{10}=-652694486.$$
5) The target \(A_n+B_n\) collapses to a much simpler expression.
Define
$$C_n=A_n+B_n.$$
Add the two recurrences:
$$C_n=n!-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}C_k.$$
Now use the induction hypothesis \(C_k=k!-A_k\). Then
$$\sum_{k=0}^{n-1}\binom{n}{k}C_k =\sum_{k=0}^{n-1}\frac{n!}{(n-k)!}-\sum_{k=0}^{n-1}\binom{n}{k}A_k =\sum_{j=1}^{n}\frac{n!}{j!}-\sum_{k=0}^{n-1}\binom{n}{k}A_k.$$
The two factorial sums cancel, leaving
$$C_n=-\sum_{k=0}^{n-1}\binom{n}{k}A_k=n!-A_n.$$
So the quantity asked by the problem is
$$A_n+B_n=n!-A_n.$$
6) Modulo a prime \(p\), the factorial term disappears after \(n\ge p\).
For each prime factor \(p\in\{7,11,73,101,137\}\), Wilson-style reasoning is not even needed: once \(n\ge p\), the product \(n!\) contains \(p\), hence
$$n!\equiv 0\pmod p.$$
Therefore, for large \(n\),
$$A_n+B_n\equiv -A_n\pmod p.$$
The code keeps the unified formula
$$r_p(n)\equiv n!-A_{n'}\pmod p,$$
which also handles the tiny case \(n<p\).
7) The key compression is eventual periodicity modulo each prime.
The implementation exploits the modular fact that, for each prime \(p\), the sequence \(A_n\bmod p\) becomes periodic from index \(p\) onward with period
$$\pi_p=p(p-1).$$
So instead of working at \(n=10^9\), the code reduces the index to
$$n'= \begin{cases} n, & n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr), & n\ge p. \end{cases}$$
This is the entire reason the huge input becomes easy. The program also spot-checks this periodicity numerically for each prime factor on one full band of sample offsets.
8) Computing \(A_n \bmod p\) up to the reduced index is straightforward.
For a fixed prime \(p\), the code computes all values
$$A_0,A_1,\dots,A_{n'}\pmod p$$
sequentially from the recurrence
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p.$$
It keeps one rolling row of Pascal's triangle in the array comb, updating the binomial coefficients in place from right to left. At the same time it updates \(n!\bmod p\), which instantly becomes \(0\) once \(n\ge p\).
9) Recombine the five prime residues by CRT.
For \(n=10^9\), the per-prime residues found by the code are
$$r_7=1,\qquad r_{11}=3,\qquad r_{73}=66,\qquad r_{101}=44,\qquad r_{137}=117.$$
The Chinese remainder theorem then reconstructs the unique residue modulo
$$M=77{,}777{,}777.$$
1) For each prime factor \(p\), reduce \(n\) to \(n'\) using the period \(p(p-1)\) after index \(p\).
2) Compute \(A_0,\dots,A_{n'}\pmod p\) by the binomial-convolution recurrence.
3) Return the prime residue \(r_p(n)\equiv n!-A_{n'}\pmod p\).
4) Combine the five residues with the Chinese remainder theorem.
For a fixed prime \(p\), the reduced index satisfies \(n'<p^2\), and the direct convolution computes each \(A_n\) by summing over all smaller \(k\). So the cost per prime is
$$O((n')^2),$$
which is still tiny here because the largest reduced index is only on the order of \(10^4\). The memory cost is
$$O(n').$$
Since there are only five prime factors, the whole computation is comfortably fast.
The code verifies
$$A_{10}=328161643,\qquad B_{10}=-652694486,$$
and also checks for \(0\le n\le 12\) that the modular solver agrees with the exact integer recurrence.
After CRT recombination, the final answer is
$$\boxed{15955822}.$$
Die Folge \(a(n)\) ist durch
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),\qquad a(n)=1\ (n<0)$$
gegeben. Laut Aufgabe existieren ganze Zahlen \(A(n)\), \(B(n)\) mit
$$a(n)=\frac{A(n)e+B(n)}{n!}.$$
Gesucht ist
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777},$$
wobei
$$77{,}777{,}777=7\cdot11\cdot73\cdot101\cdot137.$$
1) Die unendliche Summe zerfaellt in einen endlichen Teil und einen \(e\)-Rest.
Fuer \(i>n\) liegt \(n-i<0\), also ist \(a(n-i)=1\). Daher
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac1{i!} =\sum_{i=1}^{n}\frac{a(n-i)}{i!}+e-\sum_{k=0}^{n}\frac1{k!}.$$
2) Setze die Darstellung \((A_ne+B_n)/n!\) ein.
Nach Multiplikation mit \(n!\) erhaelt man
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}.$$
Nun werden \(e\)-Koeffizient und konstanter Anteil getrennt verglichen.
3) Exakte Rekurrenzen fuer \(A_n\) und \(B_n\).
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k,$$
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
Genau diese beiden Formeln nutzt der Checkpoint-Code.
4) Kleine Werte.
$$A_0=1,\ B_0=-1,\qquad A_1=2,\ B_1=-3,\qquad A_2=7,\ B_2=-12.$$
Damit folgen
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!},$$
wie in der Aufgabenstellung. Ausserdem prueft das Programm
$$A_{10}=328161643,\qquad B_{10}=-652694486.$$
5) Das Ziel \(A_n+B_n\) vereinfacht zu \(n!-A_n\).
Mit \(C_n=A_n+B_n\) und Induktion ueber \(n\) ergibt sich
$$C_n=n!-A_n.$$
Damit muss man am Ende gar nicht beide Folgen separat modulo grossem Modul verfolgen; \(A_n\) genuegt.
6) Modulo einer Primzahl \(p\) verschwindet \(n!\) ab \(n\ge p\).
Dann gilt sofort
$$n!\equiv 0\pmod p,\qquad A_n+B_n\equiv -A_n\pmod p.$$
Der Code verwendet die einheitliche Formel
$$r_p(n)\equiv n!-A_{n'}\pmod p,$$
damit auch der Fall \(n<p\) korrekt behandelt wird.
7) Der entscheidende Trick ist die Periodizitaet modulo \(p\).
Die Implementierung nutzt die Tatsache, dass \(A_n\bmod p\) ab Index \(p\) periodisch mit Periode
$$p(p-1)$$
wird. Deshalb reduziert sie den Index auf
$$n'= \begin{cases} n,& n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr),& n\ge p. \end{cases}$$
Diese Eigenschaft wird im Code fuer jede Primzahl zusaetzlich per Spot-Checks ueber eine volle Periode getestet.
8) Berechnung von \(A_n\bmod p\).
Fuer jedes \(p\) werden die Werte \(A_0,\dots,A_{n'}\) direkt mit
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p$$
aufgebaut. Die Binomialkoeffizienten werden dabei als laufende Pascal-Zeile in einem eindimensionalen Array gepflegt.
9) CRT setzt die Primreste wieder zusammen.
Fuer \(n=10^9\) entstehen die Reste
$$r_7=1,\ r_{11}=3,\ r_{73}=66,\ r_{101}=44,\ r_{137}=117.$$
Durch den chinesischen Restsatz ergibt das den eindeutigen Rest modulo \(77{,}777{,}777\).
1) Reduziere fuer jede Primzahl \(p\) den Index mit der Periode \(p(p-1)\).
2) Berechne \(A_0,\dots,A_{n'}\pmod p\) per Binomial-Faltung.
3) Setze \(r_p(n)\equiv n!-A_{n'}\pmod p\).
4) Kombiniere die fuenf Reste mit CRT.
Da \(n'<p^2\) und jede neue Zeile ueber alle vorherigen \(k\) summiert, kostet eine Primzahlrechnung
$$O((n')^2)$$
Zeit und \(O(n')\) Speicher. Bei den kleinen Primfaktoren ist das problemlos schnell.
Das Programm prueft unter anderem
$$A_{10}=328161643,\qquad B_{10}=-652694486,$$
und vergleicht fuer \(0\le n\le 12\) die modulare Loesung mit der exakten Ganzzahlrekurrenz.
Das Endergebnis lautet
$$\boxed{15955822}.$$
Dizi
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),\qquad a(n)=1\ (n<0)$$
ile tanimlaniyor. Problem, her terimin
$$a(n)=\frac{A(n)e+B(n)}{n!}$$
seklinde yazilabildigini soyluyor ve
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777}$$
degerini istiyor. Mod
$$77{,}777{,}777=7\cdot11\cdot73\cdot101\cdot137$$
oldugu icin cozum asal modlarda ayri ayri kurulup CRT ile birlestiriliyor.
1) Sonsuz toplami sonlu kisim + \(e\) kuyrugu diye ayir.
\(i>n\) oldugunda \(n-i<0\) ve sinir kosulundan \(a(n-i)=1\) gelir. Dolayisiyla
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac1{i!} =\sum_{i=1}^{n}\frac{a(n-i)}{i!}+e-\sum_{k=0}^{n}\frac1{k!}.$$
Boylece problem bir \(e\) katsayisi ve bir sabit terim ayristirmasina donusur.
2) \(a(n)=\frac{A_ne+B_n}{n!}\) ifadesini yerine koy.
Butun ifadeyi \(n!\) ile carpinca
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}$$
elde edilir. Burada \(e\)'nin katsayisi ile sabit kisim ayri ayri esit olmak zorundadir.
3) Kodun kullandigi iki exact recurrence.
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k,$$
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
compute_exact_ab fonksiyonu tam olarak bu iki denklemi uyguluyor.
4) Kucuk ornekler problemi elle gorunur hale getirir.
Ilk degerler
$$A_0=1,\ B_0=-1,\qquad A_1=2,\ B_1=-3,\qquad A_2=7,\ B_2=-12$$
olur. Buradan
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!}$$
cikar; bu problem ifadesindeki orneklerle aynidir. Kod ayrica
$$A_{10}=328161643,\qquad B_{10}=-652694486$$
checkpoint'ini de dogrular.
5) Asil hedef \(A_n+B_n\), aslinda \(n!-A_n\)'ye coker.
$$C_n=A_n+B_n$$
diye tanimlayalim. Iki recurrence toplanip indüksiyon kullanilinca
$$C_n=n!-A_n$$
elde edilir. Yani problem sonunda hem \(A_n\) hem \(B_n\) izlemek zorunda degiliz; \(A_n\) yeterlidir.
6) Asal mod \(p\) icin \(n!\) bir noktadan sonra sifir olur.
Eger \(n\ge p\) ise
$$n!\equiv 0\pmod p$$
ve dolayisiyla
$$A_n+B_n\equiv -A_n\pmod p.$$
Kod bunu tek bir formulle yazar:
$$r_p(n)\equiv n!-A_{n'}\pmod p,$$
boylece \(n<p\) durumu da ayni ifade icinde kalir.
7) Asil hizlandirma: \(A_n\bmod p\) dizisinin periyoda girmesi.
Uygulama, her asal \(p\) icin \(A_n\bmod p\) dizisinin \(p\) indeksinden sonra
$$p(p-1)$$
periyoduna girdigi moduler olgusunu kullaniyor. Bu nedenle dev indeks
$$n'= \begin{cases} n,& n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr),& n\ge p \end{cases}$$
seklinde indirgeniyor. Kod bu periyodu her asal icin ek spot-check'lerle de siniyor.
8) \(A_n\bmod p\) hesaplamasi nasil yapiliyor?
Sabit bir asal \(p\) icin
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p$$
recurrence'i ardarda uygulanir. Binom katsayilari, comb dizisinde Pascal satiri sagdan sola guncellenerek tutulur. Aynı anda \(n!\bmod p\) da guncellenir; \(n\ge p\) oldugu anda bu terim otomatik olarak sifira duser.
9) Son adim CRT ile birlestirmedir.
\(n=10^9\) icin kodun buldugu asal bazli kalintilar
$$r_7=1,\qquad r_{11}=3,\qquad r_{73}=66,\qquad r_{101}=44,\qquad r_{137}=117$$
olur. Bunlar CRT ile tek bir
$$77{,}777{,}777$$
mod kalintisina donusturulur.
1) Her asal carpan \(p\) icin indeksi \(p(p-1)\) periyoduyla kucult.
2) \(A_0,\dots,A_{n'}\pmod p\) degerlerini binom-konvolusyon recurrence'i ile uret.
3) \(r_p(n)\equiv n!-A_{n'}\pmod p\) kalintisini al.
4) Bes asal kalintisini CRT ile birlestir.
Her asal icin \(n'<p^2\) ve her adim onceki tum \(k\)'leri topladigi icin maliyet
$$O((n')^2)$$
zaman,
$$O(n')$$
bellektir. Bu problemde en buyuk indirgenmis indeks bile sadece on binler mertebesindedir; bu yuzden cozum cok hizlidir.
Kod
$$A_{10}=328161643,\qquad B_{10}=-652694486$$
esitligini ve \(0\le n\le 12\) icin moduler/coexact recurrence uyumunu test eder.
Nihai cevap
$$\boxed{15955822}$$
olarak bulunur.
La sucesion viene dada por
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),\qquad a(n)=1\ (n<0).$$
El enunciado afirma que existe una descomposicion
$$a(n)=\frac{A(n)e+B(n)}{n!},$$
con \(A(n),B(n)\) enteros, y pide
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777}.$$
1) Separar la suma infinita en parte finita y cola de \(e\).
Si \(i>n\), entonces \(n-i<0\) y vale la condicion de borde \(a(n-i)=1\). Asi,
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac1{i!} =\sum_{i=1}^{n}\frac{a(n-i)}{i!}+e-\sum_{k=0}^{n}\frac1{k!}.$$
2) Sustituir \((A_ne+B_n)/n!\).
Multiplicando por \(n!\):
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}.$$
Ahora se igualan por separado el coeficiente de \(e\) y la parte constante.
3) Recurrencias enteras.
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k,$$
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
4) Valores pequenos.
$$A_0=1,\ B_0=-1,\qquad A_1=2,\ B_1=-3,\qquad A_2=7,\ B_2=-12,$$
de donde
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!}.$$
El programa tambien comprueba
$$A_{10}=328161643,\qquad B_{10}=-652694486.$$
5) El objetivo se reduce a \(n!-A_n\).
Si definimos \(C_n=A_n+B_n\), entonces al sumar las recurrencias y usar induccion se obtiene
$$C_n=n!-A_n.$$
Por tanto, el valor pedido puede recuperarse con \(A_n\) solamente.
6) Modulo un primo \(p\), el factorial desaparece para \(n\ge p\).
En ese caso
$$n!\equiv 0\pmod p,\qquad A_n+B_n\equiv -A_n\pmod p.$$
El codigo usa la formula unificada
$$r_p(n)\equiv n!-A_{n'}\pmod p.$$
7) La compresion clave es la periodicidad modulo \(p\).
La implementacion aprovecha que \(A_n\bmod p\) entra, desde el indice \(p\), en un periodo de longitud
$$p(p-1).$$
Por ello reduce el indice a
$$n'= \begin{cases} n,& n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr),& n\ge p. \end{cases}$$
El propio programa hace comprobaciones de esta periodicidad para cada primo.
8) Como se calcula \(A_n\bmod p\).
Se generan sucesivamente \(A_0,\dots,A_{n'}\) con
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p.$$
La fila binomial se actualiza in situ mediante un arreglo comb, como una fila de Pascal modulo \(p\).
9) Finalmente se recompone con CRT.
Para \(n=10^9\), los residuos por primo son
$$r_7=1,\qquad r_{11}=3,\qquad r_{73}=66,\qquad r_{101}=44,\qquad r_{137}=117.$$
El teorema chino del resto da el unico residuo modulo \(77{,}777{,}777\).
1) Reducir \(n\) a \(n'\) para cada primo usando el periodo \(p(p-1)\).
2) Calcular \(A_0,\dots,A_{n'}\pmod p\) por convolucion binomial.
3) Obtener \(r_p(n)\equiv n!-A_{n'}\pmod p\).
4) Recomponer los cinco residuos con CRT.
Como \(n'<p^2\) y cada valor suma todos los anteriores, el costo por primo es
$$O((n')^2)$$
en tiempo y
$$O(n')$$
en memoria. Con estos primos pequenos, el total es muy bajo.
El codigo valida
$$A_{10}=328161643,\qquad B_{10}=-652694486,$$
y para \(0\le n\le 12\) compara el solver modular con la recurrencia exacta.
El resultado final es
$$\boxed{15955822}.$$
数列满足
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),\qquad a(n)=1\ (n<0).$$
题目说明每一项都能写成
$$a(n)=\frac{A(n)e+B(n)}{n!},$$
其中 \(A(n),B(n)\) 是整数，并要求计算
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777}.$$
1）把无穷和拆成有限部分与 \(e\) 的尾项。
当 \(i>n\) 时有 \(n-i<0\)，因此 \(a(n-i)=1\)。于是
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac1{i!} =\sum_{i=1}^{n}\frac{a(n-i)}{i!}+e-\sum_{k=0}^{n}\frac1{k!}.$$
2）代入 \((A_ne+B_n)/n!\) 形式。
两边乘以 \(n!\)，得到
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}.$$
接下来分别比较 \(e\) 的系数与常数项。
3）得到两条整数递推。
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k,$$
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
这正是代码中 compute_exact_ab 所实现的内容。
4）小例子可以直接复原题目中的值。
$$A_0=1,\ B_0=-1,\qquad A_1=2,\ B_1=-3,\qquad A_2=7,\ B_2=-12.$$
所以
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!}.$$
代码还检查更大的断点
$$A_{10}=328161643,\qquad B_{10}=-652694486.$$
5）目标量可以压缩成 \(n!-A_n\)。
令
$$C_n=A_n+B_n.$$
把两条递推相加并做归纳，可以得到
$$C_n=n!-A_n.$$
也就是说，题目真正要求的是 \(A_n\) 的一个简单修正，而不必同时追踪两条大序列。
6）在素数模 \(p\) 下，\(n!\) 从 \(n\ge p\) 开始恒为零。
因此
$$n!\equiv 0\pmod p,\qquad A_n+B_n\equiv -A_n\pmod p.$$
代码统一写成
$$r_p(n)\equiv n!-A_{n'}\pmod p.$$
7）真正的加速来自模 \(p\) 的周期性。
实现使用这样一个模性质：对每个素数 \(p\)，数列 \(A_n\bmod p\) 从索引 \(p\) 开始进入周期
$$p(p-1).$$
因此只需要把超大索引压缩成
$$n'= \begin{cases} n,& n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr),& n\ge p. \end{cases}$$
代码还对每个素因子做了跨一个完整周期的 spot-check。
8）如何计算 \(A_n\bmod p\)。
固定一个素数 \(p\)，顺序计算
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p.$$
二项式系数通过一个滚动的 Pascal 行数组 comb 原地更新，\(n!\bmod p\) 也同步更新；一旦 \(n\ge p\)，该项立刻变成 \(0\)。
9）最后用 CRT 合并五个素数模的结果。
对 \(n=10^9\)，代码得到
$$r_7=1,\qquad r_{11}=3,\qquad r_{73}=66,\qquad r_{101}=44,\qquad r_{137}=117.$$
中国剩余定理把它们还原为模 \(77{,}777{,}777\) 下的唯一答案。
1） 对每个素因子 \(p\)，用周期 \(p(p-1)\) 把 \(n\) 约化到 \(n'\)。
2） 按二项卷积递推计算 \(A_0,\dots,A_{n'}\pmod p\)。
3） 取素数模残差 \(r_p(n)\equiv n!-A_{n'}\pmod p\)。
4） 用中国剩余定理合并五个残差。
因为 \(n'<p^2\)，而每个新值都要累加此前所有 \(k\)，所以单个素数的时间复杂度是
$$O((n')^2),$$
空间复杂度是
$$O(n').$$
在本题中最大的 \(n'\) 也只是万级，因此总计算量很小。
程序验证
$$A_{10}=328161643,\qquad B_{10}=-652694486,$$
并对 \(0\le n\le 12\) 检查模算法与精确整数递推的一致性。
最终答案为
$$\boxed{15955822}.$$
Последовательность определяется формулой
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),\qquad a(n)=1\ (n<0).$$
Из условия известно, что
$$a(n)=\frac{A(n)e+B(n)}{n!},$$
где \(A(n)\) и \(B(n)\) - целые. Нужно найти
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777}.$$
1) Разделяем бесконечную сумму на конечную часть и хвост с \(e\).
Если \(i>n\), то \(n-i<0\), а значит \(a(n-i)=1\). Поэтому
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac1{i!} =\sum_{i=1}^{n}\frac{a(n-i)}{i!}+e-\sum_{k=0}^{n}\frac1{k!}.$$
2) Подставляем форму \((A_ne+B_n)/n!\).
После умножения на \(n!\) получаем
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}.$$
Теперь коэффициент при \(e\) и свободная часть сравниваются отдельно.
3) Получаем точные рекурсии.
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k,$$
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
4) Первые значения.
$$A_0=1,\ B_0=-1,\qquad A_1=2,\ B_1=-3,\qquad A_2=7,\ B_2=-12.$$
Отсюда
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!},$$
что совпадает с условием. В коде дополнительно проверяется
$$A_{10}=328161643,\qquad B_{10}=-652694486.$$
5) Сумма \(A_n+B_n\) упрощается до \(n!-A_n\).
Положим \(C_n=A_n+B_n\). Тогда после сложения рекурсий и индукции получается
$$C_n=n!-A_n.$$
То есть интересующая нас величина выражается только через \(A_n\).
6) По модулю простого \(p\) факториал зануляется при \(n\ge p\).
Следовательно,
$$n!\equiv 0\pmod p,\qquad A_n+B_n\equiv -A_n\pmod p.$$
Программа использует единую запись
$$r_p(n)\equiv n!-A_{n'}\pmod p.$$
7) Главное ускорение - периодичность \(A_n\bmod p\).
Реализация использует факт, что начиная с индекса \(p\), последовательность \(A_n\bmod p\) имеет период
$$p(p-1).$$
Поэтому огромный индекс \(10^9\) заменяется на
$$n'= \begin{cases} n,& n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr),& n\ge p. \end{cases}$$
Код дополнительно делает spot-check этой периодичности для каждого простого делителя.
8) Как считается \(A_n\bmod p\).
Для фиксированного простого \(p\) значения \(A_0,\dots,A_{n'}\) строятся по формуле
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p.$$
Биномиальная строка Паскаля поддерживается в одном массиве comb, обновляемом справа налево.
9) Затем применяется CRT.
Для \(n=10^9\) программа получает
$$r_7=1,\qquad r_{11}=3,\qquad r_{73}=66,\qquad r_{101}=44,\qquad r_{137}=117.$$
Китайская теорема об остатках восстанавливает из них единственный остаток по модулю \(77{,}777{,}777\).
1) Для каждого простого \(p\) сократить индекс при помощи периода \(p(p-1)\).
2) Вычислить \(A_0,\dots,A_{n'}\pmod p\) по биномиальной свертке.
3) Взять остаток \(r_p(n)\equiv n!-A_{n'}\pmod p\).
4) Объединить пять остатков через CRT.
Поскольку \(n'<p^2\), а каждый новый член суммирует все предыдущие, стоимость для одного простого модуля равна
$$O((n')^2)$$
по времени и
$$O(n')$$
по памяти. Для данных маленьких простых это очень быстро.
Код проверяет
$$A_{10}=328161643,\qquad B_{10}=-652694486,$$
а также для \(0\le n\le 12\) сверяет модульное решение с точной целочисленной рекурсией.
Окончательный ответ:
$$\boxed{15955822}.$$
المتتالية معرفة بالعلاقة
$$a(n)=\sum_{i=1}^{\infty}\frac{a(n-i)}{i!}\qquad(n\ge 0),\qquad a(n)=1\ (n<0).$$
ويذكر نص المسألة أن كل حد يمكن كتابته على الصورة
$$a(n)=\frac{A(n)e+B(n)}{n!},$$
حيث \(A(n)\) و\(B(n)\) عددان صحيحان. المطلوب هو حساب
$$A(10^9)+B(10^9)\pmod{77{,}777{,}777}.$$
1) نفصل المجموع اللانهائي إلى جزء منتهٍ وذيل مرتبط بـ \(e\).
إذا كان \(i>n\) فإن \(n-i<0\)، وبالتالي من شرط الحدود نحصل على \(a(n-i)=1\). لذلك
$$a(n)=\sum_{i=1}^{n}\frac{a(n-i)}{i!}+\sum_{i=n+1}^{\infty}\frac1{i!} =\sum_{i=1}^{n}\frac{a(n-i)}{i!}+e-\sum_{k=0}^{n}\frac1{k!}.$$
2) نعوض بالصيغة \((A_ne+B_n)/n!\).
بعد الضرب في \(n!\) نحصل على
$$A_n e+B_n =\sum_{k=0}^{n-1}\binom{n}{k}(A_k e+B_k)+e\,n!-\sum_{k=0}^{n}\frac{n!}{k!}.$$
ومن هنا نقارن معامل \(e\) والجزء الثابت كلًّا على حدة.
3) نحصل على علاقتين صحيحتين تمامًا لـ \(A_n\) و\(B_n\).
$$A_n=n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k,$$
$$B_n=-\sum_{k=0}^{n}\frac{n!}{k!}+\sum_{k=0}^{n-1}\binom{n}{k}B_k.$$
وهاتان هما بالضبط العلاقتان اللتان يستخدمهما الكود في فحوص القيم الصغيرة.
4) القيم الأولى تعيد أمثلة نص المسألة.
$$A_0=1,\ B_0=-1,\qquad A_1=2,\ B_1=-3,\qquad A_2=7,\ B_2=-12.$$
ومن ثم
$$a(0)=e-1,\qquad a(1)=2e-3,\qquad a(2)=\frac{7e-12}{2!}.$$
كما يتحقق البرنامج أيضًا من النقطة الكبيرة
$$A_{10}=328161643,\qquad B_{10}=-652694486.$$
5) الكمية المطلوبة تختزل إلى \(n!-A_n\).
إذا عرفنا
$$C_n=A_n+B_n,$$
فإن جمع العلاقتين ثم تطبيق الاستقراء يعطي
$$C_n=n!-A_n.$$
أي أن المطلوب في النهاية يمكن حسابه من \(A_n\) وحده.
6) عند العمل modulo أولي \(p\)، يختفي \(n!\) عندما \(n\ge p\).
إذ عندها
$$n!\equiv 0\pmod p,\qquad A_n+B_n\equiv -A_n\pmod p.$$
ولهذا يكتب الكود الباقي على الصورة الموحدة
$$r_p(n)\equiv n!-A_{n'}\pmod p.$$
7) ضغط الفهرس يعتمد على دورية modulo كل أولي.
تستفيد الخوارزمية من حقيقة أن المتتالية \(A_n\bmod p\) تصبح دورية ابتداءً من الفهرس \(p\) وبطول
$$p(p-1).$$
ولهذا يختزل الفهرس الضخم إلى
$$n'= \begin{cases} n,& n<p,\\ p+\bigl((n-p)\bmod p(p-1)\bigr),& n\ge p. \end{cases}$$
والكود يجري اختبارات موضعية لهذه الدورية لكل عامل أولي.
8) حساب \(A_n\bmod p\) يتم مباشرة من العلاقة الالتفافية.
لكل أولي ثابت \(p\) نحسب
$$A_n\equiv n!+\sum_{k=0}^{n-1}\binom{n}{k}A_k\pmod p$$
بشكل تتابعي. صف معاملات ذات الحدين يحفظ في المصفوفة comb ويحدث من اليمين إلى اليسار مثل صف باسكال modulo \(p\).
9) ثم نعيد تركيب البواقي الخمسة بواسطة CRT.
عند \(n=10^9\) يعطي الكود
$$r_7=1,\qquad r_{11}=3,\qquad r_{73}=66,\qquad r_{101}=44,\qquad r_{137}=117.$$
ثم تعيد مبرهنة البواقي الصينية تركيب الجواب الوحيد modulo \(77{,}777{,}777\).
1) لكل عامل أولي \(p\)، نختزل \(n\) إلى \(n'\) باستخدام دورية طولها \(p(p-1)\).
2) نحسب \(A_0,\dots,A_{n'}\pmod p\) بالعلاقة الثنائية السابقة.
3) نأخذ الباقي \(r_p(n)\equiv n!-A_{n'}\pmod p\).
4) نجمع البواقي الخمسة بنظرية البواقي الصينية.
بما أن \(n'<p^2\)، وكل قيمة جديدة تجمع كل القيم السابقة، فالتكلفة لكل أولي هي
$$O((n')^2)$$
زمنًا و
$$O(n')$$
ذاكرةً. ومع صغر هذه العوامل الأولية يبقى الحساب عمليًا جدًا.
يتحقق البرنامج من
$$A_{10}=328161643,\qquad B_{10}=-652694486,$$
ويطابق الحل المعياري مع العودية الصحيحة لكل \(0\le n\le 12\).
والنتيجة النهائية هي
$$\boxed{15955822}.$$