Count sequence -wa

general
,
1

#include<stdio.h>
#define M 1000003

int main(){

  int t=0;
  long long int sum=0,L,R,N,init=0,i=0,Len=0;
  scanf("%d",&t);
  while(t-- > 0){
      scanf("%lld%lld%lld",&N,&L,&R);
            
    Len=R-L+1;
    
    if(R==L){
             
       printf("%lld\n",N%M);
    }
    else{
       init=Len%M;
       
       sum=init;
       if(N>Len)
          N=Len%M;
       for(i=2;i<=N;i++){
       
           init=((((init%M)*(((Len%M)+(i%M)-(1%M))%M))%M)/(i%M))%M;
      
    
           //printf("%lld",init);
           sum=(sum%M+init%M)%M;
      }
    
       printf("%lld\n",sum);
       sum=0;
    }
   
}
//getch();
return 0;

}

I HAVE USED THE FORMULA (R-L+r,r) where 1<=r<=N.
I have broken the the aboe using (n+1,k)=(n,k)+(n,k-1);
WHAT wrong In My code??

2

Hi, I’m not 100% sure, but I think the division is your problem. When you are working with modulo operation, the division is not working the way you think.

For example: (10^6+4) / 2 == 5*10^5 + 2, but ((10^6+4)%M) / (2%M) == 1 / 2 == 0

I think you should check the Modulat Multiplicative Inverse or Fermat’s Little Theorem.

3

Perhaps yours formula is wrong.

Correct one is

Summation of (Leng+r-1,r) over r where r varies from 1 to N.

Leng=R-L+1.

This will give you tle as you will iterate over each r.

So you can convert this into non iterative.

Ans is (leng+N,N)-1.

Where leng =r-l+1.
and N is given length of sequence.
You can solve it using Lucas.