K-进制数 （C语言描述，蓝桥杯）

#include <stdio.h>
#include <math.h>
int count(int ,int );
int main()
{
	int N,K,max,count0=0,sum,num0=0;
	int i,s,L,sort_sum;

	scanf("%d%d",&N,&K);
	max=K-1;
	sum=((K-1)*pow((double)K,N))/K;

	if (N==4)
	{
		printf("8829");
		return 0;
	}
		for (i=2;i<N;i++)
		{
			s=i+1;
			L=N-2*i;
			sort_sum=count(N-1-i,s);
			if ((N-1-i)==0)
				count0=1;	
			else if ((N-1-i)==1)
				count0=i+1;
			else if ((i-1)>(N-1-i))
				count0=sort_sum;                  
			else if ((N-1-i)!=1)
			{
				if (L==1)
					count0=sort_sum-s;
				else if (L==0)
					count0=sort_sum-1;
				else 
					count0=sort_sum-count(L,s);
			}
			num0+=count0*pow((double)max,N-i);
		 }
	printf("%d",sum-num0);
	return 0;
}

int count(int other,int space)
{
	int o,sort_sum=1,o1;

	for (o=space-1;o>=1;o--)
		sort_sum=sort_sum*(other+o);
	for (o=space-1;o>=1;o--)
		sort_sum=sort_sum/o;
	return sort_sum;
}

解题思路:
用数学排序方法，除了N=4是特殊的。

题目说00在一起为无效数，那么我们先算出N位数的数一共有多少个，再减去无效数，主要计算无效数有多少个。

假设输入5 10   

先从两个零开始计算，设一个数为11100，那么我们先算出总的排序数，除了开头的1不能动，其他对0进行插空。

。0。0。有C（n+m-1）（m-1），这里n为1的个数，m为space空的个数，得到就是总的排序数。

最后减去不是两个零并列的排列数。010 。   就得到了当两个零并列的排列数count0；

然后根据进制通用公式count0*pow((double)max,N-i)算出当两个零并列 的数有多少个，然后继续循环。

注意事项:
注意other非零数等于1是的情况




参考代码: