DEGREE - Số lượng bậc

Tác giả: RR

Ngôn ngữ: C++

#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;
}

Download