2020ICPC上海 C.Sum of Log（数位DP）

思路：
思路很快就出来了，但是实现过程还是有点细节，一直在T。。。

可以观察发现，题中式子的结果就是$i|j$的最高位。那么我们按照X,Y的二进制位跑数位DP就好了。

我初始的状态定义是$dp[len][high]$，代表两个数枚举到了第$len$位，最高位为$high$时候的结果。但是这样定义状态有个问题，由于$limit$的存在，就是很多状态无法记录不下来，比如X=1000000000，Y=1的时候，前面部分几乎就是在枚举X本身。这样肯定会T。过了40%的数据。

然后又想着将$limit$作为状态，每次都情况$dp$数组，这样就变成了$dp[len][high][limit1][limit2]$。算起来的话一共有$30\ast 30\ast 2\ast 2$个状态，每个状态最坏算$3$次，一共$1e5$次询问，复杂度还是感人。过了66.67%数据。

最后查了下别人的解法，发现他们省掉了$high$这一维状态，大悟。因为最高位只可能出现在一个数字上面，所以我们枚举最高位的位置以及是出现在$X$中还是在$Y$中，复杂度就少了很大一个档次。

所以最终状态定义为$dp[len][llimit1][limit2]$，转移的话就是使得这个位置上$i\&j\ne 1$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
typedef long long ll;

ll dp[32][2][2]; //X的位,Y的位,X|Y的最高位
int a[32],b[32];
ll dfs(int len,int limit1,int limit2) {
    if(len == -1) {
        return 1;
    }
    if(dp[len][limit1][limit2] != -1) return dp[len][limit1][limit2];
    int ans = 0;
    int up1 = limit1 ? a[len] : 1;
    int up2 = limit2 ? b[len] : 1;
    for(int i = 0;i <= up1;i++) {
        for(int j = 0;j <= up2;j++) {
            if((i & j) == 1) continue;
            ans += dfs(len - 1,limit1 && i == up1,limit2 && j == up2);
            ans %= mod;
        }
    }
    return dp[len][limit1][limit2] = ans;
}

ll solve(int X,int Y) {
    memset(dp,-1,sizeof(dp));
    int lena = -1,lenb = -1;
    for(int i = 30;i >= 0;i--) {
        a[i] = (X >> i) & 1;
        b[i] = (Y >> i) & 1;
        if(lena == -1 && a[i]) {
            lena = i;
        }
        if(lenb == -1 && b[i]) {
            lenb = i;
        }
    }
    ll res = 0;
    //X是最高位
    for(int i = lena;i >= 0;i--) {
        res += dfs(i - 1,i == lena,i > lenb) * (i + 1) % mod;
        res %= mod;
    }
    //Y是最高位
    for(int i = lenb;i >= 0;i--) {
        res += dfs(i - 1,i > lena,i == lenb) * (i + 1) % mod;
        res %= mod;
    }
    return res;
}

int main() {
    int T;scanf("%d",&T);
    while(T--) {
        int X,Y;scanf("%d%d",&X,&Y);
        ll ans = solve(X,Y);
        ans = (ans + mod) % mod;
        printf("%lldn",ans);
    }
    return 0;
}

超时代码（没有省掉最高位那个维度）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
typedef long long ll;

int dp[31][31][2][2]; //X的位,Y的位,X|Y的最高位
int a[32],b[32];
int dfs(int len,int high,int limit1,int limit2) {
    if(len == -1) {
        return high + 1;
    }
    if(dp[len][high][limit1][limit2] != -1) return dp[len][high][limit1][limit2];
    int ans = 0;
    int up1 = limit1 ? a[len] : 1;
    int up2 = limit2 ? b[len] : 1;
    for(int i = 0;i <= up1;i++) {
        for(int j = 0;j <= up2;j++) {
            if((i & j) == 1) continue;
            int now = high;
            if(now == 0 && ((i | j) == 1)) {
                now = len;
            }
            ans += dfs(len - 1,now,limit1 && i == up1,limit2 && j == up2);
            ans %= mod;
        }
    }
    return dp[len][high][limit1][limit2] = ans;
}

int solve(int X,int Y) {
    memset(dp,-1,sizeof(dp));
    int len = 0;
    for(int i = 30;i >= 0;i--) {
        a[i] = (X >> i) & 1;
        b[i] = (Y >> i) & 1;
        if(!len && (a[i] || b[i])) {
            len = i;
        }
    }
    return dfs(len,0,true,true);
}

int main() {
    int T;scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while(T--) {
        int X,Y;scanf("%d%d",&X,&Y);
        int ans = solve(X,Y) - 1;
        ans = (ans + mod) % mod;
        printf("%dn",ans);
    }
    return 0;
}

最后

以上就是专一电话为你收集整理的2020ICPC上海 C.Sum of Log（数位DP）的全部内容，希望文章能够帮你解决2020ICPC上海 C.Sum of Log（数位DP）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。