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 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 5. 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!
