Help required in problem BADMATH

help
1

I’ve been trying this problem, and I received WA in 6/10 cases and AC in the other 4. My solution is pretty much plain brute force. I recursively replaced each '_' with a '1' and a '0' and checked whether the number formed from each case was divisible by m, and incremented the answer accordingly. I can’t seem to figure out where I went wrong. Is my approach plain incorrect (though it’s unlikely), or have I made some stupid implementation mistake ?
Since the solutions aren’t public, I am pasting my code in a spoiler below.

Spoiler 
       void rec(string s, int idx) {
        if(idx == -1) {
            ll nf = 0;
            for(int i = n-1; i >= 0; i--) {
                if(s[i] == '1') {
                    nf |= (1<<(n-1-i));
                }
            }
            if(nf%m == 0) ans++;
        } else {
            if(s[idx] == '_') {
                string scopy = s;
                scopy[idx] = '1';
                rec(scopy, idx - 1);
                scopy[idx] = '0';
                rec(scopy, idx - 1);
            } else {
                rec(s, idx - 1);
            }
        }
    }

    void solve() {
        cin >> n >> m;
        string s; cin >> s;
        ans = 0;
        rec(s, n-1);
        cout << ans << "\n";
    }
2

N can be upto 100, and 1<<65 will overflow. Also if you want to try, this problem can be solved in polynomial time independent of k, the brute force also works, but you’ll have to precompute the powers of 2 mod m.

2 Likes
3

Thanks! I failed to notice the overflow. I precomputed the powers of 2 mod m and it worked. :slight_smile: