PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming, Binary Exponentiation, Fermats Little Theorem
PROBLEM:
Define the sequence f_i as:
- f_0 = \text{``0"}
- f_1 = \text{``1"}
- f_i = f_{i-1}+f_{i-2} for i\ge 2, where + is the string concatenation operation.
Determine the sum of the digits of all subsequences of f_i modulo 10^9+7.
EXPLANATION:
It is evident that f_i only consists of zeros and ones. Let k_i denote the number of ones in f_i.
Also, let len_i denote the length of string f_i.
Claim: Every digit in f_i occurs in exactly 2^{len_i-1} subsequences of f_i.
(See this for details. Complete proof is trivial and left to the reader.)
The sum of the digits over all subsequences is equivalent to the sum of the number of times each 1 occurs in a subsequence. From the above claim, it is clear that the answer is then k_i*2^{len_i-1}.
All that remains is to calculate k_i and len_i efficiently.
Since f_i is the concatenation of f_{i-1} and f_{i-1}, k_i is therefore equal to k_{i-1}+k_{i-2}. Similarly, len_i is equal to len_{i-1}+len_{i-2}. This can be precomputed quickly using dynamic programming.
Recurrence relations
The formula for calculating k_i is
- k_0 = 0, k_1 = 1
- k_i = k_{i-1}+k_{i-2}
Similarly, the formula for calculating len_i is
- len_0 = 1, len_1 = 1
- len_i = len_{i-1}+len_{i-2}
Special emphasis must be made on the method to compute the answer modulo MOD = 10^9+7.
The important point to note here is that, while computing the answer modulo MOD,
(not 2^{(len_i-1) \% MOD}) by application of Fermats little theorem (see this for details).
You should use binary exponentiation to compute the value of 2^{len_i} in O(\log len_i).
TIME COMPLEXITY:
Precomputing the answer for every i \le 10^5 can be done in
where MOD=10^9+7. The \log factor is present because of the pow
function (which implements binary exponentiation for an optimal runtime).
SOLUTIONS:
Editorialist’s solution can be found here.
BONUS:
How would you find the sum of digits over all subsequences of f_i when i \le 10^{18}?
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters