题目

小A有两个幸运数字字符a和b。他认为一个数很美当且仅当这个数字只包含字符a和b，且这个数字没位数字之和也只包含数字字符a和b。例如：幸运数字字符为1和2，那么11就很美，其每位数字之和为2,11和2都只含有数字字符1和2,。但是12、21、111都不美，虽然它们本身都只含有数字字符1和2，但它们的每位数字之和都为3，而3不是幸运数字字符。
现在小A想知道对于所有的k位数字，有多少个美丽的数字？

输入描述

一行包含3个数字，a、b和k，其中。
对于10%的数据：
对于20%的数据：
对于100%的数据：

输出描述

一行包含一个数字，即美丽的数字个数。由于答案可能很大，请对取模。

解题思路

思路一：暴力法

枚举所有的k位数字，判断是否为美丽的数字，得到所有符合条件的解的个数.

思路二：组合法

已知k位数字只包含数字字符a和b，根据题意可知，一个数字是否美丽只和其包含a和b的个数有关，因此可以先判断出包含m个a字符的数字是否为美丽的数字，其中。得到相应的。最终美丽的数字个数为。

示例代码

import math

k = 2
digit_a = 1
digit_b = 2
result = 0


def c(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n - r)


def is_beautiful(number, a, b):
    if number == 0:
        return False
    while number != 0:
        digit = number % 10
        if digit != a and digit != b:
            return False
        number //= 10
    return True


for i in range(k + 1):
    temp = i * digit_a + (k - i) * digit_b
    if is_beautiful(temp, digit_a, digit_b):
        result += c(k, i)
result = result % 1000000007
print(result)