dicorder.cpp

n个元素{1,2,…,n}有n!个不同的排列。将这n!个排列按字典序排列

			mul nXX;
			mov ebx, xx[eax];						
			mov esi, [ebx]xx.pValue;
			mov ecx, [ebx]xx.last

			mov edx, this;
			mov edi, [edx]this.pValue;
			mov eax, [edx]this.last;
			sub eax, ecx;
			shl eax, 2;
			add edi, eax;
			push eax;	//保存eax

			xor ebx, ebx;	//作为变址寄存器
			clc;
sub_loop:
			mov eax, [esi][ebx*4];
			sbb [edi][ebx*4], eax;
			inc ebx;
			loop sub_loop;

			//调整last
			mov edi, [edx]this.pValue;
			mov eax, [edx]this.last;
			mov ecx, eax;
			dec eax;
			shl eax, 2;
			add edi, eax;

			xor eax, eax;
			repe scasd;
			inc ecx;
			mov [edx]this.last, ecx;

			//将商的相应位置1
			mov esi, r.pValue;
			pop eax;
			mov ecx, nXX;
			bts dword ptr [esi][eax], ecx;		
		}
	}	

	for (i=0; i<32; i++)
	{
		if (xx[i] != NULL)
		{
			delete xx[i];
		}
	}
	CBigInt ret(*this);
	*this = r;
	return ret;
}


DWORD CBigInt::operator /= (DWORD dwValue) //返回余数
{
	if (dwValue == 0)
	{
		CMyException* exception = new CMyException("除数为0", 
My_ErrorNo_ZeroByDiv);
		throw exception;		
	}
	__asm
	{
		mov ebx, this;
		mov esi, [ebx]this.pValue;
		mov ecx, [ebx]this.last;
		mov edx, 0;
		mov ebx, dwValue;
		jmp L2;
L1:				
		mov eax, [esi][ecx*4];
		div ebx;
		mov [esi][ecx*4], eax;
L2:
		loop L1;
		mov eax, [esi]
			div ebx;
		mov [esi], eax;
		
		mov ebx, this;
		mov eax, [ebx]this.last;
		dec eax;
		jz   L3;
		mov esi, [ebx]this.pValue;
		cmp [esi][4*eax], 0;
		jne  L3;
		dec [ebx]this.last;
L3:
		mov eax, edx;
	}
}

bool CBigInt::operator == (const CBigInt& x)
{
	__asm
	{
		mov al, 1;		//return true;
		mov ebx, this;
		mov ecx, [ebx]this.last;
		mov edx, x;
		cmp ecx, [edx]x.last;
		jne  L1;		
		mov esi, [ebx]this.pValue;
		mov edi, [edx]x.pValue;
		cld;
		repe cmpsd;
		jz L2;
L1:
		mov al, 0;
L2:
	}
}

bool CBigInt::operator == (DWORD dwValue)
{
	return last == 1 && pValue[0] == dwValue;
}

bool CBigInt::operator != (const CBigInt& x)
{
	return !operator == (x);
}

bool CBigInt::operator != (DWORD dwValue) 
{
	return last > 1 || pValue[0] != dwValue;
}

bool CBigInt::operator > (const CBigInt& x)
{
	__asm
	{		
		pushf;
		mov al, 1;		//return true;
		mov ebx, this;
		mov ecx, [ebx]this.last;
		mov edx, x;
		cmp ecx, [edx]x.last;
		ja  L2;
		jb  L1;
		mov esi, [ebx]this.pValue;
		mov edi, [edx]x.pValue;
		mov edx, ecx;
		dec edx;
		shl edx, 2;
		add esi, edx;
		add edi, edx;
		std;
		repe cmpsd;
		ja L2;
L1:
		mov al, 0;
L2:
		popf;
	}
}

bool CBigInt::operator > (DWORD dwValue)
{
	return last > 1 || pValue[0] > dwValue;
}

bool CBigInt::operator >= (const CBigInt& x) 
{
	return operator == (x) || operator > (x);
}

bool CBigInt::operator >= (DWORD dwValue)
{
	return last > 1 || (last == 1 && pValue[0] >= dwValue);
}

bool CBigInt::operator < (const CBigInt& x) 
{	
	return !operator >= (x);
}

bool CBigInt::operator < (DWORD dwValue)
{
	return last == 1 && pValue[0] < dwValue;
}

bool CBigInt::operator <= (CBigInt& x) 
{
	return !operator > (x);
}

bool CBigInt::operator <= (DWORD dwValue)
{
	return last == 1 && pValue[0] <= dwValue;
}

CBigInt& CBigInt::operator -= (DWORD dwValue)	
{
	if (operator >= (dwValue))
	{
		__asm
		{		
			mov ebx, this;
			mov edi, [ebx]this.pValue;
			mov ecx, [ebx]this.last;		
			
			mov eax, dwValue;
			sub [edi], eax;
			jnc to_return;						

			sub dword ptr[edi+4], 1;
			jnz to_return;
			dec [ebx]this.last;
to_return:		
		}
	}
	else
	{
		*pValue = dwValue-*pValue;
		last = 1;
	}
	return *this;
}

CBigInt& CBigInt::operator -= (CBigInt& x)
{
	if (*this >= x)
	{
		__asm
		{
			mov ebx, this;
			mov edx, x;
			mov edi, [ebx]this.pValue;
			mov esi, [edx]x.pValue;
			mov ecx, [edx]x.last;	
			xor edx, edx;
			clc;
L1:	
			mov eax, [esi][edx*4];
			sbb [edi][edx*4], eax;
			inc edx;
			loop L1;		
			jnc L3;
			
			mov ecx, [ebx]this.last;
			mov ebx, x;		
			sub ecx, [ebx]x.last;			
			xor eax, eax;		
			stc;
L2:
			sbb [edi][edx*4], eax;
			jnc L3;
			inc edx;	
			loop L2;		
L3:
			//调整last
			mov ebx, this;
			mov edi, [ebx]this.pValue;
			mov eax, [ebx]this.last;
			mov ecx, eax;
			dec eax;
			shl eax, 2;
			add edi, eax;		
			xor eax, eax;
			std;
			repe scasd;
			cld;
			inc ecx;
			mov [ebx]this.last, ecx;
		}
	}
	else
	{
		CBigInt temp(x);
		temp -= *this;
		*this = temp;
	}
	return *this;	
}

CBigInt CBigInt::operator - (CBigInt& x)
{
	CBigInt temp(*this);
	return temp -= x;
}
CBigInt CBigInt::operator - (DWORD dwValue)
{
	CBigInt temp(*this);
	return temp -= dwValue;
}
CBigInt&  CBigInt::operator --()			//--a
{
	return operator -= (1);
}
CBigInt  CBigInt::operator --(int)		//a--
{
	CBigInt temp(*this);
	operator -= (1);
	return temp;
}

CBigInt& CBigInt::operator = (char* pszVal)
{
	*pValue = 0;
	last = 1;
	
	if (pszVal[0] == '0' && (pszVal[1] == 'x' || pszVal[1] == 'X'))
	{
		//十六进制		
		int n = strlen(pszVal)-2;
		n = n / 8 + (n%8 == 0 ? 0 : 1);
		Expand(LeastOver(n));
		BYTE* pVal = (BYTE*)pValue;
		char ch;
		bool bLow = true;
		for (n=strlen(pszVal)-1; n>=2; n--)
		{	
			ch = pszVal[n];
			if (ch <= '9' && ch >= '0')
			{
				ch -= '0';
			}
			else if (ch >= 'a' && ch <='f')
			{
				ch -= 'a' - 10;
			}
			else if (ch >= 'A' && ch <='F')
			{
				ch -= 'A' - 10;
			}
			else if (ch == ' ')
			{
				continue;
			}
			else
			{
				*pValue = 0;
				last = 1;
				return *this;				
			}			
			if (bLow)
			{
				bLow = false;
				*pVal = ch;
			}
			else
			{
				bLow = true;
				*pVal++ |= ch << 4;
			}
		}
		if (!bLow)
		{
			pVal++;
		}
		n = ((int)pVal-(int)pValue);
		last = n/4;
		if (n%4 != 0)
		{
			last++;
			for (int i=0; i<4-n%4; i++)
			{
				*pVal++ = 0;
			}
		}
		if (last == 0)
		{
			last = 1;
		}
	}
	else
	{
		//十进制
		int n = strlen(pszVal);
		UINT ch;
		for (int i=0; i<n; i++)
		{
			 ch = pszVal[i];
			if (ch <='9' && ch >= '0')
			{	
				operator *= (10);
				operator += (pszVal[i] - '0');
			}
			else if (ch = ' ')
			{
				continue;
			}
			else
			{
				*pValue = 0;
				last = 1;
				break;
			}
		}
	}
	return *this;
}

void CBigInt::ToDecStr(std::string &s)
{
	DWORD n = DWORD(last * 32 * log(2) / log(1000000000)+1)*9;
	s.resize(n,0);
	char* pDec = (char*)s.begin();	
	char* p = pDec;
	CBigInt a(*this);
	DWORD remainder;
	do
	{
		remainder = (a/=1000000000);
		__asm
		{
			mov eax, remainder;
			mov ebx, 10;
			mov edi, p;
			mov ecx, 9;
L1:
			cmp eax, 0;
			je L2;
			xor edx, edx;	
			div ebx;
			add dl, '0';
			mov [edi], dl;
			inc edi;
			loop L1;
			jmp L3;
L2:
			mov [edi], '0';
			inc edi;
			loop L2;			
L3:
			mov p, edi;
		}
		if (p+9 > pDec+n)
		{
			int c=1;
		}
	}
	while(a.last > 1 || a.pValue[0] != 0);
	while (p[-1] == '0' && p > pDec+1)
	{
		p--;
	}
	s.resize(p-pDec);
	char temp;
	for(int m=0;m<s.size()/2;m++)
	{
		temp=s[m];
		s[m]=s[s.size()-1-m];
		s[s.size()-1-m]=temp;
	}
}

void CBigInt::ToHexStr(std::string &s)
{
	DWORD n = DWORD(last * 9 + 1);
	s.resize(n,0);
	char* pHex =(char *) s.begin();
	for (DWORD i=last; i>0; i--)
	{
		sprintf(pHex, "%08x ", pValue[i-1]);
		pHex += 9;
	}
	s.resize(pHex-(char*)s.begin());
}

std::string CBigInt::ToDecStr()
{
	std::string s;
	ToDecStr(s);
	return s;
}

std::string CBigInt::ToHexStr()
{   
	std::string s;
	ToHexStr(s);
	return s;
}

CBigInt CBigInt::operator / (DWORD dwValue) //返回商
{
	CBigInt temp(*this);
	temp /= dwValue;
	return temp;
}

CBigInt CBigInt::operator / (CBigInt& x)//返回商
{
	CBigInt temp(*this);
	temp /= x;
	return temp;
}
CBigInt CBigInt::operator % (CBigInt& x)
{
	CBigInt temp(*this);
	return temp /= x;
}
DWORD CBigInt::operator % (DWORD dwValue)
{
	CBigInt temp(*this);
	return	temp /= dwValue;
}
#endif

void swap(CBigInt &a,CBigInt &b)
{ 
    CBigInt temp;
	temp=a;
	a=b;
	b=temp;
}
void heapadjust(CBigInt *a,int s,int n)
{   
	CBigInt temp;
     temp=a[s];
   for(int j=2*s;j<=n;j*=2)
	{
		if(j<n&&(a[j]>a[j+1]))
			++j;
		if(!(temp>a[j]))
			break;  //int Cmp(CBigInt& A); 
		a[s]=a[j];
		s=j;
	}
	a[s]=temp;
}
void heapcreat(CBigInt*a,int n)
{   
	 
	for(int i=n/2;i>0;--i)
		heapadjust(a,i,n);
}
void heapsort(CBigInt *a,int n)
{
	for(int i=n/2;i>0;--i)
		heapadjust(a,i,n);
	for(i=n;i>1;--i)
	{   
		swap(a[1],a[i]);
		heapadjust(a,1,i-1);
		}
}
void insert1(CBigInt *a,CBigInt x,int *p)
{   
	(*p)++;
	int n=*p;
	 
	a[n]=x;
    int i=n;
	while(i>1&&(a[i/2]>a[i]))
	{
		swap(a[i],a[i/2]);
		i=i/2;
    }
}
CBigInt deletemin1(CBigInt *a,int *p)
{   
	int n=*p;
	CBigInt min2;
	min2=a[1];
    a[1]=a[n];
	(*p)--;
	n=*p;
	int j,i=1;
	while(i<=(n/2))
	{
		if((a[2*i+1]>a[2*i])||(2*i==n))
		    j=2*i;
		else j=2*i+1;
		if(a[i]>a[j])
		{
		   swap(a[i],a[j]);
		   i=j;
		}
		else
		   return min2;
	}
	return min2;
}

void main()
{
	double start=clock();
	int i=0,length=0,k=0,j=0,or,xb;
	int temp;

	ifstream inf("input.txt");
	ofstream outf("output.txt");
	
	//读数
	inf>>length;
	int* list;
	list=new int[length];//申请排列空间
	int* orders=new int[length];
	if (list==NULL||orders==NULL) 
	{
		cout <<"内存不够,程序运行中止";
		exit(0);
	}
	if (length<3) {cout<<"排列元素太少！"<<endl; exit(0);}
	for(i=0;i<length;i++)
		list[i]=i+1;
	
	for(j=0,or=0;j<length;j++)//每位的逆序值
	{
		inf>>i;

		for (xb=0;xb<length;xb++) if (list[xb]==i) break;//查找i数在排列中的位置
		temp=list[xb];
		list[xb]=list[j];
		list[j]=temp; 
		if (xb!=j) or++;

		for (int k=xb-1,int l=xb;k>j;)
		{
			if (list[k]>list[l]) { temp=list[k];
									list[k]=list[l];
									list[l]=temp;
									k--;l--;or++;
								 }
			else break;
		}
		orders[j]=or;
		or=0;
	}
	
	
	CBigInt sum=CBigInt();
	CBigInt tp=CBigInt(1),t= CBigInt(2);
	for(j=length-1-1;j>=0;j--)
	{
		sum+=tp*orders[j];tp*=t++;
	}
	outf<<sum.ToDecStr()<<endl;

	//输出下一序列
	k=length-1;
	if (list[length-1]>list[length-2]) 
	//倒数两个的比较，最后一个比前一个大，结果则明了
	{
		temp=list[length-1];list[length-1]=list[length-2];list[length-2]=temp;	
	}
	else
	{
		for(j=length-2;j>0;) if (list[j-1]>list[j]) j--;  else break;
		k=j-1;   //交换位置
		for(xb=length-1;xb<=j;xb--) if (list[xb]>list[k]) break;//最小较大数
		temp=list[k];list[k]=list[xb];list[xb]=temp;//交换
	}

	for(xb=0;xb<=k;xb++) outf<<list[xb]<<" ";	//正序输出前K个元素
	for(xb=length-1;xb>k;xb--) outf<<list[xb]<<" ";//逆序输出剩下元素
	outf<<endl;
}