Editorial for Số không (I)
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,k:longint; d:array[0..65] of byte; c:array[0..32,0..32] of longint; sl:array[0..32] of int64; re:int64; procedure init; var i:longint; begin fillchar(d,sizeof(d),0); i:=0; while n>0 do begin d[i]:=n mod 2; n:=n div 2; inc(i); end; num:=i; end; procedure ini; 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 work(k:longint); var i,num0,j:longint; begin fillchar(sl,sizeof(sl),0); for i:=1 to num-1 do for j:=1 to i-1 do sl[j]:=sl[j]+c[i-1,j]; num0:=0; for i:=num-2 downto 0 do if d[i]=1 then begin for j:=0 to i do sl[j+num0+1]:=sl[j+num0+1]+c[i,j]; end else inc(num0); num0:=0; for i:=0 to num-1 do if d[i]=0 then inc(num0); inc(sl[num0]); for i:=1 to 32 do for j:=(i-1)*k+1 to i*k do if j<=32 then re:=re+sl[j]*i; end; begin ini; while not eof do begin readln(n,k); if n=1 then begin writeln(0); continue; end; init; re:=0; work(k); writeln(re); end; end.
Code mẫu của happyboy99x
#include <iostream> #include <cstring> #include <cstdio> using namespace std; long long f[32][32][2][2]; int g[32][2][2]; int n; int k; int G(int bit, int smaller, int started) { if (bit == -1) return started; int &res = g[bit][smaller][started]; if (res != -1) return res; res = G(bit - 1, smaller | (n >> bit & 1), started); if (smaller == 1 || (n >> bit & 1) == 1) { res += G(bit - 1, smaller, 1); } return res; } long long F(int bit, int fromLastZero, int smaller, int started) { if (bit == -1) return 0; long long &res = f[bit][fromLastZero][smaller][started]; if (res != -1) return res; res = F(bit - 1, started == 1 ? (fromLastZero + 1) % k : 0, smaller | (n >> bit & 1), started) + (started == 1 && fromLastZero == 0 ? G(bit - 1, smaller | (n >> bit & 1), started) : 0); if (smaller == 1 || (n >> bit & 1) == 1) { res += F(bit - 1, fromLastZero, smaller, 1); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); while (cin >> n >> k) { memset(f, -1, sizeof f); memset(g, -1, sizeof g); printf("%lld\n", F(31, 0, 0, 0)); } return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Pham Quang Vu program VN_ZR_I; const inp=''; out=''; type mang=array[1..50] of longint; var fi,fo:text; n,k,nbit:longint; bit:mang; c:array[0..40,0..40] of int64; procedure openfile; begin assign(fi,inp);reset(fi); assign(fo,out);rewrite(fo); end; procedure getbit(x:longint;var c:mang;var top:longint); begin top:=0; while x>0 do begin inc(top); c[top]:= x and 1; x:=x shr 1; end; end; procedure init; var i,j:longint; begin for i:=0 to 34 do c[0,i]:=1; for i:=1 to 34 do begin c[i,i]:=1; for j:=i+1 to 34 do c[i,j]:=c[i,j-1]+c[i-1,j-1]; end; end; procedure solve; var count,i,j:longint; result:int64; begin getbit(n,bit,nbit); result:=0; for i:=nbit-1 downto 1 do for j:=1 to i-1 do result:=result+c[j,i-1]*((j-1) div k+1); count:=0; for i:=nbit-1 downto 1 do if bit[i]=1 then begin for j:=0 to i-1 do result:=result+c[j,i-1]*((j+count) div k+1); end else inc(count); if count>=1 then result:=result+(count-1) div k+1; writeln(fo,result); end; procedure enter; begin init; while not eof(fi) do begin readln(fi,n,k); if (n=0) and (k=0) then exit; solve; end; end; procedure closefile; begin close(fi); close(fo); end; begin openfile; enter; closefile; end.
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<sstream> #include<list> #define fi first #define se second #define PB push_back #define MP make_pair #define ep 0.00001 #define oo 111111111 #define mod 790972 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define rep(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) #define MS(a, x) memset(a, x, sizeof(a)) #define SZ(a) (int)(a.size()) #define maxn 505 //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long ll; int dx[] = {+1, 0, -1, 0}; int dy[] = {0, -1, 0, +1}; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } typedef long long ll; #define modun 2 int num, a[100]; ll dp[33][2][2][33]; long long n, m; ll go(int pos, int less, int zero, int cnt) { if (pos < 0){ if(!cnt) return 0; else return (cnt - 1)/ m + 1; } ll &ret = dp[pos][less][zero][cnt]; if (ret != -1) return ret; // cout << pos << " " << less << " " << zero << " " << cnt << endl; ret = 0; int maxd = less ? 1 : a[pos]; for (int d = 0; d <= maxd; ++d) { ret += go(pos - 1, less | (d < a[pos]), zero | d, cnt + (zero && (!d))); } return ret; } ll howmany(ll A) { if (A <= 0) return 0; num = 0; while (A > 0) { a[num++] = A & 1; A >>= 1; } memset(dp, -1, sizeof(dp)); return go(num - 1, 0, 0, 0); } ll solve(ll A, ll B) { if (A == 0) { if (B == 0) return 1; return howmany(B) + 1; } return howmany(B) - howmany(A - 1); } int main(){ //OPEN(); while(scanf("%lld %lld", &n, &m) > 0){ printf("%lld\n", howmany(n)); } }
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() { ll ret = 0; digit = 0; int tmp = n; while (tmp) { d[++digit] = tmp % 2; tmp /= 2; }; for (int i = 1; i < digit; i++) { tmp = calc(i); //if (i == 2) cout << "query: " << i << ' ' << tmp << endl; ret += 1LL * tmp * ((i + k - 1)/k); }; return ret; }; int main() { // freopen("zr.in","r",stdin); // freopen("zr.ou","w",stdout); getC(); while (cin >> n >> k) cout << solve() << endl; };
Code mẫu của khuc_tuan
#include "stdio.h" #include "string.h" int n, k; int a[40], b[40]; long long result; long C[33][33]; void tinh(int i,int sk) { for(int j=0;j<=i;++j) { if(j+sk>0) result += C[j][i] * ((j+sk-1)/k+1); } } void duyet(int i, int sk) { if(i<0) { if(sk>0) result += (sk-1)/k + 1; return; } bool nhohon = false, lonhon = false; for(int j=33;j>i;--j) { if(a[j]>b[j]) { nhohon = true; break; } if(a[j]<b[j]) { lonhon = true; break; } } if(nhohon) { tinh(i+1,sk); return; } if(lonhon) return; b[i] = 0; duyet(i-1,sk+1); if(a[i]==1) { b[i] = 1; duyet(i-1,sk); } } void run() { memset( a, 0, sizeof(a)); memset( b, 0, sizeof(b)); int last=-1; for(int i=0;i<31;++i) if((n&(1<<i))!=0) { a[i] = 1; last = i; } result = 0; for(int i=last;i>=0;--i) { memset( b, 0, sizeof(b)); b[i] = 1; duyet(i-1,0); } printf("%lld\n",result); } void init() { C[0][0] = 1; for(int i=1;i<33;++i) { C[0][i] = C[i][i] = 1; for(int j=1;j<i;++j) C[j][i] = C[j-1][i-1] + C[j][i-1]; } } int main() { init(); while(true) { n = -11; scanf("%d%d",&n,&k); if(n==-11) break; run(); } }
Comments