fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ub        upper_bound            // first element >  val(itr)
  5. #define lb        lower_bound            // first element >= val(itr)
  6.  
  7. #define sz(a) int((a).size())
  8. #define pb push_back
  9. #define all(c) (c).begin(),(c).end()
  10. #define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
  11. #define present(c,x) ((c).find(x) != (c).end()) 
  12. #define cpresent(c,x) (find(all(c),x) != (c).end()) 
  13. #define mem(a,b) memset( a, b, sizeof(a) )
  14.  
  15. #define bitcount(a) __builtin_popcount(a)   // count set bits
  16. #define lzcount(x) __builtin_clz(x)        // count leading zeros in binary representation of number
  17. #define tzcount(x) __builtin_ctz(x)        // count trailing zeros in binary representation of number
  18.  
  19. #define FAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  20.  
  21. typedef long long int ll;
  22. const ll MOD = 1e9+7;
  23.  
  24. template<typename T> T gcd(T a,T b){ if(b>a) return gcd(b,a);return b==0?a:gcd(b,a%b); }
  25. template<typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
  26. template<typename T> T fast_power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
  27. /*
  28. inline ll mod(ll x,ll n) {if (x < n) return x; if (x >= n) return x - n;}
  29. string IntToString(ll a){ ostringstream temp; temp << a; return temp.str();}
  30. ll findMMI_fermat(ll n,ll M) {ll ans= fast_power(n,M-2,M);return ans;}//i.e In (a/b)%M..it calculates MMI of b wrt M,only if M is prime
  31. ll add(ll a,ll b,ll M)  { return mod(( mod(a,M ) + mod(b,M )),M);     }
  32. ll sub(ll a, ll b,ll M) { return mod((mod(a,M ) + M - mod(b,M )),M);   }
  33. ll mult(ll a,ll b,ll M) { return  mod(( mod(a,M)*mod(b,M) ),M) ; }
  34. bool isprime(ll a){ if(a==2) {return 1;}if(!(a&1) ) {return 0;}for(ll i=3;i*i<=a;i+=2){if(a%i==0) {return 0;} } return 1;} 
  35.  
  36.   
  37.                /* -------------------------------Main Code------------------------------- */		
  38.  
  39. vector<int> num;
  40. ll dp[300][2][300];//pos,restricted,sum
  41.  
  42. ll call(int pos,int f1,int sum){
  43. 	if(pos==num.size()){
  44. 		return sum;
  45. 	}
  46.  
  47. 	ll &ret = dp[pos][f1][sum];
  48. 	if(ret!=-1) return ret;
  49.  
  50. 	int LIM = f1 ? 9 : num[pos];
  51. 	ll ans = 0;
  52.  
  53. 	for(int i=0;i<=LIM;i++){
  54. 		ans += call(pos+1,i<num[pos] ? 1 : f1 ,sum+i );
  55. 	}
  56.  
  57. 	return ret = ans;
  58. }
  59.  
  60. ll solve(int x){
  61. 	num.clear();
  62. 	while(x){
  63. 		num.push_back(x%10);
  64. 		x/=10;
  65. 	}
  66. 	reverse(num.begin(),num.end());
  67. 	mem(dp,-1);
  68. 	return call(0,0,0);
  69. }
  70.  
  71.  
  72. int main(){
  73.     FAST
  74. 	int t;cin>>t;
  75. 	while(t--){
  76. 		int a,b;cin>>a>>b;
  77. 		cout<<solve(b)-solve(a-1)<<endl;
  78. 	}
  79. 	return 0;
  80. }
  81.  
  82.  
  83.  
  84.  
  85.  
Success #stdin #stdout 0s 5068KB
comments (?)
stdin
copy 
3
0 10
28 31
1234 56789
stdout
copy 
46
28
1128600
https://ideone.com/8lmVno
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!