Please help to solve this problem related to Maths

general
1

Problem Link

My approach :-

  1. A nice number is one which has only ‘a’ and ‘b’ as its digits. And if sum of all digits of a nice number is also nice than it is known as very nice number. We have to make a number of n digits . Let ta be the number of ‘a’ digit and tb be the number of ‘b’ digit. Note for a nice number ta+tb = n .

  2. So for ta equal to 0 to n we will find all the possible sum .

  3. Then we will check if each sum is a nice number or not. if its nice than we have a total of nCta possible combination for a and b for a particular nice sum .

  4. final ans will be total of nCta for all the nice sum.

My Code :-

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007


int checkNice(ll sum,ll a,ll b)
{
	while(sum>0)
	{	ll z = sum%10;
		if(z!=a&&z!=b)
			return 0;
		sum/=10;
	}
	return 1;
}

ll fact(ll x )
{
	ll ans=1;
	while(x>0)
	{
		ans=(ans*x)%mod;
		x--;
	}
	return ans ; 
}

ll findNum(ll n,ll upto )
{
	ll ans = 1; 
	for(ll g=n;g>upto;g--)
	{
		ans=(ans*g)%mod; 
	}
	return ans ; 
}


int main()
{
	ll t; cin>>t; 
	for(int i=0;i<t;i++)
	{
		ll a,b,n;
		cin>>a>>b>>n;

		ll ans =0;
		if(n==1)
		{
			cout<<2<<endl;
		}
		else 
		{
			// n is the position that we have to fill with 
			// a and b 

			for(ll g=0;g<=n;g++)
			{
				ll ta,tb; 
				ta=g; tb=(n-g);
				ll sum=0;
				sum = ta*a+tb*b; 
				int flag = checkNice(sum,a,b);
				//cout<<"flag is "<<flag<<endl;
				if(flag==1)
				{
					ll fact1=n, fact2 = ta, fact3 =n-ta;

					ll upto = (fact3>fact2)? fact3:fact2;

					ll den = (fact3>fact2)? fact2:fact3;

					//cout<<"upto and den are "<<upto<<" "<<den<<endl;

					ll down = fact(den); 

					ll up = findNum(n,upto);


					 ans = (ans+up/down)%mod;
				}
			}
			cout<<ans<<endl;
		}
	}
	
}