Problem 6: Sigma Sigma Everywhere

Points:

Small Case: 5 Answer: 64332645

Large Case: 10 Answer: 33570795

Given the values of n, p, i and j, Find

where

Small Case: n=100, p=5, i=3, j=2
Large Case: n=10000, p=200, i=50, j=40

Solution:

The above summation is given by:

Reference: Journal of Integer Sequences, Vol. 13 (2010), Article 10.4.4, Section 2

Code:

#include<iostream>

#include<cmath>

using namespace std;



#define MOD 100000007



int primes[1253]={2, 3, 5, 7, 11, 13, 17, 19, 23};



void genPrime(){

	int n=4,k,count=0;

	float check;

	bool flag=false;

	for(int i=9;i<=10200;i+=2)

	{

		check=sqrt((double)i);

	        for(k=0;primes[k]<=check;k++)

	        {

	          if(i%primes[k]==0)

	          {

	             flag=false;

	             break;

	          }

	          else

	             flag=true;

	       }

       if(flag==true){

          primes[n++]=i;

          }

       }

	primes[n]=10211;

}



long long nck(int n, int k)

{

	long long int result=1LL;

	long long int  tempn,tempk,tempnk,i,j;

	long long int  count[1252]={0};

	for(i=0;i<1252 && primes[i]<=n;i++){

		tempn=n;

		tempk=k;

		tempnk=n-k;

		while(tempn!=1 && primes[i]<=tempn){

			tempn=tempn/primes[i];

			count[i]+=tempn;

			}

		while(tempk!=1 && primes[i]<=tempk){

			tempk=tempk/primes[i];

			count[i]-=tempk;

			

		}

		while(tempnk!=1 && primes[i]<=tempnk){

			tempnk=tempnk/primes[i];

			count[i]-=tempnk;

		}

	}

	for(j=0;j<i;j++){

		long long int  po;

		if(count>0){

			po=(long long int )(pow((double)primes[j],(double)count[j]));

			result=(result*(po%MOD))%MOD;

		}

	}

	

return result;

}



int main(){

	long long int n,p,i,j,ans;

	n=10000, p=200, i=50, j=40;

	genPrime();

	ans=(nck(j+i-1,i-1)*nck(n+p,p+j))%MOD;

	cout<<ans<<endl;

	return 0;

}