F-猴子排序的期望

其实就是个有重复元素的排序，但是大数模拟很麻烦，用Python3……

链接：https://www.nowcoder.com/acm/contest/116/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
我们知道有一种神奇的排序方法叫做猴子排序，就是把待排序的数字写在卡片上，然后让猴子把卡片扔在空中，等落下的时候观察这些卡片是否从左到右已经排序完成（我们认为不会发生卡片落地后叠在一起的情况）如果有序则排序完成，否则让猴子再扔一遍，直到卡片有序，那么问题来了，给你N个卡片，每个卡片上写着一个大写字母，请问猴子第一次扔这些卡片就按字典序排序完成的概率有多大?

输入描述:
第一行是一个整数N(1<N<100)表示给猴子N张卡片，接下来是一个长度为N的字符串，代表这些卡片上所写的字母。
输出描述:
输出一行，表示猴子排序第一次就成功的概率(用分子为1的分数表示)。
示例1
输入
7
SCIENCE
输出

1/1260

import math
 
n = int(input())
str1 = input()
 
sum = math.factorial(n)
 
li = [0]*26
for c in str1:
    li[ord(c)-ord('A')]+=1
 
for i in li:
    sum = sum//math.factorial(i)
 
print('1/%d'%sum)

秒客网

F-猴子排序的期望

相关文章