fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mp make_pair
  5. #define ff first
  6. #define ss second
  7. #define sz(x) (int)(x.size())
  8. #define all(a) a.begin(), a.end()
  9. #define INF numeric_limits<long long>::max()
  10. #define oo numeric_limits<int> :: max()
  11. #define CLR(s) memset(s, false, sizeof(s))
  12. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  13. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  14. #define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
  15. #define DBG(s) cerr << #s << " == > " << s << endl
  16. #define trace5(a,b,c,d,e) cerr<<#a<<" == > "<<a<<" "<<#b<<" == > "<<b<<" "<<#c<<" == > "<<c<<" "<<#d<<" == > "<<d<<" "<<#e<<" == > "<<e<<endl
  17. typedef long long lld;
  18. typedef vector <int> vi;
  19. typedef pair< int, int > pii;
  20. typedef vector <pii> vpii;
  21. #define MOD 1000000007
  22. #define MA 100
  23. int dp[54][2][18][18][18];
  24. vi a;
  25. int num;
  26. int solve(int index, int free, int t,int s, int n)
  27. {
  28. if(t > 17 || s > 17 || n > 17) return 0;
  29.  
  30. //DBG(index);
  31. if(index == num)
  32. {
  33. //DBG(index);
  34. if(t >= 1 && (t == s) && (s == n))
  35. return 1;
  36. return 0;
  37. }
  38. int &ret = dp[index][free][t][s][n];
  39. if(ret != -1) return ret;
  40. ret = 0;
  41. int nfree,nt,ns,nn;
  42. for(int i = 0; i < 10; i++)
  43. {
  44. nfree = free | (i < a[index]);
  45. nt = t + ( (i == 3) ? 1 : 0); //DBG(nt);
  46. ns = s + ( (i == 6) ? 1 : 0); //DBG(ns);
  47. nn = n + ( (i == 9) ? 1 : 0); //DBG(nn);
  48. if(free)
  49. {
  50. ret = ((ret % MOD) + (solve(index+1, nfree, nt, ns, nn)) % MOD) % MOD;
  51. }
  52. else
  53. {
  54. if( i <= a[index])
  55. ret = (ret % MOD + (solve(index+1, nfree, nt, ns, nn)) % MOD ) % MOD;
  56. }
  57.  
  58. }
  59.  
  60. return (ret% MOD);
  61. }
  62. void convert(char* m)
  63. {
  64. a.clear();
  65. int l = strlen(m);
  66. for(int i = 0; i < l; i++)
  67. a.pb( (m[i] - '0'));
  68. //reverse(all(a));
  69. num = sz(a);
  70. }
  71.  
  72. void decrement(char* s)
  73. {
  74. int l = strlen(s)-1;
  75. int g = s[l] - '0';
  76. int b = 0;
  77.  
  78. if(g != 0)
  79. {
  80. g--;
  81. s[l] = g + '0';
  82. }
  83. else
  84. {
  85. g = 9;
  86. s[l] = g + '0';
  87. l--; b = 1;
  88. }
  89. while( b != 0 && l >= 0)
  90. {
  91. int g = s[l] - '0';
  92. if( g != 0)
  93. {
  94. g --;
  95. s[l] = g + '0';
  96. b = 0;
  97. }
  98. else
  99. {
  100. g = 9;
  101. s[l] = g + '0';
  102. b = 1; l--;
  103. }
  104. }
  105.  
  106.  
  107. }
  108. int main()
  109. {
  110. int te; cin >> te;
  111. while(te--)
  112. {
  113. char x[MA],y[MA]; cin >> x >> y;
  114. decrement(x);
  115. //int l = strlen(x);
  116. /*for(int i = 0; i < l; i++)
  117. cout << x[i];
  118. cout << endl;*/
  119. convert(x);
  120. memset(dp,-1,sizeof dp);
  121. int ans1 = solve(0,0,0,0,0);
  122.  
  123. convert(y);
  124. memset(dp,-1,sizeof dp);
  125. int ans2 = solve(0,0,0,0,0);
  126. cout << ((ans2 - ans1)%MOD+MOD)%MOD << endl;
  127. }
  128. return 0;
  129. }
  130. /*
  131. 4
  132. 767675 767676
  133. 0
  134. 5656565556566565 656756655454665657666666666666666666666666666666
  135. -208860808
  136.  
  137. 656756655454665657666666666666666666666666666666
  138. */
  139.  
Success #stdin #stdout 0.05s 5284KB
stdin
1
1 10000000000000000000000000000000000000000000000000
stdout
21790326