fork(4) download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <cstring>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <string>
  12. #include <functional>
  13. #include <numeric>
  14. #include <utility>
  15. #include <sstream>
  16. #include <iostream>
  17. #include <iomanip>
  18. #include <cstdio>
  19. #define REP(i,n)for(int i=0;i<n;i++)
  20. #define REPP(i,n)for(int i=1;i<=n;i++) 
  21. #include <cmath>
  22. #include <cstdlib>
  23. #include <ctime>
  24. #define ll long long
  25. using namespace std;
  26.  
  27. const int NN = 170;
  28. #define MOD 1000000007
  29. //dig three six nine
  30.  
  31. ll dp[52][52][52][52];
  32.  
  33. const int SZ = 200;
  34. int N, M;
  35.  
  36. ll LP[SZ + 1];
  37. vector<ll>pr;
  38. void SV(){
  39. 	for (int i = 2; i <= SZ; i++){
  40. 		if (LP[i] == 0){
  41. 			LP[i] = i;
  42. 			pr.push_back(i);
  43. 		}
  44.  
  45. 		for (int j = 0; j < pr.size() && pr[j] <= LP[i] && i*pr[j] <= SZ; j++){
  46. 			LP[i*pr[j]] = pr[j];
  47. 		}
  48. 	}
  49.  
  50. }
  51.  
  52.  
  53. #define PS system("pause")
  54. #define exit return 0
  55.  
  56. ll go(int dig, int thr, int six, int nine){
  57. 	if (dig == 0){
  58. 		if (thr == six&&six == nine&&thr > 0)return 1;
  59. 		return 0;
  60. 	}
  61.  
  62. 	if (dp[dig][thr][six][nine] != -1)return dp[dig][thr][six][nine];
  63.  
  64. 	ll res = 0;
  65.  
  66. 	for (int i = 0; i <= 9; i++){
  67. 		if (i == 3){
  68. 			res += go(dig - 1, thr + 1, six, nine);
  69. 			res %= MOD;
  70. 		}
  71. 		else if (i == 6){
  72. 			res += go(dig - 1, thr, six + 1, nine);
  73. 			res %= MOD;
  74. 		}
  75. 		else if (i == 9){
  76. 			res += go(dig - 1, thr, six, nine + 1);
  77. 			res %= MOD;
  78. 		}
  79. 		else res += go(dig - 1, thr, six, nine);
  80. 		res %= MOD;
  81. 	}
  82. 	res %= MOD;
  83. 	dp[dig][thr][six][nine] = res;
  84. 	return dp[dig][thr][six][nine];
  85. }
  86.  
  87. ll doit(char in[]){
  88. 	int three = 0;
  89. 	int six = 0;
  90. 	int nine = 0;
  91. 	ll pas = 0LL;
  92. 	int len = strlen(in);
  93. 	int cur_len = len;
  94. 	for (int i = 0; i < len; i++){
  95. 		cur_len -= 1;
  96. 		int D = in[i] - '0';
  97. 		for (int j = 0; j < D; j++){
  98. 			if (j == 3){
  99. 				pas = (pas + go(cur_len, three + 1, six, nine)) % MOD;
  100. 			}
  101. 			else if (j == 6){
  102. 				pas = (pas + go(cur_len, three, six + 1, nine)) % MOD;
  103. 			}
  104. 			else if (j == 9){
  105. 				pas = (pas + go(cur_len, three, six, nine + 1)) % MOD;
  106. 			}
  107. 			else{
  108. 				pas = (pas + go(cur_len, three, six, nine)) % MOD;
  109. 			}
  110.  
  111. 		}
  112. 		if (D == 3)three += 1;
  113. 		if (D == 6)six += 1;
  114. 		if (D == 9)nine += 1;
  115. 	}
  116. 	pas %= MOD;
  117. 	return pas;
  118. }
  119.  
  120.  
  121. int tst;
  122.  
  123. int main() {
  124. 	//SV();
  125. 	memset(dp, -1, sizeof(dp));
  126. 	scanf("%d", &tst);
  127. 	while (tst--){
  128. 		char F[60], S[60];
  129. 		cin >> F >> S;
  130. 		int a, b, c;
  131. 		a = b = c = 0;
  132. 		for (int i = 0; i < strlen(S); i++){
  133. 			if (S[i] == '3')a++;
  134. 			if (S[i] == '6')b++;
  135. 			if (S[i] == '9')c++;
  136. 		}
  137. 		int p = 0;
  138. 		/*if (a == b && b == c && c>0){
  139. 			p = 1;
  140. 		}*/
  141. 		printf("%lld\n", ((doit(S) - doit(F)) + p) % MOD);
  142. 	}
  143. 	//PS;
  144. 	exit;
  145.  
  146. }
Success #stdin #stdout 0.06s 60584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ycnepw
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!