组合数学的确出题的顺序和方法十分灵活。
今天又做了一个组合数学的题目。
题目描述：
Description
The base of the hexadecimal system is 16. In order to write down numbers in this system one uses 16 digits 0,1,...,9,A,B,C,D,E,F. The capital letters A,..,F stands for 10,..,15, respectively. For instance the value of the hexadecimal number CF2 is 12 * 162 + 15 * 16 + 2 = 3314 in the decimal system. Let X be the set of all positive integers whose hexadecimal representations have at most 8 digits and do not contain repetitions of any digit. The most significant digit in such a representation is not zero. The largest element in X is the number with the hexadecimal representation FEDCBA98, the second largest is the number FEDCBA97, the third is FEDCBA96 and so forth.
Write a program that: finds the n-th largest element of X;
Output
Your program should output the n-th largest element in X in the hexadecimal representation.
题目的意思呢非常简单，就是给一个数n，要你求出在十六进制中第n大的数。
要求在这个十六进制中任何两个位上的字母不同。
显然的排列组合呢。
首先我的想法是，对于每个排到数位上有多少种情况先预处理，然后再实现的时候，逐步减去，这样的话就可以推出最后的答案了。
但是很悲催，wa了
后来仔细观察发现，原来题目的意思是最多八位，也就是说要求的这个数可能不足八位，这样，之前的预处理就必须在每次判断位数后重新处理一遍。
嗯的，就是这样，我就a了。
上代码：
＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
#define ll long long
using namespace std;
ll a[9],num[9],n;
bool b[17],flag;
char ch[17]={' ','0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
void get(ll x)
{
for (ll i=16; ;i--)
if (!b[i])
{
num[x]=i;
return;
}
}
void next(ll& x) { if (x==1) return; while (b[--x] && x>1) ; }
ll P(ll y,ll x)
{
ll ans=1;
for (ll i=y-x+1; i<=y; i++) ans*=i;
return ans;
}
int main()
{
for (ll i=1; i<=7; i++) a[i]=P(16-i,8-i);
a[8]=1;
while (scanf("%I64d",&n)!=EOF)
{
flag=false;
memset(b,false,sizeof b);
for (ll i=1; i<=8; i++)
{
get(i);
while (n>a[i] && num[i]>1) n-=a[i],next(num[i]);
b[num[i]]=true;
if (num[i]==1 && !flag)
{
b[1]=false;
for (ll j=i+1; j<=7; j++) a[j]=P(16-j+i,8-j);
}
else flag=true;
}
for (ll i=1; i<=8; i++)
{
if (num[i]>1)
{
while (i<=8) printf("%c",ch[num[i++]]);
printf("\n");
break;
}
}
}
return 0;
}
代码写得好挫，求不喷。
另注：最近精神不太好，代码能力有所下降，接下来要加油了呢。
