Sum of Log_牛客博客

图片说明

思路：
由于 $i\&j==0$ ，所以 $log_2(i+j)$ +1其实就是 $i、j$ 之中最大的那个数的二进制位加一，这个比赛的时候就想到了。直接写状态，上板子即可。比赛的时候只会求单个区间的问题，叠加的没想过，然后死活想不出来怎么去数位dp。
叠加的不就是多个数随机组合吗，也就是对应二进制位的随机组合，居然没想到，2333。
~~补题时的时候数位dp的状态不敢多开几维，状态一多就怕超时，忘了算复杂度~~
数位dp的状态是：

$dp[len][eff][limit1][limit2]$ ， $len$ 表示当前是第 $len$ 位， $eff$ 表示有效长度， $limit1$ 表示 $i$ 的上界， $limit2$ 表示 $j$ 的上界
补了数位dp入门题后，能独立写出来，但是这题有个地方可以优化的，开始没优化超时了，嫖了一眼别人的代码，有效长度确定，且如果 $i、j$ 的高位都没有达到上界的话，假设现在是第 $len$ 位，那么第 $dp[len][eff][0][0]=3^{len+1}*(eff+1)$ ，太菜了。（好像不优化复杂度也不是很高，没想到会T
运行860ms

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[32][32][2][2],f[32];
bool num1[32],num2[32];
ll dfs(int len,int eff,bool limit1,bool limit2) {
    if(len==-1)  return eff+1;
    ll &x=dp[len][eff][limit1][limit2];
    if(~x)
        return x;
    if((!limit1)&&(!limit2)&&eff) return x=f[len+1]*(eff*1LL+1)%mod;
    int end1=limit1?num1[len]:1;
    int end2=limit2?num2[len]:1;
    x=0;
    for(int i=0; i<=end1; ++i)
        for(int j=0; j<=end2; ++j) {
            if(i&j) continue;
            if(!eff&&(i|j)) eff=len;
            x+=dfs(len-1,eff,limit1&&i==end1,limit2&&j==end2);
        }
    return x;
}
int main() {
    int t=read();
    f[0]=1;
    for(int i=1;i<31;++i) {
        f[i]=f[i-1]*3LL%mod;
    }
    while(t--) {
        int L=read(),R=read();
        memset(dp,-1,sizeof dp);
        for(int i=0,tmp=1; i<31; ++i) {
            num1[i]=L&tmp;
            num2[i]=R&tmp;
            tmp<<=1;
        }
        printf("%lld\n",(dfs(30,0,true,true)-1+mod)%mod);
    }
}

更优的常规做法：

不直接用状态记录公式的值之和，而是记录满足要求的组合有多少个，当最高位确定后，这个最高位包含的区间对答案的贡献就是二进制位加一乘以满足要求的组合个数，通过全局变量减少一维状态，从而剪枝。
运行280ms

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[32][2][2],f[32],ans;
bool num1[32],num2[32];
ll dfs(int len,bool limit1,bool limit2,bool zero) {
    if(len==-1)  return 1;
    ll &x=dp[len][limit1][limit2];
    if(~x)
        return x;
    if((!limit1)&&(!limit2)&&!zero) return x=f[len+1];//加不加都行 
    int end1=limit1?num1[len]:1;
    int end2=limit2?num2[len]:1;
    x=0;
    ll tmp,cnt=0;
    for(int i=0; i<=end1; ++i)
        for(int j=0; j<=end2; ++j) {
            if(i&j) continue;
            if(zero&&(i|j)) {
                tmp=dfs(len-1,limit1&&i==end1,limit2&&j==end2,false);
                x=(x+tmp)%mod;
                cnt=(cnt+tmp)%mod;
            }
            else x=(x+dfs(len-1,limit1&&i==end1,limit2&&j==end2,zero&&!(i|j)))%mod;
        }
    ans=(ans+cnt*(len*1LL+1))%mod;
    return x;
}
int main() {
    int t=read();
    f[0]=1;
    for(int i=1;i<31;++i) {
        f[i]=f[i-1]*3LL%mod;
    }
    while(t--) {
        int L=read(),R=read();
        memset(dp,-1,sizeof dp);
        for(int i=0,tmp=1; i<31; ++i) {
            num1[i]=L&tmp;
            num2[i]=R&tmp;
            tmp<<=1;
        }
        ans=0;
        dfs(30,true,true,true);
        printf("%lld\n",ans);
    }
}