Hướng dẫn giải của Số nhị phân có nghĩa
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận