K-进制数 （C++代码）[排列组合解法]

解题思路:
分析题目后可知:

这个是一个无序插空的问题.

于是分组,将0和其他进制数分为两组,之后对于每个非零位的数字均有K - 1个,对于数字0.

此处假设,是一个N位的一个数字,并且,根据数字分布情况可知,该序列内的0一定不会超过N / 2(向零取整)个.

根据无序插空法可知,该序列中去除第一个必不为0的数后有N - 1个数,其空位(包含头部尾部)有N个,再取其中0有i个.

综上,此时序列内有非零数共N - i个,其每个可以取得的数字根据排列组合则有(K - 1)^{(N - i)}个再根据无序插空公式有Cⁱ_{(N - i)}种0的插入方法故得出以下代码:

注意事项:
直接通过循环来插入0,无0的情况直接可以通过(K - 1)^N得出

参考代码:

#include <iostream>
#include <cmath>
int C(int up,int down){
    int T = down - up;
    int sum = 1;
    for(int i = 0;i<T;++i)
        sum *= down--;
    int T1 = 1;
    for(;T>0;--T)
        T1 *= T;
    return sum / T1;
}
int main(){
    int K,N;
    std::cin>>N>>K;
    int sum = pow(K - 1,N);
    for(int i = 1;i<= N / 2;++i)
        sum += pow(K - 1,N - i) * C(i,N - i);
    std::cout<<sum;
    return 0;
}