2^k进制数转换问题 - NOIP 2006 提高组 第四题

设\u000Ar是一个2\u000A2位k进制数，并满足以下条件：\u000A\u000Ar至少是个2\u000A2位的2\u000A2k进制数。\u000A作为2\u000A2k进制数，除最后一位外，\u000Ar的每一位严格小于它右边相邻的那一位。\u000A将\u000Ar转换为二进制数\u000Aq后，则\u000Aq的总位数不超过\u000Aw。\u000A在这里，正整数\u000A，\u000Ak,w是事先给定的。\u000A问：满足上述条件的不同的\u000Ar共有多少个？\u000A我们再从另一角度作些解释：设\u000AS是长度为\u000Aw的01\u000A01字符串（即字符串\u000AS由\u000Aw个0\u000A0或1\u000A1组成），\u000AS对应于上述条件三中的\u000Aq。将\u000AS从右起划分为若干个长度为\u000Ak的段，每段对应一位2\u000A2k进制的数，如果\u000AS至少可分成2\u000A2段，则\u000AS所对应的二进制数又可以转换为上述的2\u000A2k进制数\u000Ar。\u000A例：设\u000A=3，\u000Ak=3,w=7。则\u000Ar是个八进制数（2\u000A3=8\u000A23=8）。由于\u000A=7\u000Aw=7，长度为7\u000A7的01\u000A01字符串按3\u000A3位一段分，可分为3\u000A3段（即1,3,3，左边第一段只有一个二进制位），则满足条件的八进制数有：\u000A2\u000A2位数：\u000A高位为1\u000A1：6\u000A6个（即12,13,14,15,16,17\u000A12,13,14,15,16,17），\u000A高位为2\u000A2：5\u000A5个，\u000A…，\u000A高位为6\u000A6：1\u000A1个（即67\u000A67）。\u000A共6\u000A+5\u000A+…+1=21\u000A6+5+…+1=21个。\u000A3\u000A3位数：\u000A高位只能是1\u000A1，\u000A第2\u000A2位为2\u000A2：5\u000A5个（即123,124,125,126,127\u000A123,124,125,126,127），\u000A第2\u000A2位为3\u000A3：4\u000A4个，\u000A…，\u000A第2\u000A2位为6\u000A6：1\u000A1个（即167\u000A167）。\u000A共5\u000A+4\u000A+…+1=15\u000A5+4+…+1=15个。\u000A所以，满足要求的\u000Ar共有36\u000A36个。\u000A输入格式\u000A一行两个正整数\u000A，\u000Ak,w用一个空格隔开：\u000A\u000A输出格式\u000A一行一个个正整数，为所求的计算结果。\u000A即满足条件的不同的\u000Ar的个数（用十进制数表示），要求不得有前导零，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。\u000A\u000A（提示：作为结果的正整数可能很大，但不会超过200\u000A200位）\u000A\u000A输入输出样例\u000A输入 #1复制\u000A3 7\u000A输出 #1复制\u000A36\u000A说明/提示\u000A【数据范围】\u000A1\u000A≤\u000A≤9\u000A1≤k≤9\u000A1\u000A≤\u000Aw≤3×10\u000A4\u000A\u000A\u000ANOIP 2006 提高组 第四题\u000A用C++解答内容：首先，我们可以观察到，满足条件的r的位数至少为2，最多为w/k+1。\u000A\u000A接下来，我们可以考虑如何生成满足条件的r。\u000A\u000A我们可以从高位开始生成r的每一位。设当前要生成的位是第i位，那么我们需要知道第i+1位的值。\u000A\u000A我们可以将r的第i+1位的值从0到k-1枚举一遍，然后判断是否满足条件即可。\u000A\u000A具体来说，我们可以用递归的方式生成r的每一位。\u000A\u000A设当前要生成的是第i位，当前已经生成的r的值为cur。我们可以枚举第i+1位的值，从0到k-1，然后判断是否满足条件。\u000A\u000A满足条件的话，我们可以继续递归生成下一位。\u000A\u000A递归的终止条件是当生成的位数已经达到了w/k+1。\u000A\u000A最后，我们可以统计满足条件的r的个数即可。\u000A\u000A下面是具体的实现代码：\u000A\u000A#include\u000Ausing namespace std;\u000A\u000Aint k, w; \u000Aint cnt = 0; \u000A\u000Avoid dfs(int i, int cur) { \u000A if (i == w / k + 1) { // 生成位数已经达到w/k+1 \u000A cnt++; \u000A return; \u000A } \u000A for (int j = 0; j < k; j++) { \u000A if (cur % k > j) { // 每一位严格小于它右边相邻的那一位 \u000A dfs(i + 1, cur * k + j); \u000A } \u000A } \u000A} \u000A\u000Aint main() { \u000A cin >> k >> w; \u000A dfs(1, 0); // 从第一位开始生成r \u000A cout << cnt << endl; \u000A return 0; \u000A}