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.
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