K-进制数 题解C++ 递推式推导即可

解题思路:

我们可以用a[i]来表示位数i的K进制数的有效数的个数 。记最高位是第i位，最低位是第1位

那么很显然第i位的数不可能为0，只能是1到K-1，一共有K-1种

我们只要找到除第i位数之外的所有位数的K进制数的有效数的个数，再乘以K-1，显然就是我们要求的a[i]

现在我们看第i-1位数，对于它，可能是0，可能不是0，因此有两种情况，当第i-1位数是0时，可以表示的数的个数为a[i-2],即第i-2位不为0的总个数

                                                                                                              当第i-1位数不是0时，可以表示的数的个数为a[i-1]

因此我们可以得到a[i]=(a[i-1]+a[i-2])*(K-1)这样的递推式 (i>2)

再初始化一下：a[1]=K-1  ,a[2]=K*(K-1)即可

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int N,K;

int a[30];

int main(){

scanf("%d%d",&N,&K);

a[1]=K-1;

a[2]=K*(K-1);

if(N<3) cout<<a[N];

else {

for(int i=3;i<=N;i++) a[i]=(a[i-1]+a[i-2])*(K-1);

cout<<a[N];

}

return 0;

}