题目大意：
I
n
p
u
t
I
n
p
u
t
(4,(3,2,1,4))
(5,(3,5,1,2,4))
-1
O
u
t
p
u
t
O
u
t
p
u
t
15,67
思路：
考试时居然把这道题推出来了。。。
然后还AK了。。。
正题：
这道题要我们求出这个排列是字典序第几大的，也就是让我们求
有多少个排列比该排列小
，再加1即是答案。
那么应该如何考虑呢？
举个例子
-
(
5
,
(
3
,
5
,
1
,
2
,
4
)
)
(5
,
(
3
,
5
,
1
,
2
,
4
)
)
这个排列是
-
3
5
1
2
4
35
1
2
4
考虑万位数，有多少个数只填万位数就
肯定
比它小呢？
很明显，如果必须比它小，那么就只有万位数为
1
1
或
才行。那么万位数为
1
1
或
的又有几个数呢？
如果把数字
1
1
放入万位
- 1_ _ _ _
无论后面放入什么数字，都满足这个数字小于
所以说，
后面的数字可以随便填，方案数为
4
！
4
！
（
！
！
表示阶乘，后面相同）
那么把
填进万位也有
4
！
4
！
种方法，所以仅看万位就有
2
×
4
!
=
48
2
×
4
!
=
48
种填法。
那么接下来看千位
- 3 _ _ _ _
填千位使得这个数必然小于
3
5
1
2
4
3
5
1
2
4
一共有几种方案呢？
按照原来的方法，应该有
4
×
3
!
=
24
4
×
3
!
=
24
种方法。
但是，这样错了！
我们来把这个过程模拟一遍。
这个数千位必须小于5，那么就有
1
1
，
，
3
3
，
四个数可填。
但是！
我们在填万位数的时候就已经把
1
1
或
填进去了，所以如果万位填
1
1
，那么千位就不能填
（每个数只能填一遍）,那就只有
2
2
，
，
4
4
三个数可填。同理，如果将
填入万位，就只有
1
1
，
，
3
3
三个数可填。
所以无论用哪种填法，千位都只能填3个数！
但是如果这个样例是这样的
-
那么千位就能填
1
1
，
两个数字，还是千位数减一。
那是为什么呢？
不难发现，两组数据的区别就在于
一个万位数比千位数大，一个万位数比千位数小
。
如果万位数比千位数小，那么这个数就不能填在千位数（以及百位数，十位数，个位数）。同理，若果一个数万位数比百位数小，那么这个数就不能填在百位数（以及十位数和个位数）上。
所以，回到样例，由于
3
<
5
3<
5
,所以千位数就少了一个候选数，也就变成了
3
×
3
!
=
18
3×
3
!
=
18
。按照这种方法求下去，就得到
-
0
×
2
!
=
0
0×
2
!
=
0
-
0
×
1
!
=
0
0×
1
!
=
0
-
0
×
0
!
=
0
0×
0
!
=
0
（真有趣）
那么总共就是
48
+
18
+
0
+
0
+
0
=
66
48+
18
+
0
+
0
+
0
=
66
个数字比
3
5
1
2
4
35
1
2
4
小。
那么
3
5
1
2
4
35
1
2
4
就是第67大的数字啦！我们再用这种方法把另一个样例试一遍。
-
原数
=
3214
=3214
-
2
×
3
!
=
12
2×
3
!
=
12
-
1
×
2
!
=
2
1×
2
!
=
2
-
0
×
1
!
=
0
0×
1
!
=
0
-
0
×
0
!
=
0
0×
0
!
=
0
和
=
12
+
2
+
0
+
0
=
14
=12
+
2
+
0
+
0
=
14
所以，
3214
3214
是字典序第15的数字。总结：
我们设
n
u
m
[
i
]
nu
m
[
i
]
表示第
i
i
个数字（从左往右数），
为
n
u
m
[
1
]
nu
m
[
1
]
到
n
u
m
[
i
−
1
]
nu
m
[
i
−
1
]
中，比
n
u
m
[
i
]
nu
m
[
i
]
大的数字个数，则
a
n
s
=
(
(
∑
i
=
1
n
(
n
u
m
[
i
]
−
a
[
i
]
−
1
)
×
(
n
−
1
)
!
)
)
+
1
an
s
=
(
(
∑
i
=
1
n
(
n
u
m
[
i
]
−
a
[
i
]
−
1
)
×
(
n
−
1
)
!
)
)
+
1
本题要用高精度！
#include <cstdio> #include <iostream> #include <string> #include <cstring> using namespace std; const int maxn=100; int n,x,num[101],a[101][maxn+1],size,k,b[101],t,c[maxn+1],o,kk,tot; string s; int main() { a[1][maxn]=1; for (int i=2;i<=50;i++) //初始化，求阶乘 { t=0; for (int j=maxn;j>=1;j--) { a[i][j]=a[i-1][j]*i+t; t=a[i][j]/10; a[i][j]%=10; } } while (++tot) { cin>>s; memset(num,0,sizeof(num)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); if (s=="-1") break; n=(int)s[1]-'0'; if (s[2]>='0'&&s[2]<='9') n=n*10+((int)s[2]-'0'); if (n==1) //特判 { if (tot>1) printf(","); printf("1"); continue; } if (tot>1) printf(","); size=s.size(); k=1; for (int i=1;i<size;i++) //读入，分离数字 if (s[i]=='(') { for (int j=i+1;j<size;j++) { if (s[j]>='0'&&s[j]<='9') b[k]=b[k]*10+((int)s[j]-'0'); if (s[j]==',') k++; if (s[j]==')') break; } break; } for (int i=1;i<=n;i++) //求出答案 { o=b[i]; for (int j=b[i]+1;j<=n;j++) num[j]++; b[i]--; b[i]-=num[o]; t=0; for (int j=maxn;j>=1;j--) { c[j]+=b[i]*a[n-i][j]+t; t=c[j]/10; c[j]%=10; } } c[maxn]++; //加1 t=0; for (int i=maxn;i>=1;i--) { c[i]+=t; t=c[i]/10; c[i]%=10; } kk=1; while (!c[kk]) kk++; for (int i=kk;i<=maxn;i++) printf("%d",c[i]); } return 0; } -