做題記錄2021.6.12

思路：分為最高位為0和1計算。注意：n的二進制位位數為 m = [ l o g 2 n ] + 1 m=[log_2 n]+1 m=[log2​n]+1。

最高位為0時，後面的各二進制位可以任意取0或1，共 C m k C_m^k Cmk​種情況。

最高位為1時，這個我還真沒想出來，隻能暴力求解。可以減少求解次數，比如k=2，m=10，可以從513(1000000001)求解到min(n,768(1100000000))。

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long int64;
int k=10,bin[64];
int64 combin(int t,int b=k) {
	if(t==k+1)	return 1;
	if(b>t/2)	b=t-b; //加一句
    int64 fz=1,fm=1;
    for(int64 i=t;i>t-b;i--)
        fz*=i;
    for(int64 i=b;i>1;i--)
        fm*=i;
    return fz/fm;
}

void add(int t,int &last) {
    for(int i=t-1;i>=0;i--) {
        if(bin[i]==0) {
            bin[i]=1;
            last++;
            return;
        }
        else if(bin[i]==1){
            bin[i]=0;
            last--;
        }
    }
}

int64 minnum(int wei) {
	int64 res=0;
	for(int i=0;i<k-1;i++) {
		res+=(int64)pow(2,i);
	}
	res+=pow(2,wei-1);
	return res;
}

int64 maxnum(int wei) {
	int64 res=0;
	for(int i=wei-1;i>=wei-k;i--) {
		res+=(int64)pow(2,i);
	}
	return res;
}

int main(){
    int64 n,t,res=0;
    int one=0;
    scanf("%I64d%d",&n,&k);
	for(t=0;(int64)pow(2,t)<=n;t++);
    res=combin((int)(t-1)); //最高位非0的情況
    //最小數為100....11（共t位，有k個1，除最高位外的k-1個1均在最低位連續排列）
	//最大為111....00（共t位前k個為1）
	int64 minn=minnum(t),maxn=maxnum(t),tmp=minn;
	//預處理最小數
	for(int i=0;i<t;i++) {
        bin[t-i-1]=tmp%2;
        if(bin[t-i-1]==1)   one++;
        tmp/=2;
	}
	if(one==k)  res++;
	//不用每個數都轉二進制
	//時間複雜度與n轉換為二進制後與11....000（共t位，前k個為1）的差有關，與n大小關系較小
	for(int64 j=minn+1;j<=maxn&&j<=n;j++) {
		add(t,one);
		if(one==k)  res++;
	}
	printf("%I64d",res);
    return 0;
}