\begin{array}{c} \text{Dãy số} \\ \text{Giới hạn thời gian:} \ 1000 \ \text{ms} \\ \text{Giới hạn bộ nhớ:} \ 512 \ \text{MB} \\ \text{Đầu vào: Bàn phím} \\ \text{Đầu ra: Màn hình} \end{array} Cho dãy `(u_n)` xác định bởi hệ thức truy hồi: `{(u_1=84),(u_2=496),(u_3=3144),(u_(n+3)=13u_(n+2)-50u_(n+1)+56u_n \ (n in NN^**)):}` Cho trước một số nguyên dương `n`, hãy tìm `u_n`. Do `u_n` có thể quá lớn nên hãy in ra `u_n % (10^9 + 7)`. `"Input"` $\qquad$ `***` `"Một dòng chứa số nguyên dương" \ n \ (1 <= n <= 10^9)` `"Output"` $\qquad$ `***` Kết quả bài toán `"Scoring"` $\qquad$ `***` Subtask `1` (`10%` số điểm): `1 <= n <= 10^3` $\qquad$ `***` Subtask `2` (`40%` số điểm): `10^3 < n <= 10^6` $\qquad$ `***` Subtask `3` (`50%` số điểm): `10^6 < n <= 10^9` `"Example"` \begin{array}{|c|c|c|} \hline \text{Input}&\text{Output} \\\hline 4&20776 \\\hline 10&266095482 \\\hline \end{array} `"Ngôn ngữ lập trình: Python"`

Ta cần:

$A\left[\begin{array}{ccc}u_n\\u_{n+1}\\u_{n+2}\end{array}\right] = $ $\left[\begin{array}{ccc}u_{n+1}\\u_{n+2}\\u_{n+3}\end{array}\right]$

Từ định nghĩa

`{(u_1=84),(u_2=496),(u_3=3144),(u_(n+3)=13u_(n+2)-50u_(n+1)+56u_n \ (n in NN^**)):}`

Ta suy ra được 

$A=\left[\begin{array}{ccc}0&1&0\\0&0&1\\56&-50&13\end{array}\right]$ 

Triển khai hàm tính lũy thừa nhanh, ta có thể dễ dàng tính `u_{n}` trong O(TlogN) với T là thời gian tính `AB`.

$\\$

$\color{#23d78c}{\texttt{P}}\color{#9ee36f}{\texttt{y}}\color{#10c1ed}{\texttt{t}}\color{#10c1ed}{\texttt{h}}\color{#c6ea64}{\texttt{o}}\color{#fbfb45}{\texttt{n}}$

MOD = 10**9+7
def mod(x):
    return (x + MOD) % MOD
def nhan(a, b):
    m = len(a)
    n = len(a[0])
    p = len(b[0])
    c = [[0]*p for _ in range(m)]
    for i in range(m):
        for j in range(p):
            for k in range(n):
                c[i][j] = mod(c[i][j] + a[i][k] * b[k][j])
    return c
def power(a, n):
    res = a
    n -= 1
    while n > 0:
        if (n & 1): res = nhan(res, a)
        a = nhan(a, a)
        n >>= 1
    return res
a = [[0, 1, 0], [0, 0, 1], [56, -50, 13]]
b = [[84], [496], [3144]]

n = int(input())
if n == 1:
    print(84)
elif n == 2:
    print(496)
elif n == 3:
    print(3144)
else:
    print(nhan(power(a, n-1), b)[0][0])
    
# Author : Daoanhviet96
# Language : Python3

$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}