CHFNSEQ - Editorial

Problem link:##

Contest , Practice

Setter: Aman Kumar Singh

Tester: Indrajit Sinha.

Difficulty:##

Easy

Prerequisites:##

Modular division Properties

Explanation:##

As the N is 10^18 so we cannot form any type of array upto N.And as q is also very large 10^5
each query has to be answered in O(1) time complexity.For each query there are two numbers
l and r and the answer to the query is the sum of all the numbers from i’th number of the
sequence to the r’th number of sequence[l,r]. First we find the middle position of of the
sequence.Then there can be 3 consequences:

  1. l and r both are on the right of middle point.

  2. l and r both are on the left of middle point.

  3. l is on the left of the middle point and r is on the left of the middle point.

Let MOD_VAL=10^9+7

For 1 and 2 we just find the number which is corresponding to the l th position from middle
and the number which is corresponding to the r th position from middle. And we just use the
formula

((Number of terms in the AP) MOD_VAL*(First term + last term)
MOD_VAL*(2^(MOD_VAL-2))%MOD_VAL)%MOD_VAL (where 2^(MOD_VAL-2))%MOD_VAL is
the multiplicative mod inverse of 2).

For 3rd consequence there will be 2 AP one on the right of middle and one on left of middle,
we find the number which is corresponding to the l th position from middle and the number
which is corresponding to the r th position from middle. And we just use the formula

((Number of terms in the AP) MOD_VAL*(First term + middle term)
MOD_VAL*(2^(MOD_VAL-2))%MOD_VAL)%MOD_VAL (where 2^(MOD_VAL-2))MOD_VAL is the multiplicative mod inverse of 2)+ ((Number of terms in the AP) MOD_VAL*(2 + last term) % MOD_VAL*(2^(MOD_VAL2))%MOD_VAL)%MOD_VAL
(where 2^(MOD_VAL-2))%MOD_VAL is the multiplicative mod
inverse of 2)

Time Complexity:##

O(1) per query

Author’s and Tester’s Solution:##

Author’s solution is here

Tester’s solution is here