Today, I learned Digit DP for the first time, so I tried to solve different kinds of Digit DP problems. While doing that, I came upon [This](https://mirror.codeforces.com/problemset/problem/2039/C1) question. I know this is not a Digit Dp question, and there is a much better approach to this question. However, I wrote a solution using the concepts I learned and got **TLE on Test Case 45**. Can Someone help me optimize this further?↵
↵
Here is the code :↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace std;↵
using namespace __gnu_pbds;↵
template<class T> using oset = tree< T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update >; ↵
// *st.find_by_order(i) --> element at ith position↵
// st.order_of_key(x) --> no. of ele less than x↵
//For multiset change less to less_equal and for reverse order change less to greater↵
#define int long long ↵
#define endl '\n'↵
#define all(x) (x).begin(), (x).end()↵
template<typename T> // cin >> vector<T>↵
istream& operator>>(istream &istream, vector<T> &v){for(auto &it : v)cin >> it;return istream;}↵
template<typename T> // cout << vector<T>↵
ostream& operator<<(ostream &ostream, const vector<T> &c){for(auto &it : c)cout << it << " ";return ostream;}↵
↵
// int dp[19][2];↵
map<tuple<int, bool, string>, int> memo;↵
↵
int f(int idx , bool bound , string ans , int x , string &s) {↵
if(idx == (int)s.size()) {↵
int y = stoll(ans);↵
if(y == 0 or (x == y)) return 0;↵
int div = x ^ y;↵
return (x % div == 0) or (y % div == 0);↵
}↵
auto state = make_tuple(idx, bound, ans);↵
if (memo.find(state) != memo.end()) return memo[state];↵
// if(dp[idx][bound] != -1) return dp[idx][bound];↵
int res = 0;↵
int maxDigit = 9;↵
if(bound) maxDigit = s[idx] - '0';↵
for(int i = 0 ; i <= maxDigit ; i++) {↵
res += f(idx + 1 , bound & (i == maxDigit) , ans + to_string(i) , x , s) ;↵
}↵
// return dp[idx][bound] = res;↵
return memo[state] = res;↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
int testCase; cin >> testCase;↵
while(testCase--) {↵
memo.clear();↵
int x , m;↵
cin >> x >> m;↵
string s = to_string(m);↵
string ans = "";↵
// memset(dp , -1 , sizeof(dp));↵
cout << f(0 , true , ans , x , s) << endl;↵
memo.clear();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
↵
Any help is highly appreciated, my friend!
↵
Here is the code :↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace std;↵
using namespace __gnu_pbds;↵
template<class T> using oset = tree< T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update >; ↵
// *st.find_by_order(i) --> element at ith position↵
// st.order_of_key(x) --> no. of ele less than x↵
//For multiset change less to less_equal and for reverse order change less to greater↵
#define int long long ↵
#define endl '\n'↵
#define all(x) (x).begin(), (x).end()↵
template<typename T> // cin >> vector<T>↵
istream& operator>>(istream &istream, vector<T> &v){for(auto &it : v)cin >> it;return istream;}↵
template<typename T> // cout << vector<T>↵
ostream& operator<<(ostream &ostream, const vector<T> &c){for(auto &it : c)cout << it << " ";return ostream;}↵
↵
// int dp[19][2];↵
map<tuple<int, bool, string>, int> memo;↵
↵
int f(int idx , bool bound , string ans , int x , string &s) {↵
if(idx == (int)s.size()) {↵
int y = stoll(ans);↵
if(y == 0 or (x == y)) return 0;↵
int div = x ^ y;↵
return (x % div == 0) or (y % div == 0);↵
}↵
auto state = make_tuple(idx, bound, ans);↵
if (memo.find(state) != memo.end()) return memo[state];↵
// if(dp[idx][bound] != -1) return dp[idx][bound];↵
int res = 0;↵
int maxDigit = 9;↵
if(bound) maxDigit = s[idx] - '0';↵
for(int i = 0 ; i <= maxDigit ; i++) {↵
res += f(idx + 1 , bound & (i == maxDigit) , ans + to_string(i) , x , s) ;↵
}↵
// return dp[idx][bound] = res;↵
return memo[state] = res;↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
int testCase; cin >> testCase;↵
while(testCase--) {↵
memo.clear();↵
int x , m;↵
cin >> x >> m;↵
string s = to_string(m);↵
string ans = "";↵
// memset(dp , -1 , sizeof(dp));↵
cout << f(0 , true , ans , x , s) << endl;↵
memo.clear();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
↵
Any help is highly appreciated, my friend!
