You are viewing a single comment's thread. Return to all comments →
You will find it obvious if you first think in plain English for the recurrence relation:
DP(i, j) := The # of subset using numbers within [3500, i] which XOR result of the subset equals to j (3500 <= i <= 4500)
Now, DP(i, j) should consists of two disjoint parts:
So Part 1 includes subsets of DP(i-1, j) union even number of i, as even number of i will produce 0 on the XOR result (no effect)
Part 2 on the contrast includes subsets of DP(i-1, j^i) union odd number of i, as odd number of i will produce a XOR i effect
Combined these points, the problem becomes counting how many even / odd i to produce XOR result j, which is the (cnt[i]+2)/2 or (cnt[i]+1)/2
Seems like cookies are disabled on this browser, please enable them to open this website
Prime XOR
You are viewing a single comment's thread. Return to all comments →
You will find it obvious if you first think in plain English for the recurrence relation:
DP(i, j) := The # of subset using numbers within [3500, i] which XOR result of the subset equals to j (3500 <= i <= 4500)
Now, DP(i, j) should consists of two disjoint parts:
So Part 1 includes subsets of DP(i-1, j) union even number of i, as even number of i will produce 0 on the XOR result (no effect)
Part 2 on the contrast includes subsets of DP(i-1, j^i) union odd number of i, as odd number of i will produce a XOR i effect
Combined these points, the problem becomes counting how many even / odd i to produce XOR result j, which is the (cnt[i]+2)/2 or (cnt[i]+1)/2