Newguy


私信TA

用户名:772007765

访问量:88627

签 名:

已秃人士

等  级
排  名 29
经  验 15333
参赛次数 3
文章发表 92
年  龄 0
在职情况 在职
学  校
专  业

  自我简介:

#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是的情况




参考代码:

 

0.0分

0 人评分

  评论区

运行题例2 10的时候是89 = =
2018-03-18 14:48:46
好难
2017-11-28 15:33:45
大佬带带我
2017-10-20 18:19:22
前排围观大神
2017-10-15 20:18:00
  • «
  • 1
  • »