Recursive Sequence
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy (\(a_i\)) các số tự nhiên được định như sau:
- \(a_i = b_i\) (với \(i \le k\))
- \(a_i = c_1a_{i-1} + c_2a_{i-2} + ... + c_ka_{i-k}\) (với \(i > k\))
Với \(b_i\) và \(c_i\) là các số tự nhiên cho trước (\(1\le i\le k\)). Hãy tính \(a_n \mod 10^9\), với \(n\) cho trước.
Input
- Dòng đầu tiên chứa số \(c\) là số lượng test (\(1\le c\le 1000\)). Mỗi test chứa 4 dòng:
- Dòng 1: chứa số \(k\), là số phần tử của dãy \(c\) và \(b\) (\(1 \le k \le 10\))
- Dòng 2: chứa các số \(b_1,...,b_k\) với \(0 \le b_i \le 10^9\), mỗi số cách nhau một dấu cách.
- Dòng 3: chứa các số \(c_1,...,c_k\) với \(0 \le c_i \le 10^9\), mỗi số cách nhau một dấu cách.
- Dòng 4: chứa số \(n\) (\(0 \le n \le 10^9\))
Output
- Gồm \(c\) dòng, mỗi dòng là kết quả của một test, ghi giá trị: \(a_n \mod 10^9\)
Example
Test 1
Input
3
3
5 8 2
32 54 6
2
3
1 2 3
4 5 6
6
3
24 354 6
56 57 465
98765432Output
8
714
257599514
Bình luận
Mình xin chia sẻ lời giải bài này như sau:
Ta có: \(\left\{\begin{matrix} a_i=b_i (\forall i\le k) \\ a_i =\sum\limits_{j=1}^{k}c_ja_{i-j} (\forall i>k)\end{matrix}\right.\)
\(\implies \begin{pmatrix}a_n & a_{n-1} & ... & a_{n-k+1}\end{pmatrix}.\begin{pmatrix}c_1 & 1 & 0 & ... & 0 \\ c_2 & 0 & 1 & ... & 0 \\ ... \\ c_n & 0 & 0 & ... &0 \end{pmatrix}=\begin{pmatrix}a_{n+1} & a_{n} & ... & a_{n-k+2}\end{pmatrix}\)
Để hiểu tại sao ta lại ra được công thức trên, các bạn cứ lấy các trường hợp nhỏ ứng với \(k=2,k=3,k=4,...\) là ta sẽ rút ra được quy luật.
Đến đây đặt \(p_n = \begin{pmatrix}a_n & a_{n-1} & ... & a_{n-k+1}\end{pmatrix}\) và \(M=\begin{pmatrix}c_1 & 1 & 0 & ... & 0 \\ c_2 & 0 & 1 & ... & 0 \\ ... \\ c_n & 0 & 0 & ... &0 \end{pmatrix}\)
Ta được: \(p_{n} = p_{n-1}.M = ... = p_k.M^{n-k}\)
trong đó: \(p_k=\begin{pmatrix}a_k & a_{k-1} & ... & a_{1}\end{pmatrix}\)
Đến đây, ứng với \(n<k\) thì kết quả rõ ràng là : \(b[n]\). Ngược lại chúng ta sử dụng lũy thừa nhị phân để tính \(p_n\) là xong.
Như vậy là bài toán đã được giải quyết.
Các bạn có thể tham khảo code của mình tại đây
1 bình luận nữa