Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& STL DEBUGGER &&&&&&&&&&&&&&&&&&&&&&&&&&&
- // #define _GLIBCXX_DEBUG // Iterator safety; out-of-bounds access for Containers, etc.
- // #pragma GCC optimize "trapv" // abort() on (signed) integer overflow.
- //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LIBRARIES &&&&&&&&&&&&&&&&&&&&&&&&&&&
- #include <bits/stdc++.h>
- using namespace std;
- /*#include <ext/pb_ds/assoc_container.hpp> // Common file
- #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
- template<typename T, typename V = __gnu_pbds::null_type>
- using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
- */
- //find_by_order()->returns an iterator to the k-th largest element(0-based indexing)
- //order_of_key()->Number of items that are strictly smaller than our item
- //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEFINES &&&&&&&&&&&&&&&&&&&&&&&&&&&
- #define int long long int
- #define ld long double
- #define X first
- #define Y second
- #define all(i) i.begin(), i.end()
- #define sz(a) (int)a.size()
- const ld PI = 3.141592;
- const int dx4[4] = {0, 1, 0, -1};
- const int dy4[4] = {-1, 0, 1, 0};
- const int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
- const int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
- //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEBUG &&&&&&&&&&&&&&&&&&&&&&&&&&&
- #define XOX
- vector<string> vec_splitter(string s) {
- for(char& c: s) c = c == ','? ' ': c;
- stringstream ss; ss << s;
- vector<string> res;
- for(string z; ss >> z; res.push_back(z));
- return res;
- }
- void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; }
- template <typename Head, typename... Tail>
- void debug_out(vector<string> args, int idx, Head H, Tail... T) {
- if(idx > 0) cerr << ", ";
- stringstream ss; ss << H;
- cerr << args[idx] << " = " << ss.str();
- debug_out(args, idx + 1, T...);
- }
- #ifdef XOX
- #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
- #else
- #define debug(...) 42
- #endif
- //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CODE &&&&&&&&&&&&&&&&&&&&&&&&&&&
- int L, R;
- int dp[19][2][1<<(10)];
- int freq[10];
- int cnt[10];
- int bruteforce(int l, int r){
- int ct = 0;
- for(int i = l; i <= r; ++i){
- vector<int> cnt(10, 0);
- int x = i;
- while(x){
- cnt[x%10]++;
- x /= 10;
- }
- bool poss = true;
- for(int i = 0; i <= 9; ++i)
- if(freq[i] == cnt[i])
- poss = false;
- if(poss)
- ct++;
- }
- return ct;
- }
- vector<int> getDigits(int x){
- vector<int> temp;
- while(x){
- temp.push_back(x%10);
- x /= 10;
- }
- reverse(all(temp));
- return temp;
- }
- //dp[id][tight][mask];
- //mask represents the digits that have appreared till now.
- //tight to represt if we have same prefix as the number or not.
- int solve(vector<int> &digits, int cnt[], int id, bool tight, int mask, bool leadZero){
- if(id == sz(digits)){
- if(leadZero)
- return 0;
- // for(int i = 0; i <= 9; ++i)
- // cout << cnt[i] << " ";
- // cout << '\n';
- for(int i = 0; i <= 9; ++i) //Check if number formed is bad or not
- if(freq[i] == cnt[i])
- return 0;
- return 1;
- }
- auto &res = dp[id][tight][mask];
- if(res != -1)
- return res;
- int LIM = (tight) ? digits[id] : 9;
- res = 0;
- for(int i = 0; i <= LIM; ++i){
- bool newtight = (i == digits[id] ? tight : false);
- int newmask = mask | (1<<i);
- if(i == 0){
- if(leadZero){
- res += solve(digits, cnt, id + 1, newtight, mask, leadZero);
- } else {
- cnt[i]++;
- res += solve(digits, cnt, id + 1, newtight, newmask, leadZero);
- cnt[i]--;
- }
- continue;
- }
- cnt[i]++;
- res += solve(digits, cnt, id + 1, newtight, newmask, false);
- cnt[i]--;
- }
- return res;
- }
- void init(){
- vector<int> digits = getDigits(L - 1);
- memset(dp, -1, sizeof(dp));
- memset(cnt, 0, sizeof(cnt));
- int ans1 = solve(digits, cnt, 0, true, 0, true);
- // cout << ans1 << " \n ss \n" << bruteforce(1, L - 1) << '\n';
- digits = getDigits(R);
- memset(dp, -1, sizeof(dp));
- memset(cnt, 0, sizeof(cnt));
- int ans2 = solve(digits, cnt, 0, true, 0, true);
- // cout << ans2 << " " << bruteforce(1, R) << '\n';
- cout << ans2 - ans1 << '\n';
- }
- void solve(){
- cin >> L >> R;
- for(int i = 0; i <= 9; ++i)
- cin >> freq[i];
- init();
- }
- int32_t main(){
- ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
- int T = 1;
- cin >> T;
- for(int i = 1; i <= T; ++i){
- solve();
- }
- return 0;
- }
- /*
- Sample inp
- */
Add Comment
Please, Sign In to add comment