电子商务网站建设的书,wordpress 边框,wordpress小说系统,北京网络营销北京正题 大意
求一个闭区间内二进制0的个数大于等于1的个数的数的数量。 解题思路
我们将二进制考虑成01串 我们先不考虑有前导零的情况#xff1a; 在kk个空位中放i role=presentation style=position: relative;ii个0#xff0c;别的都…正题 大意
求一个闭区间内二进制0的个数大于等于1的个数的数的数量。 解题思路
我们将二进制考虑成01串 我们先不考虑有前导零的情况 在kkk个空位中放i" role="presentation" style="position: relative;">iii个0别的都放1的方案数为CikCkiC_k^i(我们将一个位置放0表示成取出这个位置的数)。 然后我们可以先计算1∼r1∼r1\sim r然后减去1∼l−11∼l−11\sim l-1就是l∼rl∼rl\sim r这个区间内的数量。 我们考虑计算 如一个数121212我们将它转换为二进制100101001010010。我们先计算1∼100001∼100001\sim 10000中的数量我们可以先枚举位数然后我们保证第一位是1后后面的就是在剩余空位中放置满足个数要求的情况。 然后我们开始考虑后面的我们可以发现如果我们从大到小枚举到一位数是111，那么如果我们将其改为0" role="presentation" style="position: relative;">000然后后面无论如何填入都无需考虑大小所有我们可以利用这个性质计算如果是111就该为0" role="presentation" style="position: relative;">000统计答案之后该回11script typemath/tex idMathJax-Element-22451/script继续往后因为这个位数是0的情况都计算完了。 Code
#includecstdio
#includecmath
#define ll long long
#define find_c(x,y) c[x1][y1]
#define w 31
using namespace std;
ll first,second,c[w2][w2],f[w2];
void make_C()
{c[1][1]1;c[2][1]1;c[2][2]1;for (ll i3;iw1;i)for (ll j1;ji;j)c[i][j]c[i-1][j]c[i-1][j-1];//预处理组合数
}
int answer(ll x,ll y)//计算在k个位中填01并且前面已经有y个1的合法情况总数
{int ans0;for (int i0;ix;i)if (ix-iy)//满足条件ansfind_c(x,i);//计算答案return ans;
}
int work(ll x)
{if (x0) return 0;ll klog2(x)1,ans0,now1,one1;for (int i1;ik;i)ansanswer(i-1,1),now1;//计算答案k--;now1;//无视第一位(前面已经计算过了)while(k){if (xnow) ansanswer(k-1,one-1),one1;//可以计算答案else one-1;//统计零一个数k--;now1;//下一位}if (one0) ans;//判断本身是否满足要求return ans;
}
int main()
{make_C();scanf(%d%d,first,second);printf(%d,work(second)-work(first-1));
}
