问题 1378. -- 猴子排序问题

1378: 猴子排序问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 16  解决: 2
[提交][状态][讨论版]

题目描述

我们知道有一种神奇的排序方法叫做猴子排序,就是把待排序的数字写在卡片上,然后让猴子把卡片扔在空中,等落下的时候观察这些卡片是否从左到右已经排序完成(我们认为不会发生卡片落地后叠在一起的情况)如果有序则排序完成,否则让猴子再扔一遍,直到卡片有序,那么问题来了,给你N个卡片,每个卡片上写着一个大写字母,请问猴子第一次扔这些卡片就按字典序排序完成的概率有多大?

输入

第一行是一个整数N(1<N<100)表示给猴子N张卡片,接下来是一个长度为N的字符串,代表这些卡片上所写的字母。

输出

输出一行,表示猴子排序第一次就成功的概率(用分子为1的分数表示)。

样例输入

7
SCIENCE

样例输出

1/1260

提示

来源

[提交][状态]