fork download
copy 
  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
comments (?)
stdin
copy 
1
1 10000000000000000000000000000000000000000000000000
stdout
copy 
21790326
https://ideone.com/VnPIZp
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!