SHARE
TWEET

C

a guest Apr 25th, 2013 2,059 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _SECURE_SCL 0
  3. #pragma comment(linker, "/STACK:200000000")
  4.  
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <cassert>
  8. #include <cctype>
  9. #include <complex>
  10. #include <ctime>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <deque>
  15. #include <functional>
  16. #include <fstream>
  17. #include <iostream>
  18. #include <map>
  19. #include <memory.h>
  20. #include <numeric>
  21. #include <iomanip>
  22. #include <queue>
  23. #include <set>
  24. #include <stack>
  25. #include <list>
  26. #include <string>
  27. #include <sstream>
  28. #include <vector>
  29. #include <utility>
  30. #include <cmath>
  31. using namespace std;
  32.  
  33. #define pb push_back
  34. #define mp make_pair
  35. #define mset(mas,val) memset(mas,val,sizeof(mas))
  36. #define sz(a) (int)(a).size()
  37. #define all(a) (a).begin(), (a).end()
  38. #define rall(a) (a).rbegin(), (a).rend()
  39.  
  40. #define forn(i,n) for (int i=0; i<int(n); ++i)
  41. #define fornd(i,n) for (int i=int(n)-1; i>=0; --i)
  42. #define forab(i,a,b) for (int i=int(a); i<int(b); ++i)
  43.  
  44. typedef long long ll;
  45. typedef long double ld;
  46. typedef unsigned long long ull;
  47.        
  48. const int INF = (int) 1e9;
  49. const long long INF64 = (long long) 1e18;
  50. long double eps = 1e-6;
  51. const long double pi = 3.14159265358979323846;
  52.  
  53. const int N = 1e6 + 100;
  54. long long fact[N], modulo = INF + 7;
  55. int n, a, b;
  56. bool read()
  57. {
  58.         if (!(cin >> a >> b >> n))
  59.                 return false;
  60.         assert(a >= 1 && a <= 9);
  61.         assert(b >= a + 1 && b <= 9);
  62.         assert(n >= 1 && n <= (int)1e6);
  63.         return true;
  64. }
  65. long long binpow(long long val, long long deg, long long mod) {
  66.         if (!deg) return 1 % mod;
  67.         if (deg & 1) return binpow(val, deg - 1, mod) * val % mod;
  68.         long long res = binpow(val ,deg >> 1, mod);
  69.         return (res*res) % mod;
  70. }
  71. bool check(long long val, int a, int b) {
  72.         while (val > 0) {
  73.                 if (val % 10 == a || val % 10 == b) {
  74.                         val /= 10;
  75.                 } else return false;
  76.         }
  77.         return true;
  78. }
  79. void initfact() {
  80.         fact[0] = 1;
  81.         for(int i = 1; i < N; i++) {
  82.                 fact[i] = (fact[i-1] * i);
  83.                 fact[i] %= modulo;
  84.         }
  85. }
  86. long long getC(int n, int i) {
  87.         long long res = fact[n];
  88.         long long div = fact[n-i] * fact[i];
  89.         div %= modulo;  div = binpow(div, modulo - 2, modulo);
  90.         return (res * div) % modulo;
  91. }
  92. void solve()
  93. {
  94.         long long ans = 0;
  95.         for(int i = 0; i <= n; i++) {
  96.                 long long expsum = a * i + b*(n-i);
  97.                 if (check(expsum, a, b)) {
  98.                         ans += getC(n, i);
  99.                         ans %= modulo;
  100.                 }
  101.         }
  102.         cout << ans << endl;
  103. }
  104.  
  105. int main(){
  106. #ifdef gridnevvvit
  107.         freopen("input.txt","rt",stdin);
  108.         freopen("output.txt","wt",stdout);
  109. #endif
  110.         initfact();
  111.         assert(read());
  112.         solve();
  113.         return 0;
  114. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top