Guest User

Untitled

a guest
May 29th, 2020
9
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& STL DEBUGGER &&&&&&&&&&&&&&&&&&&&&&&&&&&
  2.  
  3. // #define _GLIBCXX_DEBUG // Iterator safety; out-of-bounds access for Containers, etc.
  4. // #pragma GCC optimize "trapv" // abort() on (signed) integer overflow.
  5.  
  6. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LIBRARIES &&&&&&&&&&&&&&&&&&&&&&&&&&&
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10.  
  11. /*#include <ext/pb_ds/assoc_container.hpp> // Common file
  12. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  13. template<typename T, typename V = __gnu_pbds::null_type>
  14. using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  15. */
  16. //find_by_order()->returns an iterator to the k-th largest element(0-based indexing)
  17. //order_of_key()->Number of items that are strictly smaller than our item
  18.  
  19. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEFINES &&&&&&&&&&&&&&&&&&&&&&&&&&&
  20.  
  21. #define int long long int
  22. #define ld long double
  23. #define X first
  24. #define Y second
  25. #define all(i) i.begin(), i.end()
  26. #define sz(a) (int)a.size()
  27.  
  28. const ld PI = 3.141592;
  29. const int dx4[4] = {0, 1, 0, -1};
  30. const int dy4[4] = {-1, 0, 1, 0};
  31. const int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  32. const int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  33.  
  34. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEBUG &&&&&&&&&&&&&&&&&&&&&&&&&&&
  35.  
  36. #define XOX
  37. vector<string> vec_splitter(string s) {
  38. for(char& c: s) c = c == ','? ' ': c;
  39. stringstream ss; ss << s;
  40. vector<string> res;
  41. for(string z; ss >> z; res.push_back(z));
  42. return res;
  43. }
  44.  
  45. void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; }
  46. template <typename Head, typename... Tail>
  47. void debug_out(vector<string> args, int idx, Head H, Tail... T) {
  48. if(idx > 0) cerr << ", ";
  49. stringstream ss; ss << H;
  50. cerr << args[idx] << " = " << ss.str();
  51. debug_out(args, idx + 1, T...);
  52. }
  53.  
  54. #ifdef XOX
  55. #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
  56. #else
  57. #define debug(...) 42
  58. #endif
  59.  
  60.  
  61. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CODE &&&&&&&&&&&&&&&&&&&&&&&&&&&
  62.  
  63. int L, R;
  64. int dp[19][2][1<<(10)];
  65. int freq[10];
  66. int cnt[10];
  67.  
  68. int bruteforce(int l, int r){
  69. int ct = 0;
  70. for(int i = l; i <= r; ++i){
  71. vector<int> cnt(10, 0);
  72. int x = i;
  73. while(x){
  74. cnt[x%10]++;
  75. x /= 10;
  76. }
  77. bool poss = true;
  78. for(int i = 0; i <= 9; ++i)
  79. if(freq[i] == cnt[i])
  80. poss = false;
  81.  
  82. if(poss)
  83. ct++;
  84. }
  85. return ct;
  86. }
  87.  
  88. vector<int> getDigits(int x){
  89. vector<int> temp;
  90. while(x){
  91. temp.push_back(x%10);
  92. x /= 10;
  93. }
  94. reverse(all(temp));
  95. return temp;
  96. }
  97.  
  98. //dp[id][tight][mask];
  99. //mask represents the digits that have appreared till now.
  100. //tight to represt if we have same prefix as the number or not.
  101.  
  102. int solve(vector<int> &digits, int cnt[], int id, bool tight, int mask, bool leadZero){
  103. if(id == sz(digits)){
  104. if(leadZero)
  105. return 0;
  106. // for(int i = 0; i <= 9; ++i)
  107. // cout << cnt[i] << " ";
  108. // cout << '\n';
  109. for(int i = 0; i <= 9; ++i) //Check if number formed is bad or not
  110. if(freq[i] == cnt[i])
  111. return 0;
  112. return 1;
  113. }
  114. auto &res = dp[id][tight][mask];
  115. if(res != -1)
  116. return res;
  117. int LIM = (tight) ? digits[id] : 9;
  118. res = 0;
  119. for(int i = 0; i <= LIM; ++i){
  120. bool newtight = (i == digits[id] ? tight : false);
  121. int newmask = mask | (1<<i);
  122. if(i == 0){
  123. if(leadZero){
  124. res += solve(digits, cnt, id + 1, newtight, mask, leadZero);
  125. } else {
  126. cnt[i]++;
  127. res += solve(digits, cnt, id + 1, newtight, newmask, leadZero);
  128. cnt[i]--;
  129. }
  130. continue;
  131. }
  132. cnt[i]++;
  133. res += solve(digits, cnt, id + 1, newtight, newmask, false);
  134. cnt[i]--;
  135. }
  136. return res;
  137. }
  138.  
  139. void init(){
  140. vector<int> digits = getDigits(L - 1);
  141. memset(dp, -1, sizeof(dp));
  142. memset(cnt, 0, sizeof(cnt));
  143. int ans1 = solve(digits, cnt, 0, true, 0, true);
  144. // cout << ans1 << " \n ss \n" << bruteforce(1, L - 1) << '\n';
  145. digits = getDigits(R);
  146. memset(dp, -1, sizeof(dp));
  147. memset(cnt, 0, sizeof(cnt));
  148. int ans2 = solve(digits, cnt, 0, true, 0, true);
  149. // cout << ans2 << " " << bruteforce(1, R) << '\n';
  150. cout << ans2 - ans1 << '\n';
  151. }
  152.  
  153. void solve(){
  154. cin >> L >> R;
  155. for(int i = 0; i <= 9; ++i)
  156. cin >> freq[i];
  157. init();
  158. }
  159.  
  160. int32_t main(){
  161. ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  162. int T = 1;
  163. cin >> T;
  164. for(int i = 1; i <= T; ++i){
  165. solve();
  166. }
  167. return 0;
  168. }
  169.  
  170. /*
  171. Sample inp
  172. */
RAW Paste Data