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

80 阅读 0 评论 53 点赞

我是靠谱客的博主专一电话，这篇文章主要介绍2020ICPC上海 C.Sum of Log（数位DP），现在分享给大家，希望可以做个参考。

在这里插入图片描述
思路：
思路很快就出来了，但是实现过程还是有点细节，一直在T。。。

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

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

然后又想着将 $l i m i t$ 作为状态，每次都情况 $d p$ 数组，这样就变成了 $d p [l e n] [h i g h] [l i m i t 1] [l i m i t 2]$ 。算起来的话一共有 $30 * 30 * 2 * 2$ 个状态，每个状态最坏算 $3$ 次，一共 $1 e 5$ 次询问，复杂度还是感人。过了66.67%数据。

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

所以最终状态定义为 $d p [l e n] [l l i m i t 1] [l i m i t 2]$ ，转移的话就是使得这个位置上 $i & j \neq = 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}