Ok and Thanks @ameybhavsar nthterm is ll type i.e long long are iterator also allowed to be of type long long
please help,shows time limit exceeded:-
#include
#include
#include
#include
#include
using namespace std;
int main(){
long long t{},maxy{1000000007},maxs{-1},sum{1};
vector result{};
vector sums{1};
vector position{};
cin>>t;
for(long long i{};i<t;i++){
long long l{},r{};
cin>>l>>r;
position.push_back(l);
position.push_back®;}
for(long long i{1};i<position.size();i=i+2){
if(position[i]>maxs)
maxs = position[i];}
vector <long long> g{0,1};
for(long long j{2};j<=maxs;j++){
long long h{};
h = 1+g[j-g[g[j-1]]];
g.push_back(h);
sum = (sum + g[j]*g[j])%maxy;
sums.push_back(sum);}
for(long long i{0};i<position.size();i=i+2){
if(position[i]!=1)
sum = sums[position[i+1]-1]- sums[position[i]-2];
else
sum = sums[position[i+1]-1];
result.push_back(sum);
}
for(long long c:result)
cout<<c<<endl;
}
is there a pattern in frequencties of numbers ?? If yes then it will be a great help if you mention it clearly
2 Likes
i cannot understand this statement “since the quantity is large compute it with modulo 10e9+7” what does this mean?
The modulo refers to Modular Arithmetic
That means that whenever the value becomes 10^9+7 or larger you keep removing multiples of 10^9+7 until the value is again in the range 0\ldots10^9+6
It is because the final answer can exceed the maximum limit of long long. The 1010 th number in the sequence is greater than 106. So, the maximum answer can be around 1010 * (106) 2 which is above long long’s maximum value. So, you are required to compute the answer mod 109 + 7.
Does anyone got this problem ??? means what is the use of sum[x]=yxx for example g[4]=3;
if query is L=1,R=4 and ans-> (g[1]^2 +g[2]^2 +g[3]^2 +g[4]^2) ??
please explain with example??..thanks in advance…
I can’t understand the main idea here. Please help me. Thanx in advance
1 Like
For the idea of this solution see my unofficial editorial and especially a comment I made lower down
1 Like
please help shows time limit exceeded:-
#include
#include
#include
#include
#include
using namespace std;
int main(){
long long t{},maxy{1000000007},maxs{-1},sum{1};
vector result{};
vector sums{1};
vector position{};
cin>>t;
for(long long i{};i<t;i++){
long long l{},r{};
cin>>l>>r;
position.push_back(l);
position.push_back®;}
for(long long i{1};i<position.size();i=i+2){
if(position[i]>maxs)
maxs = position[i];}
vector <long long> g{0,1};
for(long long j{2};j<=maxs;j++){
long long h{};
h = 1+g[j-g[g[j-1]]];
g.push_back(h);
sum = (sum + g[j]*g[j])%maxy;
sums.push_back(sum);}
for(long long i{0};i<position.size();i=i+2){
if(position[i]!=1)
sum = sums[position[i+1]-1]- sums[position[i]-2];
else
sum = sums[position[i+1]-1];
result.push_back(sum);}
for(long long c:result)
cout<<c<<endl;
}
Thanx a lot
can you please tell how the binary search is working . i can’t able to understand it.
please tell the idea of using the binary search here
Because the three arrays will have a length of 1 820 598 elements, which combined with the 10^5 test cases will result in an TLE if you iterate over them for each test case. Another approach could be to first read in the indexes that are needed; then make the arrays and calculate the corresponding values as you come across them, but that is a little harder to implement.
1 Like
In C/C++ array name is starting location of an array. So here prefixSum refers to starting location of prefixSum array. And the whole expression is used to calculate the index at which element ‘n’ is present in prefixSum array.
1 Like
Oh yeah Thanks , now I remember it
The question states that L and R can be upto 10^10. But we are only declaring golomb array upto 2*10^6.
ll g[SIZE], prefixSum[SIZE], prefixSum2[SIZE];
How are inputs of L and R which are above 2*10^6 handled?
Thanks in advance
1 Like
Prefix and prefix contains values and not the golomb sequence … the value corresponding to max input(10^10) is 2 10^6 , so they are okay with sizes 2 10^6 however I am unsure as to how it works for g[], If someone who understands the logic explains it, then it would be awesome 
1 Like