Can someone please help me out with the approach of DSERIES problem from LOC MAY 18.
@abhi_1595 @vijju123 please post editorial of this problem 
Link to problem : DSERIES
If no1 answers, I will ahve a look tomorrow. A little busy right now.
T(n)=(n+1)*(n+2)…(n+T)
Define V(n) by taking an extra term to the right
V(n)=(n+1)(n+2)(n+3)…(n+T)*(n+T+1)
V(n-1)=(n)(n+1)(n+2)…(n+T-1)*(n+T)
V(n)-V(n-1)=(n*(n+1)(n+2)…(n+T))[n+T+1-n]
V(n)-V(n-1)=(n*(n+1)(n+2)…(n+T))(T+1)
V(n)-V(n-1)=(T+1)*T(n)
T(n)=(V(n)-V(n-1))/(T+1)
now summation of the series
Summation(T(i)(i=1; i<=n;++i))=(((V1-V0)+(V2-V1)+(V3-V2)…(Vn-V(n-1)))/(T+1)
on Simplifying This come out to be
Summation(T(i)(i=1; i<=n;++i))=(V(n)-V(0))/(T+1)
sum of the series=(V(n)-V(0))/(T+1)
V(n) and V(0) can be calcualted in O(T)
Take difference of V(n),V(0) with mod in cosideration and multiply it with inverse modulo of (T+1).
you get the Sum of the series (i.e. What is asked in the question)
This method is known as V(n)-V(n-1) method used for solving Such types of Series.
2 Likes
why inverse modulo of (T+1) is calculated can we simply cant divide (T+1) please answer i want to know why @vijju123
this is my code but it was showing TLE
#include<iostream>
using namespace std;
long long int mod=1000000007;
int main()
{
int q;
cin>>q;
long long int n,t;
while(q--)
{
cin>>n>>t;
long long int s=0,p1=1,p2=1; bool a=0;
for(int i=1;i<=t+1;++i)
{
if((n+i)%(t+1)==0 && a==0)
{ p1*=((n+i)/(t+1))%mod; a=1;}
else p1*=(n+i)%mod;
p1=p1%mod;
if(i==t+1) continue;
p2*=i%mod;
p2=p2%mod;
}
s=p1-p2;
while(s<0)
{ s+=mod;}
s%=mod;
cout<<"\n"<<s;
}
}
and this is one of my friends code and it has shown AC although we both are doing same thing except that he has used modulo inverse for t+1 while i have simply divided it from the element of the series from which it was divisible…infact my program runs for less no of loops than that of my friend…still showing TLE
#include<bits/stdc++.h>
using namespace std;
long long int power(long long int x, unsigned long long int y, unsigned long long int m);
long long int modInverse(long long int a,long long int m)
{
long long int d;
d= power(a, m-2, m);
return d;
}
// To compute x^y under modulo m
long long int power(long long int x, unsigned long long int y, unsigned long long int m)
{
if (y == 0)
return 1;
long long int p = power(x, y/2, m) % m;
p = (p * p) % m;
return (y%2 == 0)? p : (x * p) % m;
}
int main()
{
int q;
cin>>q;
long long int n,i,t;
while(q--)
{
long long int fac=1,c=1000000007, p=1,a=1,b;
cin>>n>>t;
for(i=1;i<=t+1;i++)
{
if(i!=0 && i!=t+1)
fac=(fac*i)%c;
p=(p*((n+i)%c))%c;
}
b=modInverse(t+1,c);
a=(p*b)%c;
//cout<<fac<<" "<<p<<" "<<" "<<b<<" "<<a<<endl;
if((a-fac)>=0)
cout<<a-fac<<endl;
else
cout<<(a-fac)+c<<endl;
}
return 0;
}
please tell me whats wrong in my code
Well i reached to final expression in diferrent way!!
after expansion :
(1+1)(1+2)(1+3)…(1+T)+(2+1)(2+2)(2+3)…(2+T)…
=2 * 3 * 4…(1+T)+3 * 4 * 5…(2+T)…
=fact[1+T] / fact[1]+fact[2+T] / fact[2]+fact[3+T] / fact[3]
multiply and divide by fact[T]
we’ll get
fact[T]* (C(1+T,T)+C(2+T,T)+C(T+3,T))
=fact[T]*(C(n+1+T,T+1)-1)
=(n+1)(n+2)…(n+T+1)/(T+1)-fact[t]
1 Like
Dear @incognito_nag , Your code is perfect if you include just one line after cin>>n>>t; statement that line is n%=c;, and it is for your second code.
thanks @meet2mky for answering… I really appreciate that… I understood why i should add that line but it would do no good as TLE was due to more no. of iterations which has no corelation with ‘n’…and thats why even after adding that line TLE was coming