Problem 7: Equation in Combinations

Points:

Small Case: 5 Answer: 76919904

Large Case: 10 Answer: 99989016

Given an equation

There are various values of (a,b) as (a[i],b[i]) which satisfy it with a[i]+b[i]>a[i-1]+b[i-1]

For e.g first such pair is (2,1)

Given n,find sum of nth such pair modulo 100000007 i.e (a[n]+b[n]) mod 100000007.

Small Case: n=100
Large Case: n=100000000

Solution:

The recurrence relation of a and b are:

a[n]=6*a[n-1]-a[n-2]+6

b[n]=6*b[n-1]-b[n-2]

Code:

#include<iostream>
#define MOD 100000007
using namespace std;

int main(){
	long long int n;
	long long int a,b,a1,b1,a2,b2;
	n=100;
	a2=2;
	a1=19;
	b2=1;
	b1=6;
	for(int i=2;i<n;i++){
		a=((6*a1)%MOD-a2+MOD+6)%MOD;
		b=((6*b1)%MOD-b2+MOD)%MOD;
		a2=a1;		
		a1=a;
		b2=b1;
		b1=b;
	}
	cout<<(a+b)%MOD<<endl;
	return 0;	
}