题目描述
设r是个2^k 进制数，并满足以下条件：
（1）r至少是个2位的2^k 进制数。
（2）作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k〈w≤30000）是事先给定的。
问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。
例：设k=3，w=7。则r是个八进制数（2^3=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。
所以，满足要求的r共有36个。
输入格式
只有1行，为两个正整数，用一个空格隔开：
k w
输出格式
1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
（提示：作为结果的正整数可能很大，但不会超过200位）
样例输入
3 7
样例输出
36
解题思路（这一题脑袋转不过来，分析了好久，现在分享一下思路）
例k=3，w=7
则2^k=8,8进制数，在八进制数中列出 转换为2进制后的位数 小于7位数的数
例如8进制的12，转换为2进制后为1010
满足条件
1.r至少是个2位的2^k 进制数,12是2位的8进制数
2.12的每一位严格小于它右边相邻的那一位
3.转换为2进制后1010的位数4<7
对于8进制而言，2进制每3位数表示1个8进制数
得出结论：
● 要小于7位2进制数的话，8进制数的位数只能是2位和3位，把这一思路推广一下
● 除了首位以外，其他位的取值范围是000~111（(2^k)-1），即每一位可以取0~7
●首位为0的情况下，可取w/k位，并且w/k>=2
●所以首位为0的合法解有
∑ C(2^k-1,i)(2<=i<=w/k)
即对于k=3，w=7的情况下，可取C（7，2），就是在1~7中选两个数都是合法的，那么有21种可能。为什么这21种解刚好符合题目例子（再看一遍题目，题目有例子喔）中2位数的合法解（21）呢？（只有严格递增的排列才是合法的）
●这里用的是C进行组合，从7个中选择2个，不可能有重复的两位数，并且排列并没有像A（排列）一样，（1，2）：第一位是1，第二位是2（2，1）都取，这里我们默认只取（1，2）,即严格递增的排列
●为什么没有（3，4）呢，因为(2<=i<=w/k)有限制
以上讨论了二进制首位为0的情况，接下来讨论二进制首位为1的情况
●如果首位非0，那么8进制数就是三位数
●除了首位外，还有w/k位，要符合严格递增的要求，首位的取值范围只能是1~2^（w%k）-1,例如
余下1位，那么只有0，1这两种可能，减去0这种可能就只有1种可能了
●设首位取值为val
●则剩下w/k位取值范围为val+1~(2^k)-1
●也就是有（2^k）-1-(val+1)+1个数，即2^k-1-val,按照首位为0来讨论，其合法解有
∑ C(2^k-1-val,w/k)(1<=val<=2^(w % k)-1)
用代码得出8进制数的最高位数 2<=n<=8进制数的最高位数
int Level(int k,int w) { int n=0; while(w>0) { w-=k; n++; } return n; }
重要注 (反复思考一下)
对于高精运算的处理，在网上学习到了一个比较巧妙的方法避开了复杂的数组运算，也可以有效避免溢出，就是把上面那些组合数的运算都转换成了 C(2^k-1,i) —（+1-i）—- > C(2^k-i,i),即写C组合函数的时候不是计算C(2^k-1,i)，而是计算C(2^k-i+i-1,i)，即我们把（2^k-i,i）代入函数得到的是（2^k-1,i）的结果，那么C(2^k-1,i) <—（-1+i）—- C(2^k-i,i),就需要将C（n,m)的计算，变为C（n+m-1,m）
long sump(int n, int m) //公式为C(n+m-1)(m) { int i; long sum = 1; for(i = 0 ; i < m ; i++) sum *= (n+m-1-i); for(i = 1 ; i <= m ; i++) sum /= i; return sum; }
sump（2^k-i,i)----->n=2^k-i,m=i------->C(2^k-1,i)
sump(sump( 2^k- w/k - i , w/k)----->n=2^k-w/k-i m=w/k------>C(2^k-i-1,w/k)
反过来如果我们要计算C(2^k-i-1,w/k)，公式位C（n+m-1）(m),也可以得到n=2^k-w/k-i
最终代码为
#include<stdio.h> #include<math.h> long sump(int n, int m) //公式为C(n+m-1)(m) { int i; long sum = 1; for(i = 0 ; i < m ; i++) sum *= (n+m-1-i); for(i = 1 ; i <= m ; i++) sum /= i; return sum; } int Level(int k,int w)//计算最高有几位数 { int n=0; while(w>0) { w-=k; n++; } return n; } int main() { int k ,w ,i ; scanf("%d%d",&k,&w); int level = Level(k,w); int max = pow( 2.0 , k);//这里的max是去不到的，例如k=3,2^3=8,8进制每一位最高111,就是7 int gao = pow( 2.0, w%k)-1;//最高位的数的最大值，即val,可以取0,就是w/k能整除的情况 //开始计算，分两种情况，第一种，首位为0，那么后面x位数对应的个数符合c[max-1][x] long long sum = 0; //去掉最高位 level-1;且至少两位i=2开始 for(i = 2 ; i <= level - 1;i++) sum += sump( max - i,i); //第二种情况，首位不是0，如果首位为n,解就有C[max-1-n][w/k] for( i = 1 ; i <= gao ; i++) sum += sump( max - w/k - i , w/k); printf("%d\n",sum); return 0; }
如果上面计算有点糊涂，可以直接根据公式来：
#include<stdio.h> #include<math.h> long sump(int n, int m) //公式为C(n)(m) { int i; long sum = 1; for(i = 0 ; i < m ; i++) sum *= (n-i); for(i = 1 ; i <= m ; i++) sum /= i; return sum; } int Level(int k,int w)//计算最高有几位数 { int n=0; while(w>0) { w-=k; n++; } return n; } int main() { int k ,w ,i ; scanf("%d%d",&k,&w); int level = Level(k,w); int max = pow( 2.0 , k);//这里的max是去不到的，例如k=3,2^3=8,8进制每一位最高111,就是7 int gao = pow( 2.0, w%k)-1;//最高位的数的最大值，即val,可以取0,就是w/k能整除的情况 //开始计算，分两种情况，第一种，首位为0，那么后面x位数对应的个数符合c[max-1][x] long long sum = 0; for(i=2;i<=w/k;i++) sum+=sump(max-1,i); //第二种情况，首位不是0，如果首位为n,解就有C[max-1-n][w/k] for( i = 1 ; i <= gao ; i++) sum += sump(max-1-i, w/k); printf("%d\n",sum); return 0; }
这一题主要是理解题意+分析，代码编写方面难度不大
既然提到了进制，顺便复习一下进制转换
编写一个程序，不使用格式控制符 %x 的情况下，将十进制数转换为十六进制
代码如下
#include <stdio.h> #include <stdbool.h> int main(void) { int decimal; bool negative = false; printf("输入一个十进制数: "); scanf("%d", &decimal); // 判断并记录要转换的十进制数的正负号 if(decimal < 0) { negative = true; decimal *= -1; } // 将该十进制数对16进行短除法，并将余数依次存入数组num中 int i; char hex[10]; for(i=0; i<10 && decimal!=0; i++) { switch(decimal % 16) { case 0 ... 9: hex[i] = decimal%16 + '0'; break; case 10 ... 15: hex[i] = decimal%16 - 10 + 'A'; break; } decimal /= 16; } printf("转换成十六进制为: %c0x", negative?'-':' '); // 将数组num中的数字倒序输出 int j; for(j=i-1; j>=0; j--) { printf("%c", hex[j]); } printf("\n"); return 0; }
结果展示
