CHEFSQN Editorial

editorial
, ,
1

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;
    }
}
1 Like