Answered: Information is present in the…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

100%

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply dynamic programming. Do not use recursion/memoization. Make sure ALL test cases return expected outputs.

Sample Input 0
4 4
1
2
3
4
0
1
2
3

Sample Output 0
1
3
7
15

Explanation 0
You are given the sequence 1,2,3,4.
F₀ = A₀ = 1
F₁ = A₁ + F₀ = 2 + 1 = 3
F₂ = A₂ + F₁ + F₀ = 3 + 3 + 1 = 7
F₃ = A₃ + F₂ + F₁ + F₀ = 4 + 7 + 3 + 1 = 15

The actual code

def solve(k,a):
MOD = 1000000007
# compute and return answer here

q, n = list(map(int,input().rstrip().split(" ")))
a = [int(input().rstrip()) for i in range(n)]
outs = []
for i in range(q):
k = int(input().rstrip())
outs.append(solve(k,a))
print("{}".format("\n".join(list(map(str,outs)))))

There is a notorious sequence that grows too fast and too furiously. We can define it as follows:
Given a sequence A0, A₁,..., An-1.
Fn An if n = 0
=
Fr
=
= An +F; if n > 0
You must answer queries. For each query, k, you must output F. This number may be so fast and furious
that so print it mod (10⁹ + 7). See the sample input to see an example computation.
Input Format
Input begins with a line with two space-separated integers Q and N, indicating the number of queries and
the number of given values in the sequence.
N lines follow, the ith line containing a single integer Aį.
lines follow, each containing a query k.
Constraints
1≤Q≤ 3.105
1≤N ≤ 2.10³
0 <k < N
0 ≤ A ≤ 10⁹
Output Format
For each query, output a single line containing f(k) mod (10⁹ + 7).

Expert Solution

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions