题解：P9821 [ICPC 2020 Shanghai R] Sum of Log

· · 题解

提供一种好理解的不用太多转换的数位 DP 做法。但其实都差不太多。

思路

首先看范围，可以确定是数位 DP，然后有位运算，考虑成二进制的数位 DP。

先观察式子，不妨让 j 也从 0 开始取，最后单独考虑一下 i，j 为 0 的情况即可。这样会方便很多。然后发现 log_2(i+j) 实际上就是求 i+j 的哪个最高位为 1。

我们可以先记录合法情况的方案数，然后通过方案数再计算合法情况的和。

考虑从高往低填两个数位 X 和 Y，如果对着序列切一刀，考虑这一刀前面对后面的影响，我们是不是需要知道之前的数位是否严格小于上界？想要当前数位对答案贡献，那么当前数位的前面数位是不是需要全为 0？然后对答案贡献多少，就是取决于当前数位后面的数位合法方案数了。

然后大力记忆化搜索即可。具体的，记录 dep 表示当前填到哪个数位，ok 表示填的 i 序列前面 dep 位是否已经严格小于对应的 X，ok2 同理，zero 表示前 dep 位上的数位填的 i+j 是否全为 0。

还是很好理解的，不需要对式子进行太多变形，具体见代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=34, Mod=1e9+7;

struct node
{
    ll cnt, sum;
}f[N][2][2][2];
int G, a[N], b[N];
ll L, R;
void upd(node &to, node from, bool lg, int dep)
{
//  if (lg) printf("Y %lld %lld -> ", from.cnt, from.sum);
    to.cnt=(to.cnt+from.cnt)%Mod;
    to.sum=((to.sum+from.sum)%Mod+lg*(dep+1ll)*from.cnt%Mod)%Mod;
//  if (lg) printf("%lld %lld\n", to.cnt, to.sum);
}
node dfs(int dep, bool ok, bool ok2, bool zero)
{
    if (dep<0) return {1, 0};
    if (f[dep][ok][ok2][zero].cnt!=-1) return f[dep][ok][ok2][zero];

    node ret={0, 0};
    for (int i=0; i<=1; i++)
        for (int j=0; j<=1; j++)
        {
            if ((!ok && i>a[dep]) || (!ok2 && j>b[dep]) || (i&j)!=0) continue;
//          if ((i+j==1&&zero)) printf("{%d %d %d %d [%d, %d] <%d>}\n", dep, ok, ok2, zero, i, j, (i+j==1&&zero));
            upd(ret, dfs(dep-1, ok|(i<a[dep]), ok2|(j<b[dep]), zero&(i+j==0)), (i+j==1&&zero), dep);
        }

    f[dep][ok][ok2][zero]=ret;
    return ret;
} 
ll solve(ll r, ll r2)
{
    for (int i=0; i<=31; i++)
        for (int ok=0; ok<=1; ok++)
            for (int ok2=0; ok2<=1; ok2++)
                for (int zero=0; zero<=1; zero++) f[i][ok][ok2][zero]={-1, -1};

    for (int i=31; i>=0; i--) a[i]=((r>>i)&1), b[i]=((r2>>i)&1);
    return dfs(31, 0, 0, 1).sum;
}
int main()
{
    scanf("%d", &G);
    while (G--)
    {
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", solve(L, R));
    }
    return 0;
}
/*
1 3 3
*/