Editorial for Số lượng bậc


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

const fi='';
      fo='';
var a,b,k,x,re:longint;
    c:array[0..32,0..32] of longint;

procedure rf;
var i,j:longint;
begin
     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;
     read(a,b,k,x);
end;

function calc(n:longint):longint;
var a:array[1..32] of longint;
    i,num,re,num1,dem:longint;
begin
     calc:=0;
     if n=0 then exit;
     num:=0; dem:=0;
     while n>0 do
     begin
          inc(num);
          a[num]:=n mod x;
          if dem>=0 then
          begin
               if a[num]>1 then dem:=-1
               else dem:=dem+a[num];
          end;
          n:=n div x;
     end;
     re:=0; num1:=0;
     for i:=num downto 1 do
         if a[i]>=1 then
         begin
              re:=re+c[i-1,k-num1];
              if a[i]>1 then 
              begin
                   re:=re+c[i-1,k-num1-1];
                   break;
              end;
              inc(num1);
              if num1>k then break;
         end;
     if dem=k then inc(re);
     calc:=re;
end;

procedure wf;
begin
     writeln(calc(b)-calc(a-1));
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     wf;
     close(input); close(output);
end.

Code mẫu của RR

#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

long long power[33], c[33][33];

long long get(long long x, int k, int gh) {
    if (x == 0) {
        if (k) return 0;
        else return 1;
    }

    if (x < 0) { return 0; }
    if (k == 0) return 1;

    if (k < 0) return 0;

    if (k > gh+1) return 0;
    if (gh < 0) return 0;

//    cout << x << " " << k << " " << gh << endl;

    long long sum = 0;
    REP(i,k) sum += power[gh-i];
    if (sum <= x) {
//        cout << "get = " << c[gh+1][k] << endl;
        return c[gh+1][k];
    }

    long long res = 0;
    if (x >= power[gh]) res = get(x-power[gh], k-1, gh-1);
    res += get(x, k, gh-1);
//    cout << "get = " << res << endl;
    return res;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    c[0][0] = 1;
    FOR(i,1,32) {
        c[i][0] = 1;
        FOR(j,1,i)
            c[i][j] = c[i-1][j-1] + c[i-1][j];
    }

    long long x, y, b;
    int k, gh;

    cin >> x >> y;
    cin >> k >> b;
    gh = 0; power[gh] = 1;
    while (power[gh] <= y) {
        gh++;
        power[gh] = power[gh-1] * b;
    }
    gh--;
    cout << get(y,k,gh) - get(x-1,k,gh);
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
int x,y,b,k,kq,C[33][33];

int Round(double x)
{
    if(x > 0)
       return int(x + 0.5);
    if(x < 0)
       return int(x - 0.5);
    return 0;
}

void doc()
{
     scanf("%d %d %d %d",&x,&y,&k,&b);
for(int i=0;i<=32;i++)
  for(int j=0;j<=32;j++)
    C[i][j]=0;
for(int i=0;i<=32;i++)    
  C[0][i]=1;
for(int i=1;i<=32;i++)    
  for(int j=1;j<=i;j++)
    C[j][i]=C[j][i-1]+C[j-1][i-1];
}

void xuat()
{
     printf("%d\n",kq);
}

int Cal(int a,int k)
{
 int i,n1,n,tmp,bn;
      tmp=0;
      n1 = 100000;
      while(true)
      {
         if( k == 0)
            {
               tmp=tmp+1;
               break;
            }
         else if (a < 1)  break ;
         n = int ( log(a) / log(b) ) ;
         if (n >= n1) n = n1 - 1 ;
         if (n ==-1 ) break;
         tmp = tmp + C [k][n] ;
         bn  = Round ( pow (b,n) ) ;
         a = a - bn ;
         k = k - 1 ;
         n1= n ;
      }
      return tmp ;
}
void lam()
{
   int tmp1,tmp2;
      tmp1 = Cal(x-1,k) ;
      tmp2 = Cal(y,k) ;
      kq= tmp2 - tmp1 ;
}
int main()
{
      doc();
      lam();
      xuat();
}

Code mẫu của khuc_tuan

var
   xxx, result, na, x, y, k, b : longint;
   a : array[1..100] of longint;

procedure them(scs, sb : longint);
var
   j, i, r : longint;
begin
    r := 1;
    j := 2;
    for i:=scs downto scs-sb+1 do begin
        r := r * i;
        while (j<=sb) and (r mod j=0) do begin
            r := r div j;
            inc(j);
        end;
    end;
{    for i:=1 to sb do r := r * (b-1);}
{    if sb>scs then r:=0;}
{writeln( scs,' ',sb,' ',r);}
    result := result + r;
end;

procedure duyet(i, sb : longint);
begin
     if sb>k then exit;
     if i=0 then begin
         if sb=k then inc(result);
         exit;
     end;
     if a[i]=0 then begin
         duyet(i-1,sb);
         exit;
     end;
     if a[i]>1 then begin
        them(i,k-sb);
        exit;
     end;
     them(i-1,k-sb);
     duyet(i-1,sb+1);
end;

procedure tinh(x : longint);
var
   i : integer;
begin
     na := 0;
     while x<>0 do begin
        inc(na);
        a[na] := x mod b;
        x := x div b;
     end;
{     for i:=1 to na do write(a[i],' ');
     writeln;}
     result := 0;
     duyet(na, 0);
end;

begin
   read(x, y, k, b);
   tinh(y);
   xxx := result;
{   writeln(result);}
   tinh(x-1);
   xxx := xxx - result;
{   writeln(result);}
   writeln(xxx);
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.