fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef signed long long ll;
  5. const ll mod = 1000000007;
  6. ll dp[51][2][21][21][21];
  7.  
  8. ll solve(char num[], int pos, int top, int three, int six, int nine){
  9. 	if(pos == strlen(num)) return (three && (three == six) && (six == nine));
  10. 	if(dp[pos][top][three][six][nine] != -1) return dp[pos][top][three][six][nine];
  11. 	ll ans = 0;
  12. 	int lim = top ? (num[pos] - '0'): 9;
  13. 	for(int i = 0; i<=lim; i++){
  14. 		ans = (ans + solve(num, pos+1, top && (i == lim), min(three + (i == 3), 20), min(six + (i == 6), 20), min(nine + (i == 9), 20))%mod)%mod;
  15. 	}
  16. 	return dp[pos][top][three][six][nine] = ans;
  17. }
  18.  
  19. int main() {
  20. 	int t;
  21. 	scanf("%d", &t);
  22. 	char a[55],b[55];
  23. 	for(int i = 1; i<=t; i++){
  24. 		scanf("%s %s", a, b);
  25. 		ll three = 0, six = 0, nine = 0;
  26. 		for(int j = 0; j<strlen(a); j++){
  27. 			three += (a[j] == '3'); six += (a[j] == '6'); nine += (a[j] == '9');
  28. 		}
  29. 		memset(dp,-1,sizeof(dp));
  30. 		ll ans = solve(b,0,1,0,0,0); 
  31. 		memset(dp,-1,sizeof(dp));
  32. 		ans = (ans - solve(a,0,1,0,0,0) + (three && (three == six) && (six == nine)))%mod;
  33. 		ans = (ans + mod)%mod;
  34. 		printf("%lld\n", ans);
  35. 	}
  36. 	return 0;
  37. }
Success #stdin #stdout 0s 10856KB
comments (?)
stdin
copy 
3
121 4325
432 4356
4234 4325667
stdout
copy 
60
58
207159
https://ideone.com/7fKLqx
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!