Hướng dẫn giải của Số không (I)
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,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(); } }
Bình luận