Editorial for Số nhị phân có nghĩa

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

var n,num,re,k:longint;
    d:array[0..65] of byte;
    c:array[0..32,0..32] of longint;

procedure rf;
var i,t:longint;
begin
     readln(n,k);
     fillchar(d,sizeof(d),0);
     i:=0;
     t:=n;
     while n>0 do
     begin
          if n mod 2 = 1 then d[i]:=1;
          n:=n div 2;
          inc(i);
     end;
     n:=t;
     num:=i;
end;

procedure init;
var i,j:longint;
begin
     fillchar(c,sizeof(c),0);
     c[0,0]:=1;
     for i:=1 to 32 do
     begin
          c[i,0]:=1;
          c[i,i]:=1;
          for j:=1 to i-1 do
              c[i,j]:=c[i-1,j]+c[i-1,j-1];
     end;
end;

procedure pr;
var i,num0:longint;
begin
     if (k=1) or (k=0) then re:=1 else re:=0;
     if n=1 then exit;
     {So chu so < n}
     for i:=2 to num-1 do
         if k<=i-1 then re:=re+c[i-1,k];
     {So chu so = n}
     num0:=0;
     for i:=num-2 downto 0 do
         if d[i]=1 then
         begin
              if k-num0-1<=i then
                 re:=re+c[i,k-num0-1];
         end
         else
         begin
              inc(num0);
              if num0>k then break;
         end;
     num0:=0;
     for i:=0 to num-1 do num0:=num0+d[i];
     if num0+k=num then inc(re);
end;

begin
     init;
     while not eof do
     begin
          rf;
          pr;
          writeln(re);
     end;
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
using namespace std;

int n,k,c[40][40],a[40];

void init() {
    FOR(i,0,33) {
        c[i][0]=1;
        FOR(j,1,i)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
}

int get(int pos,int s0) {
    if (pos==0) {
        if (s0==0) return 1;
        else return 0;
    }
    int res=0;
    if (a[pos]) {
        //0
        if (pos<a[0] && s0>0) res=c[pos-1][s0-1];
        //1
        res+=get(pos-1,s0);
    }
    else {
        //0
        if (s0>0) res=get(pos-1,s0-1);
    }
    return res;
}

void solve() {
    a[0]=0;
    int saven=n;
    while (n) {
        a[++a[0]]=n&1;
        n>>=1;
    }
    n=saven;

    if (k>a[0]) {
        printf("0\n");
        return ;
    }

    int res=get(a[0],k);
    FOR(l,1,a[0]-1)
        res+=c[l-1][k];
    if (k==1) res++;
    printf("%d\n",res);
}

int main() {
    init();
    while (scanf("%d %d",&n,&k)==2) {
        if (n==0) {
            if (k==1) printf("1\n");
            else printf("0\n");
        }
        else solve();
    }
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long C[34][34],a[34],n,k;
for(long i=0;i<=32;i++)
  for(long j=0;j<=32;j++)
    C[i][j]=0;
for(long i=0;i<=32;i++)
  C[0][i]=1;
for(long i=1;i<=32;i++)
  for(long j=1;j<=i;j++)
    {
    C[j][i]=C[j][i-1]+C[j-1][i-1];
    //printf("%ld ",C[j][i]);
    }  
//printf("%ld %ld %ld",C[14][32],C[32][32],C[16][32]);    
while(scanf("%ld %ld",&n,&k)>0)
  {
  long dem=0;
  long KQ=0;
  long t=0;               
  while(n!=0)
    {
    t++;
    a[t]=n%2;
    n=n/2;
    }
  if((k>=t&&k!=1)||k<0)
    printf("0\n");
  else
  {    
  for(long i=t-2;i>=k;i--)
    KQ=KQ+C[k][i];
  for(long i=t-1;i>=1;i--)
    if(a[i]==1)
      {
      if(k-t+i+dem>=0)
        {
        KQ=KQ+C[k-t+i+dem][i-1];
        //printf("%ld %ld %ld %ld",k,t,i,dem);
        }
      dem++;
      }
  if(t-dem-1==k)
  KQ++;
  if(k==1)
  KQ++;    
  printf("%ld\n",KQ);
  }
  }
//getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int n,k;
int c[34][34];
int digit,d[34];

void getC()
{
     memset(c,0,sizeof(c));
     for (int i = 0; i <= 32; i++) c[0][i] = 1;
     for (int j = 1; j <= 32; j++)
       for (int i = 1; i <= 32; i++) c[i][j] = c[i - 1][j - 1] + c[i][j - 1];     
};

ll rec(int pos,int p)
{
   if (p < 0) return 0;
   if (!pos) return (p == 0) ? 1 : 0;
   if (d[pos] == 0) return (rec(pos - 1,p - 1));
   else
   {
     ll tmp = rec(pos - 1,p);
     if (p) tmp += c[p - 1][pos - 1];
//     cout << "answer: " << pos << ' ' << p << ' ' << tmp << endl;
     return tmp;
   };
};

ll calc(int x)
{
   //x zeroes in the numbers
//   if (x != 2) return 0;
   ll ret = 0;
   for (int i = 2; i < digit; i++) ret += c[x][i - 1];
//   cout << ret << endl;
   ret += rec(digit - 1,x);
   return ret;
};

ll solve()
{
   if (k > 31) return 0;
   if (!n) return (k == 1) ? 1 : 0;
   digit = 0;  int tmp = n;
   while (tmp)
   {
         d[++digit] = tmp % 2;  tmp /= 2;
   };
   ll ret = calc(k);  if (k == 1) ret++;
   return ret;
};

int main()
{
//    freopen("binary.in","r",stdin);
//    freopen("binary.ou","w",stdout);
    getC();
    while (cin >> n >> k) cout << solve() << endl;
};

Code mẫu của skyvn97

#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;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int F[33][2][2][33];
int n, k;

int go(int pos, int greZ, int isLess, int totalZ) {
    if(pos<0) return totalZ == k;
    int & ret = F[pos][greZ][isLess][totalZ];
    if(ret!=-1) return ret;
    int cur = (n >> pos) & 1;
    ret = 0;
    for(int ad=0;ad<2;++ad) if(isLess || (ad <= cur))
        ret += go( pos - 1, greZ || (ad > 0), isLess || (ad < cur), totalZ + (ad == 0 && greZ));
    return ret;
}

int main() {
    while(scanf("%d%d", &n, &k)!=EOF) {
        memset( F, -1, sizeof(F));
        cout << go( 30, 0, 0, 0) + (k==1) - (k==0) << endl;
    }   
    return 0;
}

Comments

Please read the guidelines before commenting.

-8

trongorigami123 commented on July 11, 2025, 4:12 a.m.

em tui nó phá sorry khuctuan nha, nó còn nhỏ có biết gì đâu

This comment is hidden due to too much negative feedback. Show it anyway.

-6

trongorigami123 commented on July 11, 2025, 4:11 a.m.

mình thành thật xin lỗi, em mình không biết nên chat hơi toxic, xin lỗi tài khoản khuc tuan nói riêng và cả cộng động vnoi

This comment is hidden due to too much negative feedback. Show it anyway.

5

pppssslc commented on July 11, 2025, 1:36 a.m.

Đây là môi trường học tập văn minh, tại sao bạn lại có những lời lẽ thô tục, thiếu văn minh và vô văn hóa như vậy.

-8

trongorigami123 commented on July 11, 2025, 1:23 a.m. ← edit 2 →

em xin lỗi

This comment is hidden due to too much negative feedback. Show it anyway.

-11

trongorigami123 commented on July 11, 2025, 1:22 a.m. ← edit 2 →

xin lỗi

This comment is hidden due to too much negative feedback. Show it anyway.

-17

trongorigami123 commented on July 7, 2025, 2:03 a.m. ← edit 7 →

xin lỗi

This comment is hidden due to too much negative feedback. Show it anyway.

-16

trongorigami123 commented on July 7, 2025, 1:58 a.m. ← edit 2 →

thành thật xin lỗi

This comment is hidden due to too much negative feedback. Show it anyway.

-16

trongorigami123 commented on July 7, 2025, 1:56 a.m. ← edited →

xin lỗi

This comment is hidden due to too much negative feedback. Show it anyway.

-14

trongorigami123 commented on July 7, 2025, 2:08 a.m. ← edit 2 →

xin lỗi

This comment is hidden due to too much negative feedback. Show it anyway.