找一个范围内二进制中0的个数大于等于1的个数的数的数量。基础的数位dp
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mem1(a) memset(a, -1, sizeof(a)) 4 int digit[50], dp[50][50][50], len; 5 int dfs(int len, int num0, int num1, int f, int first) { //first记录前面是否全部为0 6 if(!len) { 7 return num0>=num1; 8 } 9 if(!f&&!first&&dp[len][num0][num1]!=-1) 10 return dp[len][num0][num1]; 11 int ret = 0, maxx = f?digit[len]:1; 12 for(int i = 0; i<=maxx; i++) { 13 if(i == 0) { 14 ret += dfs(len-1, first?0:num0+1, num1, f&&i==maxx, first); 15 } else { 16 ret += dfs(len-1, num0, num1+1, f&&i==maxx, 0); 17 } 18 } 19 if(!f&&!first) 20 return dp[len][num0][num1] = ret; 21 return ret; 22 } 23 int cal(int n) { 24 len = 0; 25 while(n) { 26 digit[++len] = n&1; 27 n>>=1; 28 } 29 return dfs(len, 0, 0, 1, 1); 30 } 31 int main() 32 { 33 int a, b; 34 mem1(dp); 35 while(~scanf("%d%d", &a, &b)) { 36 printf("%d ", cal(b)-cal(a-1)); 37 } 38 }