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.


There are no comments at the moment.