题意：
给定m，k
0 <= m <= 10^18 ,1 <= k <= 64
求一个数n，满足n+1,n+2,...n+n这n个数中，刚好有m个数的2进制表示法刚好有k个1
保证答案在10^18内
思路：
显然，
对于x，如果x+1,x+2,...,x+x有y个数有k个1
对于x+1,则x+2,x+3,...,x+x+2有k个1的数的个数 >= y
满足单调性，考虑二分：
L = m，r = 10^18
那么问题变为：给定一个数x，x+1,x+2,...,x+x中刚好有k个1的数有多少个
为了方便表达，假设x是2进制数：
则出现k个1的区间有：
[x,11...111],[10...000,2x]
即按照位数分成2段计算
函数go(LL x,int k)作用：求[x,1111111]这个区间中有k个1的数有多少个
则ans = go(x,k) + go(10...000,k) - go((x<<1)&1,k)
判断ans与m的关系就可以不断缩小L,R的范围啦
注意：
求2^x如果用(1 << x)的话，这个时候(1 << x)是默认为int型的，
所以如果超int了，要用(1LL << x)
代码：
//File Name: cf431D.cpp //Author: long //Mail: 736726758@qq.com //Created Time: 2016年07月09日 星期六 21时34分35秒 #include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #define LL long long using namespace std; int a[100],tot; LL f[100][100]; void init(){ memset(f,0,sizeof f); for(int i=0;i<100;i++){ f[i][0] = 1; for(int j=1;j<=i;j++) f[i][j] = f[i-1][j] + f[i-1][j-1]; } } LL go(LL x,int k){ tot = 0; while(x){ a[++tot] = x % 2; x >>= 1; } LL ans = 0; int pre = 0; for(int i=tot;i>0;i--){ if(a[i] == 1) pre++; else{ if(k - pre - 1 >= 0) ans += f[i-1][k-pre-1]; else break; } } if(pre == k) ans++; return ans; } LL get(LL x,int k){ LL ans = go(x,k); LL y = (1LL << tot); //printf("x = %lld y = %lld\n",x,y); ans = ans + go(y,k) - go(2 * x + 1,k); return ans; } LL solve(LL m,int k){ LL l = m,r = (LL)1e18 + 1,mid; while(r - l > 1){ mid = (l + r) >> 1; LL cur = get(mid,k); //printf("mid = %lld cur = %lld\n",mid,cur); if(cur <= m) l = mid; else r = mid; } if(get(l,k) == m) return l; else return r; } int main(){ init(); LL m; int k; cin >> m >> k; cout << solve(m,k) << endl; return 0; }
原文：http://www.cnblogs.com/-maybe/p/5656824.html