HDU 2062 Subset sequence (数学)

灰太狼 2022-06-03 01:29 134阅读 0赞

一道数学题，很有趣，看了很多题解才懂。

首先是要求出An数组的子集和有多少个。

数学拙鸡就不写推导过程了，有兴趣可以自己去搜。

A\[n\]=(A\[n-1\])\*(n-1)+1;

引用一段解释的很好的过程解释来说下3 10 这组数据是怎么处理的（语文拙计）

因为n=3，所以开始数组里1、2、3三个数。  
我们知道，n=2时，有4种排列，所以上面n=3可以分成三组，每组5个(加上空集)。  
因此第10个在第二组里。所以第一个是2，把2输出。原来的数组里删除2，变成1、3两个数。然后10 - (2 - 1) \* 5 = 5，即它在第2组的第5个。  
减去首个空集合，5 - 1 = 4 ≠ 0，表示2后面还有数字。  
因为A1 = 1是，所以再第2组里又可以分成两组，每组2个(加上空集)。  
所以，4在第2组，剩下的数组中，第二个元素是3，所以输出3。再把数组里的3删除，剩下1一个数。  
然后4 - (2 - 1) \* 2 = 2，既它是第2组的第2个。  
减去首个空集，2 - 1 = 1 ≠ 0，表示2后面还有数字。  
按上面的方法继续下去，直到n = 0 或 后面为空集为止。  
最后输出数组里的第1个元素，就得到2 3 1，就是解了。

#include <stdio.h>
    #include <algorithm>
    #include <math.h>
    #include <string.h>
    using namespace std; 
    int main(int argc, char *argv[])
    {
    	int t;
    	int i,j;
    	int n,s[30];;
    	long long int m,c[25]={0};
    	for(i=0;i<21;i++)
    	{
    		c[i]=c[i-1]*(i-1)+1;
    		//printf("%lld\n",c[i]);
    	}//求出每个数字分组里的个数 
    	while(scanf("%d %lld",&n,&m)!=EOF)
    	{
    		for(i=0;i<26;i++)
    			s[i]=i;//初始赋值 
    		while(n>0&&m>0) 
    		{
    			t=m/c[n]+1;//判断第m个数在那一组 
    			//printf("*****m=%lld cn=%lld t=%d\n",m,c[n],t);
    			if(m%c[n]==0)
    				t--;
    			if(t>0)
    			{
    				printf("%d",s[t]);//先输出t组的首数字 
    			//	printf("*******%d\n",t);
    				for(i=t;i<=n;i++)
    				{
    					s[i]=s[i+1];//在第n组中，第2个元素在第n个时变为它的下一个数 
    				}		
    				m=m-((t-1)*c[n]+1);//m变为表示在剩余子集中位于第几个 
    			//	printf("*******%d\n",m);						
    				if(m==0)
    					printf("\n");		
    				else
    					printf(" ");	
    			}
    			n--;
    		}
    	}
    	return 0;
    }

//Start-ZJ

//2017/12/14/10:01