fork download
copy 
  1. #include "bits/stdc++.h"
  2. #define ll long long
  3. #define pb push_back
  4. using namespace std;
  5.  
  6. const ll mod = 1e9 + 7;
  7.  
  8. ll num[100006][10][2], dp[100006][10][2]; // dp[index][digit][equal_or_not] - the sum of f(x) up to index, such that the last digit is digit and it is still equal to the initial number iff equal_or_not == 1
  9. ll p[100006];
  10. ll t;
  11.  
  12. void add(ll &x, ll val)
  13. {
  14. 	x += val;
  15. 	if (x >= mod)
  16. 		x -= mod;
  17. }
  18.  
  19. pair<ll, ll> f(vector<ll> vec) // pair<sum of all f less than x,sum of all f less than or equal to x>
  20. {
  21. 	for (ll idx = 0; idx <= vec.size(); idx++)
  22. 	{
  23. 		for (ll digit = 0; digit < 10; digit++)
  24. 		{
  25. 			for (ll equal = 0; equal < 2; equal++)
  26. 			{
  27. 				dp[idx][digit][equal] = num[idx][digit][equal] = 0;
  28. 			}
  29. 		}
  30. 	}
  31.  
  32. 	num[0][0][1] = 1;
  33. 	for (ll idx = 0; idx < vec.size(); idx++)
  34. 	{
  35. 		for (ll digit = 0; digit < 10; digit++)
  36. 		{
  37. 			for (ll equal = 0; equal < 2; equal++)
  38. 			{
  39. 				ll idx_next = idx + 1;
  40. 				for (ll next_digit = 0; next_digit < 10; next_digit++)
  41. 				{
  42. 					if (equal && (next_digit > vec[idx]))
  43. 						break;
  44. 					ll equal_next = (equal & (next_digit == vec[idx]));
  45. 					add(num[idx_next][next_digit][equal_next], num[idx][digit][equal]);
  46. 					add(dp[idx_next][next_digit][equal_next], dp[idx][digit][equal]);
  47. 					if (next_digit != digit)
  48. 						add(dp[idx_next][next_digit][equal_next], (((num[idx][digit][equal] * p[(vec.size() - 1 - idx)]) % mod) * next_digit) % mod);
  49. 					// ^^ if the next digit is equal to the current one, we shouldn't change the sum, else we should add 10^idx * next_digit.
  50. 				}
  51. 			}
  52. 		}
  53. 	}
  54. 	pair<ll, ll> ans = make_pair(0, 0);
  55. 	for (ll digit = 0; digit < 10; digit++)
  56. 	{
  57. 		ans = make_pair((ans.first + dp[vec.size()][digit][0]) % mod, (ans.second + dp[vec.size()][digit][0] + dp[vec.size()][digit][1]) % mod);
  58. 	}
  59. 	return ans;
  60. }
  61.  
  62. int main()
  63. {
  64. 	// Precomputing (10^i)%mod
  65. 	p[0] = 1;
  66. 	for (ll i = 1; i <= 100005; i++)
  67. 		p[i] = (p[i - 1] * 10) % mod;
  68.  
  69. 	cin >> t;
  70. 	while (t--)
  71. 	{
  72. 		ll lnum, rnum;
  73.  
  74. 		string l, r;
  75. 		vector<ll> vecl, vecr;
  76.  
  77. 		cin >> lnum >> l;
  78. 		cin >> rnum >> r;
  79.  
  80. 		for (auto it : l)
  81. 			vecl.pb(it - '0');
  82.  
  83. 		for (auto it : r)
  84. 			vecr.pb(it - '0');
  85.  
  86. 		cout << (mod + f(vecr).second - f(vecl).first) % mod << endl;
  87. 	}
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
1
2 10
3 100
stdout
copy 
4960
https://ideone.com/7V2xLP
language:
C++14 (gcc 8.3)
created:
4 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!