Problem Link

Author: @prasoonjain006

Tester: @prasoonjain006

Editorialist: @anshu8oct

Difficulty: Easy

Prerequisites : Basic Maths

**Problem description**

There is a Sequence S. Chefina will give its first term X, second term Y and third term Z. The nth term of the sequence is the sum of the previous three terms. Formally Sn=S(n−1)+S(n−2)+S(n−3). Then she will ask T queries. In each query she will give an integer N to Chef and Chef has to tell the Nth element of the sequence. Chef found this question very easy and thought he would answer quickly. But after looking at the constraints of T and N, he got confused and asked for your help. Are you able to find the answer i.e. Nth term of the given sequence.

Note− As you can see size of the elements of sequence can be very large, so for every Nth term take modulo 1000000007 .

**Quick explanation**

It is basic maths and for the time complexity part , we need to **precompute the values for each query from 1 to n**. Hence, **it is O(n) for precomputation and O(t) for each queries. Time Complexity - O(n)**.

**Solution**

Setter’s solution

```
#include <bits/stdc++.h>
using namespace std;
#define size 1000001
#define m 1000000007
vector<int> preCompute(int x,int y,int z)
{
vector<int> sol(size);
sol[0]=x,sol[1]=y,sol[2]=z;
for(int i=3;i<size;i++) sol[i]=((sol[i-1]%m + sol[i-2]%m)%m + sol[i-3]%m)%m;
return sol;
}
int main() {
int t,x,y,z,n;
cin>>t>>x>>y>>z;
vector<int> sol=preCompute(x,y,z);
while(t--)
{
cin>>n;
cout<<sol[n-1]<<endl;
}
}
```