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\)\(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\)\(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 
98765432
Output
8 
714 
257599514

Bình luận


  • 1
    jumptozero    10:07 p.m. 28 Tháng 2, 2021 chỉnh sửa 2

    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}\)\(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