D - Xor Sum AtCoder Beginner Contest 050

問題概略
２つの整数u,v <= Nであって、a ^ b = u, a + b = v となるようなu,vが何通りあるか。

制約
N <= 10 ^18

解法
aとbを適当に選んで、出てきたu,vを数えていきたくなる。しかし、これでは重複してしまうし、メモできるような数ではない。
ある桁のビットが1,0の時に0,1にしてもu,vが等しいと気づく。
よって1,0 は許すが0,1は許さないという風にすれば、a,bに対してu,vを全単射的な対応を箚せられる。
a,bをメモ化再帰の桁DPで数え上げる。
a,bのビットは0,0 1,0 11の時の3通りがあり、f(s , x):=uvがsx以下の通りとすると、0,0の時にはf(s/2,x/2)に、1,1の時にはf(s-2/2,x/2)になる。という風に桁を減らしてu,vの合計がS,X以上にならないように遷移できる。s,xについてメモすれば出来る。

public static long rec(long s, long x) {
        if (s == 0) return 1;
        String key = s + "_" + x;
        if (map.containsKey(key)) return map.get(key);
        long res = 0;
        //00
        res = modSum(res, rec(s / 2, x / 2));
        if (s > 0 && x > 0) {
            //10
            res = modSum(res, (rec((s - 1) / 2, (x - 1) / 2)));
        }
        if (s > 1) {
            //11
            res = modSum(res, (rec((s - 2) / 2, x / 2)));
        }
        map.put(key, res);
        return res;
    }

    public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = nl();
        System.out.println(rec(N, N));

    }