BINARY - Số nhị phân có nghĩa
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#define MAX 37
typedef long long ll;
ll f[MAX][MAX];
ll p[MAX];
ll n,k;
void finit(void) {
ll i,j;
p[0]=1;
for (i=1;i<=34;i=i+1) p[i]=p[i-1]*2;
for (i=0;i<=34;i=i+1) f[0][i]=1;
for (i=1;i<=34;i=i+1) f[i][0]=0;
for (i=1;i<=34;i=i+1)
for (j=1;j<=34;j=j+1) {
if (i>j) f[i][j]=0;
if (i==j) f[i][j]=1;
if (i<j) f[i][j]=f[i][j-1]+f[i-1][j-1];
}
}
ll c(const ll &k,const ll &n) {
//printf("Requests for %lld %lld\n",k,n);
if (k<0) return (0);
if (n<0) return (0);
return (f[k][n]);
}
ll nbit(const ll &x) {
ll i=0;
while (p[i]<=x) i++;
return (i);
}
void process(void) {
ll m,i,t,r;
if (n==0) {
printf("%d\n",k==1);
return;
}
t=nbit(n);
if (k>=t) {
printf("0\n");
return;
}
//printf("%lld\n",t);
r=0;
m=0;
for (i=t-1;i>=1;i=i-1) r=r+c(k,i-1);
//printf("%lld\n",r);
for (i=t-2;i>=0;i=i-1) {
if ((n|p[i])==n) r=r+c(k-m-1,i);
else m=m+1;
}
if (m==k) r++;
if (k==1) r++;
printf("%lld\n",r);
}
int main(void) {
finit();
while (scanf("%lld %lld",&n,&k)==2) process();
return 0;
}