欧拉数

数列$a_n$的定义如下 $$a_n=\begin{cases} 1 & n < 0, \\ \sum_{i=1}^{\infty} \frac{a_{n-i}}{i!} & n \ge 0.\end{cases}$$ 它的前几项是 \begin{align*} a_0&=\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\ldots=e-1 \\ a_1&=\frac{e-1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\ldots=2e-3 \\ a_2&=\frac{2e-3}{1!}+\frac{e-1}{2!}+\frac{1}{3!}+\ldots=\frac{7}{2}e-6, \end{align*} 可以发现$a_n$总是可以表达为 $$a_n=\frac{A_ne+B_n}{n!},$$ 的形式，其中$A_n, B_n$均为整数。例如 $$a_{10}=\frac{328161643e − 652694486}{10!},$$ 求$A_{10^9}+A_{10^9}$模77777777的余数。

本题难度:

解答

令$C_n=A_n+B_n$，可以观察发现$2A_n+B_n=n!$，由于这一关系的存在，$C_n$事实上可以写成不同的形式，以下使用的是 $$C_n=-\sum_{k=0}^{n-1}\binom{n}{k}C_k-\sum_{k=1}^{n}\frac{n!}{k!},$$ 由于$77777777=7\times 11\times 73\times 101\times 137$，因此可以计算$C_n$模每个素因子的结果，再用中国剩余定理将其组合。

右侧两个求和项可以分别用杨辉三角和秦九韶法（以下代码中的变量q）递推计算。

可以观察到（证明较繁琐），$C_n$模素因子p的结果是周期为$p(p-1)$的序列，因此只需计算大约一万项即可得结果$15955822$。

注：中国剩余定理的简单版本韩信点兵是我国小学奥数的传统内容，此处由于涉及的素数很小，直接遍历$\mathbb Z_p$来找出乘法逆。

注2：因需使用math.prod函数，以下代码为Python 3。

import math

def inverse(a,p):
  x=1
  while (x*a)%p!=1:
    x+=1
  return x 

d={}
for p in [7,11,73,101,137]:
    c=[0]
    q=0
    pascal=[1]
    for i in range(1,10**9%(p*(p-1))+1):
        q=(i*q+1)%p
        pascal=[1]+[(pascal[j]+pascal[j+1])%p for j in range(i-1)]+[1]
        c.append((sum((pascal[j]*c[j])%p for j in range(i))+q)%p)
    d[p]=c[-1]

n=math.prod(d.keys())
print((-(sum(d[p]*inverse(n//p,p)*n//p for p in d)%n))%77777777)