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.

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

Please read the guidelines before commenting.


There are no comments at the moment.