I was attempting this problem : https://mirror.codeforces.com/contest/628/problem/D and came up with a solution which basically look like this :
int d, m;
ll int magicNumberDP(string n, int idx,ll int curNum, bool tight) {
if (idx >= n.length()) {
return !curNum ;
}
int uprBnd = (tight) ? n[idx] - '0' : 9 ;
ll int ans = 0 ;
for (int dig = 0 ; dig <= uprBnd ; dig++) {
if ((idx + 1) % 2 == 0 and d != dig) {
continue ;
}
if ((idx + 1) % 2 == 1 and d == dig) {
continue ;
}
ans = ans + magicNumberDP(n, idx + 1, (curNum * 10 + dig) % m, tight & (dig == uprBnd)) ;
}
return ans;
}
void magicNumber() {
cin >> m >> d ;
ll int r, l;
cin >> l >> r ;
l--;
string R = to_string(r);
string L = to_string(l);
int ansR = magicNumberDP(R, 0, 0ll, 1);
int ansL = magicNumberDP(L, 0, 0ll, 1);
cout << ansL << " " << ansR << endl ;
cout << ansR - ansL << endl;
}
But this is giving wrong answer can someone tell me why I am wrong and how can I correct it?