K-进制数：简单的排列组合思想

解题思路:本题目中要求n位的k进制数，0不能在首位，不能在0的后面，因此每个0只能位于非0数字的后面，因此假设有i个0，则这i个0需要在（n-i)个非0数字的后面选择位置，一共有c(n-i,i)中情况，同时，这n-i个非0数字可能有的排列情况为（k-1）^n-i种（每一个都可能是k-1个数字中的任意一个，k进制为每一位都是从0到k-1中的一个数字），因此，在i确定的情况下，总体的情况一共有c(n-i,i)*(k-1)**(n-i)种，最后同时还需考虑i为每一种大小的情况，然后将这些情况数累加起来就是最终结果

注意事项:i最大为n//2（向下取整），一方面因为i不能大于（n-i），另一方面因为算组合数c(n-i,i)时，i超过n的一半时组合数的情况就重复了

参考代码:

n=int(input())
k=int(input())
def xuanze(a,b):
   c=1
   for i in range(b):
       c*=(a-i)
   for j in range(1,b+1):
       c/=j
   return c
count=0
for i in range(n//2+1):
   count+=xuanze(n-i,i)*(k-1)**(n-i)
print(int(count))