1 条题解

  • 1

    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;

    typedef long long ll;
    typedef pair<ll, ll> pll; // 存储两个值:sum(符合条件的数的和)、count(符合条件的数的个数)

    vector<int> bits; // 存储数字的二进制位(低位在前)
    pll dp[35][2][2]; // 记忆化数组:dp[pos][cnt][limit],pos最多30位(2^30≈1e9)

    // 数位DP核心:记忆化DFS
    pll dfs(int pos, int cnt, bool limit) {
    // 所有位处理完毕:若1的个数为奇数,返回(0,1)(个数1,和为0,后续累加位贡献);否则返回(0,0)
    if (pos == -1) {
    return cnt == 1 ? pll{0, 1} : pll{0, 0};
    }
    // 记忆化:该状态已计算过,直接返回
    if (dp[pos][cnt][limit].first != -1) {
    return dp[pos][cnt][limit];
    }

    int up = limit ? bits[pos] : 1; // 当前位能选的最大值(受limit限制)
    pll res = {0, 0}; // 当前状态的总sum和count

    // 遍历当前位的可选值(0或1)
    for (int i = 0; i <= up; ++i) {
    bool new_limit = limit && (i == up); // 新的limit:原limit且当前位选了最大值
    int new_cnt = cnt ^ (i == 1); // 新的奇偶性:选1则翻转,选0则不变
    pll tmp = dfs(pos - 1, new_cnt, new_limit); // 递归处理下一位

    // 计算当前位的贡献:
    // i*(1<<pos) * 子状态个数(每个子数在当前位加i*2^pos) + 子状态的和
    ll add_sum = (ll)i * (1LL << pos) * tmp.second + tmp.first;
    res.first += add_sum; // 累加和
    res.second += tmp.second; // 累加个数
    }

    return dp[pos][cnt][limit] = res; // 记忆化存储当前状态结果
    }

    // 计算0~x中,二进制有奇数个1的正整数之和
    ll f(ll x) {
    if (x < 1) return 0; // 0无1,不算正整数
    bits.clear();
    // 将x转为二进制(低位在前存入bits)
    while (x) {
    bits.push_back(x % 2);
    x /= 2;
    }
    // 初始化记忆化数组(-1表示未计算)
    memset(dp, -1, sizeof(dp));
    // 从最高位开始DFS:pos=bits.size()-1,初始cnt=0(1的个数为0,偶数),limit=true(受x限制)
    pll ans = dfs(bits.size() - 1, 0, true);
    return ans.first;
    }

    int main() {
    ll l, r;
    cin >> l >> r;
    // 容斥原理:[l,r]的和 = f(r) - f(l-1)
    ll ans = f(r) - f(l - 1);
    cout << ans << endl;
    return 0;
    }

  • 1

信息

ID
2978
难度
6
分类
(无)
标签
递交数
50
已通过
12
通过率
24%
上传者