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)
{
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)
{
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
54
55
| #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;
}
|