In this post, I will consider a problem with such a condition:
You have an array A of length K filled with numbers. Each next element of the array is the sum of K previous elements. Find the value of the element that will be at position N. Since the answer may be too large, you should output it modulo 1e9+7.
Solution №1.
This solution is the most primitive and consists of explicitly getting an array A of length N and outputting the last element.
At each step we need to sum K of the previous elements, and there will be N-K such steps.
Final asymptotics — O(K*(N-K))
Solution №2
Note that by using prefix sums we can get this value for O(1) instead of summing K previous elements each time.
Final asymptotics — O(N)
Solution №3
Now we'll use matrices.
To quickly count the Nth element of the array A, we need to find such a matrix that:
(A[i-k+1], A[i-k+2], ... , A[i]) * X = (A[i-k+2], A[i-k+3], ... , A[i+1])
The X matrix is constructed using the following method:
The matrix will be of size K*K and will initially consist of zeros, so that after multiplying a matrix of size K*1 by a matrix of size K*K, a matrix of size K*1 will be obtained.
Let's look at a square of size (K-1)*(K-1) with the lower left corner in the lower left corner of the K*K matrix. Let's replace all elements of the main diagonal by 1.
Replace all elements of the last column of the matrix K*K by 1.
I will prove the correctness of this construction:
After multiplying the matrix X, a matrix X will be obtained:
(A[i-k+2], A[i-k+3], ... , A[i-k+1] + A[i-k+2] + ... + A[i])
Since by the condition the next element of the array is the sum of K previous elements, the last element is exactly equal to A[i+1]. I.e. the required matrix was obtained.
Usage
You need to create an initial matrix of 1*K elements, then elevate the matrix X to degree (N-K) using binary degree expansion modulo 1e9+7.
At the end, multiply the initial matrix by the obtained matrix X^(N-K) modulo 1e9+7 and get the answer. It will be in the Kth element of the final matrix.
Final asymptotics — O(logN * (K^3))
You can get rid of the cube in degree by using faster matrix multiplication algorithms.
Example matrices for different K:
K = 1:
(1)
K = 2:
(0 1)
(1 1)
K = 3:
(0 0 1)
(1 0 1)
(0 1 1)
K = 4:
(0 0 0 1)
(1 0 0 1)
(0 1 0 1)
(0 0 1 1)
K = 5:
(0 0 0 0 1)
(1 0 0 0 1)
(0 1 0 0 1)
(0 0 1 0 1)
(0 0 0 1 1)
P.S. When K = 2, this problem is very similar to the idea of Fibonacci numbers
Results
The choice of solution option will come from the constraints in the problem, for large K and small N the 2nd option should be used, for the reverse case where large N and small K the matrices should be used.
