DP - 디지털 DP - 도의 수량

DP - 디지털 DP - 도의 수량
주어진 구간 [X, Y] 에서 다음 조건 을 만족 시 키 는 정수 개 수 를 구하 십시오. 이 수 는 K 개의 서로 다른 B 의 정수 차 멱 의 합 과 같 습 니 다.
예 를 들 어 X = 15, Y = 20, K = 2, B = 2 를 설정 하면 다음 세 개의 숫자 만 문제 의 뜻 을 만족 시 킬 수 있다.
17 = 24 + 20 18 = 24 + 21 20 = 24 + 22 입력 형식 첫 줄 은 두 개의 정수 X 와 Y 를 포함 하고 그 다음 두 줄 은 정수 K 와 B 를 포함한다.
출력 형식 은 하나의 정수 만 포함 하고 조건 을 만족 시 키 는 수의 개수 만 표시 합 니 다.
데이터 범위 1 ≤ X ≤ Y ≤ 231 − 1, 1 ≤ K ≤ 20, 2 ≤ B ≤ 10

    ：
15 20
2
2
    ：
3

분석:
접두사 와 사상 을 통 해 접두사 와 사상 을 먼저 구하 고 접두사 와 사상 을 먼저 구하 고 1 ~ N 에서 조건 을 만족 시 키 는 수의 S n 을 먼저 구하 고 구간 [l, r] 중의 개 수 = S r - S l - 1 을 구한다.N 중 조건 을 만족 시 키 는 수의 개수 Sn, 구간 [l, r] 의 개수 = Sr-S_{l-1}。 N 에서 조건 을 만족 시 키 는 수의 개 수 는 Sn 이 고 구간 [l, r] 중의 개 수 는 = Sr - Sl - 1 이다.
C o u n t 함 수 는 1 Count 함 수 를 구하 고 1 Count 함 수 는 1 ~ N 에서 조건 을 만족 시 키 는 수의 개 수 를 구하 고 N 을 먼저 B 진수 로 바 꾸 어 배열 에 저장 합 니 다.N 에서 조건 을 만족 시 키 는 수의 개 수 는 N 을 먼저 B 진수 로 바 꾸 어 배열 에 저장 합 니 다.N 에서 조건 을 만족 시 키 는 수의 개 수 는 N 을 먼저 B 진수 로 바 꾸 어 배열 에 저장 합 니 다.
제목 에 따 르 면 K 개 B i 차방 의 수의 합 을 적당 하 게 표시 해 야 한다. 등가 가 B 진법 표시 하에 K 비트 가 1 이 고 나머지 는 0 이다.제목 에 따 르 면 K 개 B ^ i 차방 의 수의 합 을 적당 하 게 나타 내 고 B 진법 은 K 비트 가 1 이 고 나머지 는 0 임 을 나타 낸다.제목 에 따 르 면 K 개 Bi 차방 의 수의 합 을 적절하게 표시 해 야 한다. 등가 가 B 진법 표시 하에 K 자리 가 1 이 고 나머지 는 0 이다.
문 제 는 N 의 B 진법 표시 에서 K 개의 위치 에서 1 을 취 하 는 모든 취 법 을 선택 한 방안 의 총수 로 바 뀌 었 다.문 제 는 N 의 B 진법 표시 에서 K 개의 위치 에서 1 을 취 하 는 모든 취 법 을 선택 한 방안 의 총수 로 바 뀌 었 다.문 제 는 N 의 B 진법 표시 에서 K 개의 위치 에서 1 을 취 하 는 모든 취 법 을 선택 한 방안 의 총수 로 바 뀌 었 다.
높 은 자리 에서 낮은 자리 까지 순서대로 옮 겨 다 니 고 높 은 자리 에서 낮은 자리 까지 순서대로 옮 겨 다 니 며 N 을 설정 한 B 진 은 V = a n - 1 a n - 2 를 나타 낸다. a 0 은 현재 l a s t 개 를 선택 했다.{n-1}a_{n-2}...a_{0}, 현재 last 개 '1' 을 선 택 했 습 니 다. N 을 설정 한 B 진 은 V = an - 1 an - 2... a0 이 고, 현재 last 개 를 선 택 했 습 니 다.
①, 만약 a i > 0: I, 우 리 는 i 위 를 0 으로 취 할 수 있다. 그러면 a i - 1... a 0 은 어떤 값 을 취하 든 V 보다 크 지 않 을 것 이다.총 방안 수 는 C i K - l a s t 이다. 즉, 나머지 i 자리 에서 K - l a s t 의 위 치 를 선택 하면 좋 을 것 같다.① 、 약 ai > 0: \ \ \ \ qquad I 、 우 리 는 i 위 를 0 으로 취 할 수 있 습 니 다. 이렇게 a{i-1}...a_0 어떤 값 을 취하 든 V 보다 크 지 않 습 니 다.총 방안 수 는 Ci ^ {K - last}, \ \ \ qquad 는 남 은 i 자리 에서 K - last 위 치 를 선택 하여 '1' 을 가 져 옵 니 다.①, 만약 ai > 0: I, 우 리 는 i 위 를 0 으로 취 할 수 있다. 그러면 ai - 1... a0 은 어떤 값 을 취하 든 V 보다 크 지 않 을 것 이다.총 방안 수 는 CiK - last, 즉 남 은 i 비트 에서 K - last 의 위 치 를 선택 하면 좋 을 것 같 아.
II 、 우 리 는 i 위 를 1 로 취 할 수 있 습 니 다. 만약 a i > 1, a i - 1... a 0 은 어떤 값 을 취하 든 V 보다 크 지 않 습 니 다.총 방안 수 는 C i K - l a s t - 1 이다. 즉, 나머지 i 자리 에서 K - l a s - 1 자 리 를 선택 하면 좋 을 것 같다.이 때 모든 합 법 적 인 방안 이 계산 되 어 순환 을 종료 합 니 다. \qquad II 、 우 리 는 i 위 를 1 로 취 할 수 있 습 니 다. \ \ \ qquad 약 ai>1，a_{i-1}...a_0 어떤 값 을 취하 든 V 보다 크 지 않 습 니 다.총 방안 수 는 Ci ^ {K - last - 1}, \ \ \ qquad 는 남 은 i 자리 에서 K - last - 1 위 치 를 선택 하여 '1' 을 가 져 옵 니 다.이때 모든 합 법 적 인 방안 이 계산 되 어 순환 을 종료 합 니 다.II 、 우 리 는 i 위 를 1 로 취 할 수 있 습 니 다. 만약 ai > 1, ai - 1... a0 은 어떤 값 을 취하 든 V 보다 크 지 않 습 니 다.총 방안 수 는 CiK - last - 1, 즉 나머지 i 자리 에서 K - last - 1 자 리 를 선택 하면 좋 을 것 같 아.이때 모든 합 법 적 인 방안 이 계산 되 어 순환 을 종료 합 니 다.
만약 a i = 1, 뒤의 취 법 은 제 I 단계 에서 계산 되 기 때문에 여기 서 중복 계산 할 필요 가 없습니다. l a s t + + 후 바로 다음 자 리 를 보 세 요. \qquad 약 ai = 1, 뒤의 취 법 은 I 단계 에서 계 산 될 것 이 므 로 중복 계산 하지 않 아 도 됩 니 다. last + 후 바로 다음 을 볼 수 있 습 니 다.ai = 1 이면 뒤의 취 법 은 제 I 단계 에서 계 산 될 것 이 므 로 중복 계산 할 필요 가 없습니다. last + 후 바로 다음 을 보 세 요.
② 、 만약 a i = 0: 뒤의 합 법 적 인 방안 도 ① - I 에서 계산 되 고 다음 사람 을 직접 볼 수 있다.② 、 만약 ai = 0: 뒤의 합 법 적 인 방안 역시 ① - I 에서 계산 되 고 다음 사람 을 직접 볼 수 있다.② 、 만약 ai = 0: 뒤의 합 법 적 인 방안 도 ① - I 에서 계산 되 어 다음 을 직접 볼 수 있다.
③ 、 마지막 으로 a 0 시 에 K 개 1 을 취 했 음 을 감안 하면 V 의 a i 위 는 모두 1 이 고 답 은 V 와 같은 방안 을 더 해 야 한다.③ 、 마지막 으로 a0 시 에 K 개 1 을 가 져 와 V 의 a 를 설명 합 니 다.i 위 는 모두 1 이 고 답 은 V 와 같은 방안 을 더 해 야 한다.③ 、 마지막 으로 a0 시 에 K 개 1 을 취 했 음 을 감안 하면 V 의 ai 위 는 모두 1 이 고 답 은 V 와 같은 방안 을 더 해 야 한 다 는 것 을 의미한다.
코드:

#include
#include

using namespace std;

const int N=35;

int K,B;
int C[N][N];

void cal()
{
     
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j) C[i][j]=1;
            else C[i][j]=C[i-1][j]+C[i-1][j-1];
}

int dp(int n)
{
     
    if(!n) return 0;
    vector<int> V;
    while(n) V.push_back(n%B),n/=B;
    
    int res=0,last=0;
    for(int i=V.size()-1;i>=0;i--)
    {
     
        int x=V[i];
        if(x)
        {
     
            res+=C[i][K-last];
            if(x>1)
            {
     
                if(K-last-1>=0) res+=C[i][K-last-1];
                break;
            }
            else
            {
     
                last++;
                if(last>K) break;
            }
        }
        if(i==0 && last==K) res++;
    }
    
    return res;
}

int main()
{
     
    cal();
    
    int l,r;
    cin>>l>>r>>K>>B;
    
    cout<<dp(r)-dp(l-1)<<endl;
    
    return 0;
}