G5018 [GESP202509 五级] 有趣的数字和 题解

知识点：数位动态规划、二进制、区间求和。

解题思路

用二进制数位DP计算前缀[0,N]内二进制1位数为奇数的数字之和。状态记录位号、奇偶性和是否贴上界，并同时返回方案数与数值和，区间答案作前缀差。

为什么正确

每一条二进制选择路径唯一对应一个数字，奇偶位累计判定合法性；当前位为1时增加该位权乘后缀方案数，精确累加数值。

易错点

不是统计合法数字个数；必须同时返回count与sum；l=0时前缀l-1返回0。

复杂度

本题每个前缀O(log N)状态，空间O(log N)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto f=[](long long n) {
        if(n<0)return 0LL;
        function<pair<long long,long long>(int,int,bool)>dp;
        map<pair<int,int>,pair<long long,long long>>memo;
        dp=[&](int b,int parity,bool tight)->pair<long long,long long> {
            if(b<0)return  {
                parity==1,0
            }
            ;
            if(!tight&&memo.count({b,parity}))return memo[ {
                b,parity
            }
            ];
            long long count=0,sum=0;
            int maxbit=tight?((n>>b)&1):1;
            for(int v=0;v<=maxbit;v++) {
                auto [c,s]=dp(b-1,parity^v,tight&&v==maxbit);
                count+=c;
                sum+=s+c*v*(1LL<<b);
            }
            auto z=make_pair(count,sum);
            if(!tight)memo[ {
                b,parity
            }
            ]=z;
            return z;
        }
        ;
        return dp(30,0,true).second;
    }
    ;
    long long l,r;
    cin>>l>>r;
    cout<<f(r)-f(l-1);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。