题意

给出区间$[A, B]$,求出区间内的数转成二进制后$0$比$1$多的数的个数

$1 \leqslant A, B \leqslant 2,000,000,000$

Sol

比较zz的数位dp

直接在二进制下dp就好

$f[i][ze][on]$表示第$i$位,填了$ze$个$0$,$on$个1的方案数

#include<cstdio>
#include<cstring>
#include<iostream>
// #include<map>
using namespace std;
#define LL long long
const LL MAXN = ;
LL A, B;
LL num[MAXN], tot, f[MAXN][MAXN][MAXN];
LL dfs(LL x, bool lim, LL ze, LL on) {
if(x == ) return
(ze != -) && (on != -) && (ze >= on);
if(!lim && f[x][ze][on]) return f[x][ze][on];
LL ans = ;
for(LL i = ; i <= (lim ? num[x] : ); i++) {
if(i == ) ans += dfs(x - , lim && (i == num[x]), ze == - ? : ze + , on);
else {
if(on == -) ans += dfs(x - , lim && (i == num[x]), , );
else ans += dfs(x - , lim && (i == num[x]), ze, on + );
}
}
if(!lim) f[x][ze][on] = ans;
return ans;
}
LL solve(LL x) {
tot = ;
while(x) num[++tot] = x % , x >>= ;
return dfs(tot, , -, -);
}
int main() {
cin >> A >> B;
cout << solve(B) - solve(A - );
return ;
}
/*
1234 4444
2
*/

最新文章

  1. MySQL索引下推技术
  2. Universal Link 笔记
  3. POJ1014 解题报告(DFS)
  4. linux系统的任务计划crontab使用详解
  5. cobbler安装、部署、测试
  6. VMware安装的相关文章
  7. git patch
  8. android之TextView
  9. 《JavaScript模式》读书笔记
  10. Java笔记(二十七)&hellip;&hellip;IO流中 File文件对象与Properties类
  11. CocoaPods导入第三方库头文件自动补齐
  12. HDOJ(HDU) 1465 不容易系列之一(错排)
  13. ThinkPHP - 自定义标签库 - 标签驱动
  14. Android灯光系统--深入理解背光灯
  15. swift -- 代理delegate
  16. Dell poweredge r210进BIOS改动磁盘控制器(SATA Controller)接口模式
  17. 【BZOJ3309】DZY Loves Math
  18. ETL总结(扫盲版)
  19. 2018-2019-2 20165234 《网络对抗技术》 Exp2 后门原理与实践
  20. Beta 冲刺(7/7)

热门文章

  1. Ubuntu Hadoop环境搭建(Hadoop2.6.5+jdk1.8.0_121)
  2. DCloud-HTML5+:5+ App开发入门指南
  3. java&amp;nbsp;原始类与封装类&amp;nbsp;的区别
  4. Obama&amp;nbsp;unveils&amp;nbsp;his&amp;amp;nbsp…
  5. 利用mysql客户端查询UCSC数据库
  6. hdu2732 Leapin&#39; Lizards (网络流dinic)
  7. ZOJ 2671 Cryptography 矩阵乘法+线段树
  8. Spring入门第二十一课
  9. 10. windows下原来可以这样隐藏webshell
  10. SQL SERVER动态列名