1 3 3

1

2 3 10

165

题目大意：

给出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\n",ans%MOD);

    }

    return 0;

}