【算法

https://codeforces.com/gym/102900/problem/C

找数对(x,y)，他们的二进制位与的结果一定是0，然后他们的贡献就是他们位或的msb的长度+1。
状态为dp[dep][xlim][ylim][lzero]表示长度为dep的数对，x限制为xlim，y限制为ylim的数对，前导零状态为lzero的总贡献（不是数量）。
lzero为1：表示前面放的都是一串0，msb还没有出现，这个时候假如决定在当前层放，会增加dep的贡献
x为lim或者y为lim的状态，最多被扫log方次，假如不想记录也可以，但是最好还是记一下。多组询问再找到这些状态memset掉不迟。

若lzero为1，则这类状态只会被扫log次的，不想记录也行。
若lzero不为1，则说明前面已经有了msb了，现在就数一数“位与为0的有多少个数对”返回给上层调用就行。

int X[32], Y[32];
int dp[32][2][2][2];

ll dfs(int dep, bool xlim, bool ylim, bool lzero) {
    if (dep == -1)
        return 1;
    if (dp[dep][xlim][ylim][lzero] != -1)
        return dp[dep][xlim][ylim][lzero];
    int maxx = xlim ? X[dep] : 1;
    int maxy = ylim ? Y[dep] : 1;
    ll ans = 0;
    for (int i = 0; i <= maxx; ++i) {
        for (int j = 0; j <= maxy; ++j) {
            if (i & j)
                continue;
            int contri = 1;
            if (lzero && (i || j))
                contri += dep;
            bool nxlim = (xlim && i == maxx);
            bool nylim = (ylim && j == maxy);
            bool nlzero = (lzero && ((i || j) == 0));
            ans += 1LL * contri * dfs(dep - 1, nxlim, nylim, nlzero);
        }
    }
    ans %= MOD;
    dp[dep][xlim][ylim][lzero] = ans;
    return ans;
}

void solve() {
    int x, y;
    scanf("%d%d", &x, &y);
    for (int i = 0; i <= 31; ++i) {
        X[i] = x & 1;
        Y[i] = y & 1;
        x >>= 1;
        y >>= 1;
    }
    memset(dp, -1, sizeof(dp));
    printf("%lld
", (dfs(31, 1, 1, 1) - 1 + MOD) % MOD);
}

给定三个整数 a,b,k ，计算满足 0<=x<a 和 0<=y<b 的位与结果小于 k（即(x&y)<k）的有序数对(x,y)的个数。
https://acm.ecnu.edu.cn/problem/77/

int X[32], Y[32], K[32];
ll dp[32][2][2][2];

ll dfs(int dep, bool xlim, bool ylim, bool klim) {
    if (dep == -1)
        return !(xlim || ylim || klim);
    if (dp[dep][xlim][ylim][klim] != -1)
        return dp[dep][xlim][ylim][klim];
    int maxx = xlim ? X[dep] : 1;
    int maxy = ylim ? Y[dep] : 1;
    ll ans = 0;
    for (int i = 0; i <= maxx; ++i) {
        for (int j = 0; j <= maxy; ++j) {
            if (klim && ((i & j) > K[dep]))
                continue;
            bool nxlim = (xlim && i == maxx);
            bool nylim = (ylim && j == maxy);
            bool nklim = (klim && (i & j) == K[dep]);
            ans += dfs(dep - 1, nxlim, nylim, nklim);
        }
    }
    dp[dep][xlim][ylim][klim] = ans;
    return ans;
}

void solve() {
    int x, y, k;
    scanf("%d%d%d", &x, &y, &k);
    for (int i = 0; i <= 31; ++i) {
        X[i] = x & 1;
        Y[i] = y & 1;
        K[i] = k & 1;
        x >>= 1;
        y >>= 1;
        k >>= 1;
    }
    memset(dp, -1, sizeof(dp));
    printf("%lld
", dfs(31, 1, 1, 1));
}

对于上面两题，问的都是从0开始的某个数或者从00开始的某个数对，所以只需要调用一次，状态也直接简化为xlim和ylim。

若要求[L,R]范围内的数对，就有可能要调用多次，这时假如继续像上面这样设，也可以但是会导致每次更换限制后要memset。另一种方法是不记录xlim和ylim为true的状态，这样子状态可以公用，记状态为“第i位放j作为x开头放k作为y的开头，两个状态都不受限制时的答案”，这样就和LR这些限制无关了。数位dp的复杂度是每个状态都会被遍历一次，然后乘上这个状态的转移带来的平均花费，一般都是几个log的事情。假如把状态信息记录太多而不进行约简，就会更像“暴力”，假如状态信息过于约简但都与lim有关，就会在更换lim多次询问时需要把与lim相关的都进行清空。