PROBLEM LINK:
Author: Nikhil Khurana
Tester: Rahul Johari
DIFFICULTY:
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)][5].
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.