fork download
  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
stdin
3
121 4325
432 4356
4234 4325667
stdout
60
58
207159