欧拉数

数列

a_{n}

的定义如下

a_{n} = {\begin{cases} 1 & n < 0, \\ \sum_{i = 1}^{\infty} \frac{a_{n - i}}{i!} & n \geq 0. \end{cases}

它的前几项是

\begin{aligned} a_{0} & = \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots = e - 1 \\ a_{1} & = \frac{e - 1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots = 2 e - 3 \\ a_{2} & = \frac{2 e - 3}{1!} + \frac{e - 1}{2!} + \frac{1}{3!} + \dots = \frac{7}{2} e - 6, \end{aligned}

可以发现

a_{n}

总是可以表达为

a_{n} = \frac{A_{n} e + B_{n}}{n!},

的形式，其中

A_{n}, B_{n}

均为整数。例如

a_{10} = \frac{328161643 e - 652694486}{10!},

求

A_{10^{9}} + A_{10^{9}}

模77777777的余数。

本题难度:

解答

令

C_{n} = A_{n} + B_{n}

，可以观察发现

2 A_{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

。

注：中国剩余定理的简单版本韩信点兵是我国小学奥数的传统内容，此处由于涉及的素数很小，直接遍历

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)