题意
给出区间$[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 = 101; LL A, B; LL num[MAXN], tot, f[MAXN][MAXN][MAXN]; LL dfs(LL x, bool lim, LL ze, LL on) { if(x == 0) return (ze != -1) && (on != -1) && (ze >= on); if(!lim && f[x][ze][on]) return f[x][ze][on]; LL ans = 0; for(LL i = 0; i <= (lim ? num[x] : 1); i++) { if(i == 0) ans += dfs(x - 1, lim && (i == num[x]), ze == -1 ? 1 : ze + 1, on); else { if(on == -1) ans += dfs(x - 1, lim && (i == num[x]), 0, 1); else ans += dfs(x - 1, lim && (i == num[x]), ze, on + 1); } } if(!lim) f[x][ze][on] = ans; return ans; } LL solve(LL x) { tot = 0; while(x) num[++tot] = x % 2, x >>= 1; return dfs(tot, 1, -1, -1); } int main() { cin >> A >> B; cout << solve(B) - solve(A - 1); return 0; } /* 1234 4444 2 */
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
