1 条题解
-
1
202509zj05张子瑞 (张子瑞) LV 9 @ 2025-12-14 16:47:36
#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%
- 上传者