x==0:我啥也填不了，没有择偶权😢；

res+=f[i][k-last]:我这位不填1，交给后辈去填吧；

if（x>1）：我这里只能填1😢，剩下的k-last-1个1，你们随便填，反正合法的只有f[i][k-lase-1]种，我已经得到答案了，所以我直接break；

如果x==1:我这里已经注定是0/1了，但是我怕后面的晚辈乱搞，比如晚辈取了非0/1,或者到时候比n大,就麻烦了，所以我要last+1，监督下一位；当然我如果是最后一个1了，我就break了；😁

赞！

生动形象 Orz

先生你适合去说书😂😂

看了一个小时，说下个人理解。这题利用的是前缀和思想。每位x可能是x == 0 或 x == 1 或 x > 1，当x == 0时，因为没有办法进行当前为选0还是选1，继续进行循环。当x >= 1时，第i为先都选0（通过组合数可以算出这种情况）。是否然后再看x是否大于1，大于1的情况 如果第i位也选1，也可以通过组合数求出余下的情况，这就是为什么可以直接break的原因。 如果恰好x == 1, 那只能继续往下执行循环

大佬说得妙啊，看视频和题解看了小半天都没整明白，一看大佬的解释立马悟了！

牛的

还这位佬,专研了的,一语道真相

            if(x > 1){
                //当前位填1，从剩下的所有位（共有i位）中选K-last-1个数。
                //对应于：左分支中填1的情况，合法
               if(K - last -1 >= 0) res += f[i][K -last -1];//i个数中选K-last-1个数填1的组合数是多少
               //对应于：左分支中其他情况（填大于1的数）和此时右分支的情况（右侧此时也>1），不合法！！！直接break。
                break;
            }

对楼主这段break的原因更改一下，这儿break其实是因为你这种情况下左分支中选的是1，也就是说如果你此时右分支存在的话，那么一定大于1，但题目总只有0,1，与题意矛盾，所以要break出去。而且楼主所说的“左分支中其他情况（填大于1的数）这局话也是有误的”，这题里面只有0,1，又怎么可能填比1大的数了？

看了好几遍楼主写的，一句话一句话思考过去的，总的来说感觉写的非常好，好详细，这段思考了好几遍，又看了几遍视频，才发表的上面这段评断，并不是随意发的。

建议看不懂的小伙伴去看看视频 26:30处。

又稍微加了些自己的理解。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
const int N=35;
int f[N][N]; //dp数组的含义：表示从i位中选，选k个1的方案数 其实在这题中也就是以组合数的形式体现出来的

int k,b;

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

int dp(int x)
{
    //首先处理边界问题
    if(!x)
    {
        return 0;
    }

    //将x的每一位提取出来
    vector<int> nums;
    while(x)
    {
        nums.push_back(x%b);
        x/=b;
    }
    int n=nums.size();

    int res=0; //用于记录答案
    int last=0; //用于记录之前用过多少1了

    for(int i=nums.size()-1;i>=0;i--)
    {
        int a=nums[i];
        //其实下面这段概况起来就是，只要我当前数a是大于0的，左分支一定可以取0，问题在1，因为本题的最大值只能到1，因此如果左分支
        //取了1，那么右分支就不能再去了，要么就是左分支不取1，让右分支取。

        if(a>0) //只有在a大于0的时候才存在左分支（这儿的左分支是一个大的概念，其除了最后一个点外，将整个数都看成是左分支）
        {
            res+=f[i][k-last]; //左分支当前选的是0，即当前位i选的是0，则可以从0~i-1中选取k-last个1
            if(a>1)
            {
                if(k-last-1>=0) res+=f[i][k-last-1]; //左分支当前选的1，同上
                //此时左分支选了1，而题目里面最大只能1，但是如果是你现在这种情况的话，右边已经是2了，所以直接break
                break;
            }
            else //对应于右分支取1，此时last++。（注意这儿的右分支指的是整个大的左分支中的右分支）
            {
                last++;
                if(last>k) break;
            }
        }
        if(!i&&last==k) res++;
    }

    return res;
}

int main()
{
    init();
    int l,r;
    cin>>l>>r>>k>>b;
    cout<<dp(r)-dp(l-1)<<endl;
    return 0;
}

感觉您的理解有问题的，题解里是将 x 化成 B 进制下的数，然后拆分出每一位来。既然是B进制，那么在 B > 2 的时候是存在大于 1 的情况的

我也这么觉得，break是因为x>1时，由于题目最高只能填到1，并且左分支中已经计算了填0和1的情况，右边分支的结果已经被包含在左分支里了

17的三进制数是110？？？？？？

17的三进制数不是122吗

楼主你好：
//上面处理完了这棵树的所有左分支，就剩下最后一种右分支的情况
// 也就是遍历到最后1位，在vector中就是下标为0的地方：i==0；
// 并且最后1位取0，才算作一种情况res。因为最后1位不为0的话，已经被上面的ifelse处理了。
if(i==0 && last == K) res;

我认为最后1位取0，才算作一种情况res这句话有所偏颇，比如在K=B=2下，101进行到最后一个分叉的时候最后一位取1，此时res
因此这句话应该是最后一位取0或1
因为在上面的else中last并没有对res进行操作，因此一路往右走到尽头为1的时候在这里res才++

你说得对，有0和1两种情况使得.本质都是选够1的时候，因为接下来没有数或者接下来全是0，导致不能加上这一个方案才res++

看了大半天 看不懂的可以移步b站https://www.bilibili.com/video/BV1Ff4y1e7YW/?spm_id_from=333.337.search-card.all.click&vd_source=e3011a4ba1b30a3e51568b42fb69f38d

帅

换个写法，希望帮助理解

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int k, b, l, r;
int dp[N][N];
void init() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (!j) dp[i][j] = 1;
            else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
}
int f(int n) {
    if (!n) return 0;
    vector<int> nums;
    while (n) nums.push_back(n % b), n /= b;
    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
        int x = nums[i];
        if (x == 1) {//当前位的最高数为1
            res += dp[i][k - last];//当前位为0的方案数
            if (++last > k) break;//往后开始讨论当前位为1的方案数，已有1的个数即last，要+1
            //为什么这里不能直接break？因为当前位为1的情况需要讨论，不能跟下面一样直接加上当前位为1的方案数，或许某个方案的数字会大于n
        }
        else if (x > 1) {//当前位的最高数大于1
            res += dp[i][k - last];//当前位为0的方案数
            if (k - last - 1 >= 0) res += dp[i][k - last - 1];//当前位为1的方案数
            break;
            //为什么可以直接break？因为当前位的最大数字大于1，那么只需要考虑当前位为0和1时的方案数，因为这已经包含所有可能情况
        }
        if (!i && last == k) ++res;
    }
    return res;
}
int main() {
    init();
    cin >> l >> r >> k >> b;
    cout << f(r) - f(l - 1);
    return 0;
}

题解中的解释有处小错误，希望题主早日修改。

// 并且最后1位取0，才算作一种情况res++。因为最后1位不为0的话，已经被上面的ifelse处理了。
        if(i==0 && last == K) res++; 

这里的解释是错的，应该是最后一位为1或0。可以按照你的意思，把代码改成

if(i==0 && last == K&& nums[i]==0) res++; 

然年，输入数据：

19 19
3
2

正确的答案是1，而按你的理解写出的代码会是0。至于为什么是0和1都行，稍微思考一下应该就理解了

终于懂了，您配享太庙😭orz

为啥x大于1,就直接break了，右边数的大小取值不应该是0-b-1吗，大大的疑惑

我来试着说一下我所理解的 x ＞ 1 时break原因吧。主要是考虑任意情况所取值必须小于上界。 从高位到低位如果某个位置大于1 后面可随意位置填1 再也不用担心后面某个位置填1会越界。举个例子2103201 因为最高位大于1 可以直接break 后面值任意取。但是为0和1时却不能break 因为后面还是被限制 任意取有可能越过上界

本题要求：从n位中选取k位，且选取的位上为1，不选的为0。
当x==0时，这一位只有0，没有左分支，故直接遍历下一位。
当x==1时，这一位有两种情况，0和1，小于x的0做左分支，从0到i-1这i位中挑选剩下所需的k-last位
当 x>1 时，0和1都小于x，所以左分支既可以取0，又可以取1 当取0时如上面x==1的情况，取1时从剩下的i位中选k-last-1位，这个减的1即为本位，因为右分支不为1，所以已经取完。

没看懂，再比如 B=3，K=2，这个数是17.就是把17化为三进制，17化为三进制为110 ，其中也有2个1，其余都是0.
，但是17(十进制) = 122(三进制)

再比如 B=3，K=2，这个数是12.就是把12化为三进制，12化为三进制为110 ，其中也有2个1，其余都是0.

欢迎指正。与其说 “后面的xxx条件不合法”， 我觉得把他们想象成一种 “剪枝” 也是一种思路。两个break都是因为 我已经统计完了所有的可能。那就没有必要再浪费时间了。 (1) 对于last>K： 就算后面还有几位，我知道一定都是0组成的. （2） 为什么res+=f[i][K -last -1]之后直接break就行了：ith位置只能取0或1， 但限定值大于1， 那我此时一口气就能找到剩余的所有可能(ith后面的选择也不要分左右子树了，直接无脑做一个从i个球中摸k-last-1个。 X的第ith位在这顶着，我们能保证最终选出来的所有数值都是小于X的)。 此时求完所有结果，直接走人

终于看懂了，总的来说就是只有当左分支取不到1的时候才会往右分支继续计算，左分支能取到1时已经将所有方案数得到了，右分支可以直接跳了。

那么右分支为什么还加呢

因为分支到最下面可能还会有一个解

终于懂了，太感谢了

Orz

注释真的很详细，66

大佬，想问一下对于不合法的情况为什么不直接break掉，而是要先res += f[i][K -last -1];，再break掉呢？

res += f[i][K -last -1];计算的部分还是合法的，先把这部分加上。除此之外，其他情况都不合法了 就 可以break了