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