关于大数据的C(M,N)

发表于 更新于 分类于 阅读次数：

     cf181 div 2的C题http://codeforces.com/contest/300/problem/C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long long cal(long long s)//s^(MOD-2)
{
     long long ans=1;
     long long n=MOD-2;
     while (n!=0)
     {
         if (n&1) ans=ans*s%MOD;
         s=s*s;
         n=n>>1;
     }
     return ans;
}

long long C(int m,int n)//f[x]=x! 求的是C(m,n)
{
     return f[m]*cal(f[n]*f[m-n]%MOD)%MOD;
}

//CF181D2C 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MOD 1000000007
using namespace std;

int a,b,n;
long long f[1000001]={0};

long long power(long long s)
{
    long long n=MOD-2;
    long long ans=1;
    while (n!=0)
    {
        if (n&1) ans=(ans*s)%MOD;
        s=(s*s)%MOD;
        n=n>>1;
    }
    return ans%MOD;
}

long long C(int n,int i)
{
    return f[n]*power(f[n-i]*f[i]%MOD);
}

bool check(int s)
{
    while (s!=0)
    {
        int t=s%10;
        if (t!=a && t!=b) return false;
        s=s/10;
    }
    return true;
}

int main()
{
    scanf("%d%d%d",&a,&b,&n);
    f[0]=1;
    for (int i=1;i<n+1;i++){
      f[i]=(i*f[i-1])%MOD;
    }
    long long ans=0;
    for (long long i=0;i<=n;i++)
    {
        if (check(i*a+(n-i)*b)){ans=(ans+C(n,i))%MOD;}
    }
    printf("%d",ans);
    return 0;
}