# Clash of Coders CLCO02 - Editorial

Practice

Contest

Author: Nikhil Khurana

Tester: Rahul Johari

MEDIUM

### PREREQUISITES:

Multiplicative Inverse, DP, Maths.

### PROBLEM:

Given two distinct integers A and B, a number is called “lucky” if it contains only digits A and B. Another number is called “superlucky” if the sum of its digits is “lucky”.

For a given integer N (length of number), find how many superlucky numbers of length exactly N are there. Output the result modulo 109+7.

### EXPLANATION:

Let MOD = 1000000007. Let’s precalculate factorial values using modulo MOD.

Fact[i] = i! % MOD, Let i be an amount of digits equal to A in current superlucky number. In this case we can find sum of digits in this number as : sum = Ai + B(n-i).

If sum is lucky, then add C[N][i] to answer. In this problem it’s impossible to calculate binomial coefficients using Pascal’s triangle, because of large N. However it can be done this way
C[n][i] = fact[n]inv(fact[n - i]fact[i]).

Inv(a) is [multiplicative inverse element(modulo MOD)].
Observe that MOD is a prime number, so inv(a) = aMOD - 2. Calculating this values for each i from 0
to N will give correct answer in O(Nlog(MOD)).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

1 Like