【拾题杂谈】GYM100517F Frequent Permutations
题面
题目描述
彼得正在开发新的赌博软件。现在他正在编写一部分软件,可以处理纸牌组。为此,他需要生成从 $1$ 到 $n$ 的整数的随机排列。
不幸的是,彼得不知道这样做的好算法。所以他使用以下算法。首先初始化 $a[i] = i$ 。然后 $t$ 次选择从 $1$ 到 $n$ 的均匀随机 $i$ 和从 $1$ 到 $n$ 的随机 $j$ ,并交换 $a[i]$ 和 $a[j]$ 。
约翰了解了彼得生成随机排列的方法,并决定利用他的知识在赌场获胜。约翰想知道在彼得方法生成的排列中,哪种排列最常发生,它的概率是多少。
请帮助越好找到这个序列以及他的概率。
输入格式
输入包含多组数据。
每一组数据输入一行两个整数 $n,t$ 含义如题面 $(\ 1\le n\le 14,0\le t\le 300\ )$ 。
最后一行输入两个零表示读入结束。
输出格式
对于每组数据,输出两行,第一行输出出现概率最大的序列,第二行输出它出现的概率,用最简分数表示。
样例输入
1 | 3 3 |
样例输出
1 | 1 2 3 |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 祝馀宫!
评论