好像很久没有发过题解了。。。

最近沉迷阅读无法自拔,《作为意志和表象的世界》和 The Great Gatsby 真好看。

Ural 原题地址

LibreOJ 原题地址

Statement

Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
$17 = 2^4+2^0$,
$18 = 2^4+2^1$,
$20 = 2^4+2^2$.

Input

The first line of input contains integers X and Y, separated with a space $(1 ≤ X ≤ Y ≤ 2^{31}−1)$. The next two lines contain integers K and B $(1 ≤ K ≤ 20; 2 ≤ B ≤ 10)$.

Output

Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.

思路

一道经典的数位 DP 题。
这道题说白了就是直接求前缀和然后相减得到区间的答案。对于一个上限,直接把它转化成 b 进制数,然后讨论每一位的情况。

代码

  1. oyyj603470138
    Sep 24, 2018

    两位大佬。。

    Reply
    • crazydavehdy
      Sep 25, 2018

      %%%大佬

      Reply
  2. CrazyDave
    Sep 16, 2018

    orz

    Reply