【链接】 我是链接,点我呀:)
【题意】
让你找到长度为n的数字
这个数字只由a或者b组成
且这n个数码的和也是由a或者b组成的
求出满足这样要求的数字的个数
【题解】
枚举答案数字中b的个数为y,那么a出现的个数就为n-y
那么和就是na + (b-a)y;
这个数字最多就7位的样子
很容易检查是不是只包含a或者b
然后如果满足只包含a或者b
则答案加上C(n,y)
即n个位置中选择y个放b,其他的放a
组合数取余的话,预处理一下阶乘以及阶乘的逆元就好
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = (int)1e6;
static class Task{
long MOD = (int)1e9+7;
int a,b,n;
long fac[],rfac[];
long _pow(long x,long y) {
long ans = 1;
while (y>0) {
if (y%2==1) ans = (ans * x)%MOD;
x = (x*x)%MOD;
y/=2;
}
return ans;
}
long C(int n,int m) {
//n!/((n-m)!*m!)
if (n<m) return 0;
long temp1 = fac[n];
temp1 = temp1*rfac[n-m]%MOD;
temp1 = temp1*rfac[m]%MOD;
return temp1;
}
boolean ok(int x) {
if (x==0) return false;
while (x>0) {
int temp = x%10;
if (temp!=a && temp!=b) return false;
x = x/10;
}
return true;
}
public void solve(InputReader in,PrintWriter out) {
fac = new long[N+10];
rfac = new long[N+10];
fac[0] = 1;
for (int i = 1;i <= N;i++) fac[i] = fac[i-1]*i%MOD;
rfac[N] = _pow(fac[N],MOD-2 );
for (int i = N-1;i >= 0;i--) {
rfac[i] = rfac[i+1]*(i+1)%MOD;
}
a = in.nextInt();b = in.nextInt();n = in.nextInt();
long ans = 0;
for (int y = 0;y <= n;y++) {
//b有y个
int sumdigits = n*a + (b-a)*y;
if (ok(sumdigits)) {
ans = ans + C(n,y);
ans = ans % MOD;
}
}
out.println(ans);
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}