作为 2k2k2k 进制数,除最后一位外, rrr 的每一位严格小于它右边相邻的那一位。
通过分析理解,题目的意思可表达为:将长度为 www 的二进制串 kkk 位一节划分为 www / kkk 份( www / kkk 要取上整,如 777 / 3=23=23=2 . 333 ,应为 333 份),则对应的 2k2k2k 进制数最多是 intintint [ www / kkk ] +1+1+1 位数,这个位数用 lenlenlen 表示,加上题目规定:最少为 222 位数,从左到右每一个数都升序的条件,这样的 2k2k2k 进制数共多少个呢?
它等于两类组合数之和:
第一类:位数为 222 — len−1len-1len−1 的 2k2k2k 进制数种数; 它等于从 2k2k2k −1-1−1 个数中分别不重复地取 222 个、 333 个、……. len−1len-1len−1 个数的不同组合数之和,即 ccc ( 2k−12k-12k−1 , 222 ) +++ ccc ( 2k−12k-12k−1 , 333 ) +++ …… +++ ccc ( 2k2k2k −1-1−1 , len−1len-1len−1 ),或∑ ccc ( 2k2k2k −1-1−1 , iii ),( 2<2<2< =i<=len−1=i<=len-1=i<=len−1
);
第二类:位数已经达到 lenlenlen 的 2k2k2k 进制数种数; 这类数的首位可能够是 111 , 222 ,…… 2k−i−12k-i-12k−i−1 ,从第 222 位开始取数时 每次都要扣除小于左边相邻数的这些数,因此可供选择的数越来越少,累加起来是∑c(2k–(i+1),len)∑c(2k –(i+1),len)∑c(2k–(i+1),len),(1<=i<=2k)(1<=i<=2k )(1<=i<=2k)。