【題解】Codeforces 1245F. Daniel and Spring Cleaning

#include <iostream>
#include <cstring>
using namespace std;
 
int t, l, r, a[32], b[32];
long long dp[32][2][2];
 
long long dfs(int pos, int lima, int limb){
    if (pos == -1) return 1;
    if (dp[pos][lima][limb] != -1) return dp[pos][lima][limb];
    int uba = lima?a[pos]:1;
    int ubb = limb?b[pos]:1;
    long long ans = 0;
    for (int i = 0; i <= uba; i++){
        for (int j = 0; j <= ubb; j++){
            if (i & j == 1) continue;
            ans += dfs(pos-1, lima&&i==a[pos], limb&&j==b[pos]);
        }
    }
    dp[pos][lima][limb] = ans;
    return ans;
}
 
long long solve(int x, int y){
    int cnt = 0;
    memset(dp, -1, sizeof(dp));
    while (x | y){
        a[cnt] = x & 1;
        b[cnt] = y & 1;
        x >>= 1;
        y >>= 1;
        cnt++;
    }
    return dfs(cnt-1, 1, 1);
}
 
int main() {
    cin >> t;
    while (t--){
        cin >> l >> r;
        if (l == 0) cout << solve(r, r) << "\n";
        else cout << solve(r, r) - 2 * solve(r, l-1) + solve(l-1, l-1) << "\n";
    }
}