線形漸化式の値を行列を使って求める - Qiita

t_0=0, t_1=t_2=1, t_3=4 \\ \large t_n = 2t_{n-1}+2t_{n-2}-2t_{n-3}+t_{n-4} この問題は$n$の値が$10^{12}$と非常に大きいのとmod計算がキーとなります。 再帰プログラム まずは安易に再帰プログラム。lru_cacheを付けても$10^3$で撃沈。 from functools import lru_cache @lru_cache(maxsize=None) def t(n): if n < 4: return [0,1,1,4][n] return (2*t(n-1)+2*t(n-2)-2*t(n-3)+t(n-4)) % 10**4 print(t(10**2)) # 8344