2^k进制数 （C++代码）-排列组合+高精度巧妙处理

解题思路:
这个题用了一天的时间，看各种大神写的，然后最后找到了一个比较简单且易懂的方式分享给大家，这个题我也不会做，不过学到了点新知识。

思路： 这是一个组合数学问题，

注意这句话：作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。

其实这是在暗示组合数，

显然r中的不会有相同的位

      如果每一位都不同，显然只有严格递增的排列是合法的

这便是组合，

将 r 转化成这种形式（设k为3） 000 000 000 000

      显然除首位外每一位的取值范围为 000 to 111(2^k-1)

      在首位为0的情况下，最多可取 w/k 位，且题目要求大于2位，

      则在首位为0的合法解有 ∑ C(2^k-1,i)(2<=i<=w/k) ，

Ps. 如果 w 模 k 等于 0 仅考虑上述情况即可。

考虑首位不为0的情况

      显然首位不为0的话，r 就有 w/k+1 位，

      除首位外还有w/k位，

      可以枚举首位的取值范围为 1 to 2^(w mod k)-1

      设首位取值为 val

      则剩下 w/k 位 取值范围为 val+1 to 2^k-1

      也就是有 2^k-1-val 个数可取

      所以首位不为0的合法解有 ∑ C(2^k-1-val,w/k)(1<=val<=2^(w mod k)-1)

所以上述两者相加便是正解（需要高精运算）

对于高精运算的处理，我看到了一个比较巧妙的方法避开了复杂的数组运算，就是把上面那些组合数的运算

都转换成了    C(2^k-1,i) ----->  C(2^k-i,i)    然后写C函数的时候不是计算C(2^k-1,i)，而是计算C(2^k-i+i-1,i)。  巧妙之处就在这里，这样可以有效的避免有溢出吧。 


注意事项:
1、本题的关键就是看懂题目，知道这是个排列组合问题。

2、在排列组合的计算时，用了一个巧妙的方法，希望能看懂。


参考代码:

#include <iostream>

#include <cmath>

using namespace std;

long C(int n,int m)                 //公式为C(n+m-1)(m)[重点]   希望结合上面说的看懂

{

    int i;

    long sum=1;

    for (i=1;i<=m;i++)

        sum*=(n+m-i);

    for (i=1;i<=m;i++)

        sum=sum/i;

    return sum;

}

int main()

{

    int k, w;

    cin >> k >> w;

    int part_num = w / k + 1;             //一共分为几段

    int maxx_num_per_part = pow(2.0,k);             //取不到，每部分最大取到maxx_num_per_part减去1，就是每一位都是1的时候

    int gaow_num_max = pow(2.0,w%k) - 1;         //最高位的数最大值,可以是0

    //开始计算，分两种情况，第一种，首段为0，那么后面n位数对应的个数符合C[maxx_num_per_part-1][n]

    long long sum = 0;

    for (int i=2; i<=part_num-1; i++)           //去掉最高位部分，还有至少两位数

    {

        sum += C(maxx_num_per_part-i, i);

    }

    //第二种情况，首段不是0，如果首段为x，解就有C[maxx_num_per_part-1-x][w/k]

    for (int i=1; i<=gaow_num_max; i++)

    {

        sum += C(maxx_num_per_part-w/k-i,w/k);

    }

    cout << sum;

    return 0;

}