Approach for DSERIES LOC May18

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 :slight_smile:

Link to problem : DSERIES

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.

@code__champ Read This : Modular Divison

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

If no1 answers, I will ahve a look tomorrow. A little busy right now.