作者tml (流刑人形)
看板puzzle
標題[中譯] ProjectEuler 483 Repeated permutation
時間Tue Oct 7 05:14:10 2014
483. Repeated permutation
https://projecteuler.net/problem=483
我們把每一個改變數列{1, 2, 3, ..., n}元素順序的操作稱為一種重排。對於有n個
元素的集合則有n!種重排的方式（包括維持所有元素順序不動的操作）。當n = 3時
共有3! = 6種重排方式列舉如下：
- P_1 = 維持原順序不作更動
- P_2 = 交換第一、二個元素
- P_3 = 交換第一、三個元素
- P_4 = 交換第二、三個元素
- P_5 = 所有元素往右輪換一個位置
- P_6 = 所有元素往左輪換一個位置
如果反覆操作其中一種重排，則終將會回到一開始的順序。給定一重排P_i，令f(P_i)
為反覆操作P_i以得到原始順序的最小所需次數。例如，當n = 3時：
- f(P_1) = 1 : (1,2,3) → (1,2,3)
- f(P_2) = 2 : (1,2,3) → (2,1,3) → (1,2,3)
- f(P_3) = 2 : (1,2,3) → (3,2,1) → (1,2,3)
- f(P_4) = 2 : (1,2,3) → (1,3,2) → (1,2,3)
- f(P_5) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)
- f(P_6) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3)
令g(n)為給定數列長度n時，對所有P_i取f(P_i)^2的平均值。
g(3) = (1^2 + 2^2 + 2^2 + 2^2 + 3^2 + 3^2)/3! = 31/6 ≒ 5.166666667e0
g(5) = 2081/120 ≒ 1.734166667e1
g(20) = 12422728886023769167301/2432902008176640000 ≒ 5.106136147e3
請求出g(350)，以科學記號表示答案至十位有效位數，並如同上面三個例子一般、
以小寫e作為真數與首數的區隔。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.2.129.153
※ 文章網址: http://webptt.com/m.aspx?n=bbs/puzzle/M.1412630053.A.C1C.html