题目大意：
给出a和b，假设一个数每一位都是a或b，那么我们称这个数为good，在good的基础上，假设这个数的每一位之和也是good，那么这个数是excellent。求长度为n的excellent数的个数mod(1e9+7)。ps：1e9+7是一个质数。
解题思路：
因为题目中给出了n，所以我们能够枚举a的个数m，那么剩下的（n-m）位就是b。再推断a*m+b*(n-m)是不是good数，假设是。那么我们在答案中加上C(m,n)就可以，枚举完成即终于答案。
可是n最大为1e6，计算组合数时(C(m,n)=n!/(m!*(n-m)!))要计算n的阶乘。直接计算肯定会出现错误。
在这里介绍一些数学知识：
（1）费马小定理
费马小定理(Fermat Theory)是数论中的一个重要定理。其内容为： 假如p是质数，且Gcd(a,p)=1。那么 a(p-1)（mod p）≡1。
即：假如a是整数，p是质数，且a,p互质(即两者仅仅有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
简而言之就是假设a，p互质，同一时候p是质数。那么a^(p-1) mod p=1。证明略。
（2）乘法逆元
若对于a，p存在x。使得a*x mod p=1。那么我们称x为a对p的乘法逆元。证明略。
那么乘法逆元存在的意义是什么呢？
假如我们要求(a/b) mod p且无法直接求得a/b的值时，我们能够求出b对p的乘法逆元inv，那么(a/b) mod p=(a*inv) mod p。
证明例如以下:
假如inv是b对于p的乘法逆元，即b*inv=p*t+1（t为整数），移项得inv=(p*t+1)/b
(a*inv) mod p
=(a*((p*t+1)/b)) mod p
=(a*(p*t/b+1/b)) mod p
=(a/b) mod p+(a*(p*t+1)) mod p
=(a/b) mod p+(a*p*t/b) mod p
∵ (a*p*t/b) mod p=0
∴ 原式=(a/b) mod p
即(a*inv) mod p=(a/b) mod p
有了这2个概念我们就能够高速地算出组合数了。
我们能够知道x与x^p-2互为逆元（p是质数）。
/*
证明：x与x^(p-2)互为逆元（p是质数）
由费马小定理：x^(p-1) mod p=1
x*(x^(p-2)) mod p=1
得x与x^(p-2)互为乘法逆元。证毕。
*/
由上述结论可知，要计算C(i,n)。即计算n!/(i!*(n-i)!) mod p，那么我们仅仅须要计算n!*(i!*(n-i))^(p-2) mod p。
參考代码：
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double eps=1e-10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int MAXN=1e6+50;
typedef __int64 LL;
LL f[MAXN],a,b,n;
bool is_excellent(int x)
{
while(x)
{
if(x%10!=a&&x%10!=b)
return false;
x/=10;
}
return true;
}
LL fastmod(LL b,LL c,LL mod)//b^c%mod
{
LL re=1,base=b;
while(c)
{
if(c&1)
re=((re%mod)*(base%mod))%mod;
base=((base%mod)*(base%mod))%mod;
c>>=1;
}
return re%mod;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
f[0]=1;
f[1]=1;
for(int i=2;i<=1e6;i++)
f[i]=(f[i-1]*i)%MOD;
while(scanf("%I64d%I64d%I64d",&a,&b,&n)!=EOF)
{
LL ans=0;
for(int i=0;i<=n;i++)
{
int num=a*i+b*(n-i);
if(is_excellent(num))
{
//DEBUG;
LL t=f[n];
t=(t*fastmod(f[i],MOD-2,MOD))%MOD;
t=(t*fastmod(f[n-i],MOD-2,MOD))%MOD;
ans=(ans+t)%MOD;
}
}
printf("%I64d
",ans%MOD);
}
return 0;
}