跳跃青蛙

池塘里有依次标着$1$到$n$的排成一行的$n$块石头，相邻标号的石头间的距离都相等。

一只青蛙从石头1开始，希望拜访每个石头恰好一次，并最后落在石头$n$上。它每次只能跳最多三格，也就是从石头$i$跳到$i\pm1, i\pm 2, i\pm 3$。

用$f(n)$表示所有可行跳法的总数，例如$f(6)=14$，跳法如下： \begin{align*} 1\mapsto 2\mapsto 3\mapsto 4\mapsto 5\mapsto 6 \\ 1\mapsto 2\mapsto 3\mapsto 5\mapsto 4\mapsto 6 \\ 1\mapsto 2\mapsto 4\mapsto 3\mapsto 5\mapsto 6 \\ 1\mapsto 2\mapsto 4\mapsto 5\mapsto 3\mapsto 6 \\ 1\mapsto 2\mapsto 5\mapsto 3\mapsto 4\mapsto 6 \\ 1\mapsto 2\mapsto 5\mapsto 4\mapsto 3\mapsto 6 \\ 1\mapsto 3\mapsto 2\mapsto 4\mapsto 5\mapsto 6 \\ 1\mapsto 3\mapsto 2\mapsto 5\mapsto 4\mapsto 6 \\ 1\mapsto 3\mapsto 4\mapsto 2\mapsto 5\mapsto 6 \\ 1\mapsto 3\mapsto 5\mapsto 2\mapsto 4\mapsto 6 \\ 1\mapsto 4\mapsto 2\mapsto 3\mapsto 5\mapsto 6 \\ 1\mapsto 4\mapsto 2\mapsto 5\mapsto 3\mapsto 6 \\ 1\mapsto 4\mapsto 3\mapsto 2\mapsto 5\mapsto 6 \\ 1\mapsto 4\mapsto 5\mapsto 2\mapsto 3\mapsto 6 \end{align*} 此外，可以验证$f(10)=254, f(40)=1439682432976$。

令$S(L)=\sum_{n=1}^L\left(f(n)\right)^3$，可以验证 \begin{align*} S(10)&=18230635, \\ S(20)&=104207881192114219, \\ S(1000) \bmod 10^9&=225031475, \\ S(10^6) \bmod 10^9&=363486179. \end{align*} 求$S(10^{14}) \bmod 10^9$。

本题难度:

解答

从定义可以看出$f$具备动态规划的特性，必定满足线性递推式，不难验证 $$f_n=2f_{n-1}-f_{n-2}+2f_{n-3}+f_{n-4}+f_{n-5}-f_{n-7}-f_{n-8}.$$ 从而$f_n^k$是关于$f_{n-1},\ldots,f_{n-8},f_{n-1}^2,\ldots,f_{n-8}^2,\ldots,f_{n-1}^k,\ldots,f_{n-8}^k$的递推式。

直接用矩阵形式计算即得最终结果$777577686$。

注：因使用numpy作多维数组运算，以下代码为Python 3。

import numpy

n=10**14

mod=10**9
X=[1, 1, 1, 2, 6, 14, 28, 56]
T=[[[i==j==k < n%8 for k in range(8)] for j in range(8)] for i in range(8)]
M=numpy.array([[0,  1,  0,  0,  0,  0,  0,  0],
[ 0,  0,  1,  0,  0,  0,  0,  0],
[ 0,  0,  0,  1,  0,  0,  0,  0],
[ 0,  0,  0,  0,  1,  0,  0,  0],
[ 0,  0,  0,  0,  0,  1,  0,  0],
[ 0,  0,  0,  0,  0,  0,  1,  0],
[ 0,  0,  0,  0,  0,  0,  0,  1],
[-1, -1,  0,  1,  1,  2, -1,  2]], numpy.int64)

f=lambda A,B:numpy.remainder(numpy.tensordot(A, B, axes=(0,0)), mod)
g=lambda A:numpy.remainder(numpy.tensordot(A, A, axes=(1,0)), mod)
f3=lambda A,B:f(f(f(A,B),B),B)
h=lambda m,A,B,C: f3(numpy.remainder(f3(A,B)+C,mod),X) if m==1 else h(m//2, numpy.remainder(f3(A,B)+C,mod) if m%2==1 else A, g(B), numpy.remainder(f3(C,B)+C, mod))
    
print(f(f(f(T))) if n//8==0 else h(n//8, T, g(g(g(M))), [[[i==j==k for k in range(8)] for j in range(8)] for i in range(8)]))