← 完整题目索引

PROJECT EULER · #0483

重复排列

Repeated Permutation

仅题目 · 待解原题 ↗

我们将排列定义为重新排列元素{1,2,3,...,n}顺序的操作。 n! 有这样的排列,其中一种排列使元素保持初始顺序。 对于 n=3,我们有 3!=6 排列:

  • P1= 保持初始订单
  • P2= 交换第一个st 和第二个nd 元件
  • P3= 交换第 1st 和 3rd 元件
  • P4= 交换第二nd 和第三rd 元件
  • P5= 向右旋转元素
  • P6= 将元素向左旋转

如果我们选择这些排列之一,并重复应用相同排列,我们最终会恢复初始顺序。
对于排列 Pi,令 f(Pi) 为通过重复应用排列 Pi 恢复初始顺序所需的步数。
对于 n=3,我们得到:

  • f(P1)=1:(1,2,3)→(1,2,3)
  • f(P2)=2:(1,2,3)→(2,1,3)→(1,2,3)
  • f(P3)=2:(1,2,3)→(3,2,1)→(1,2,3)
  • f(P4)=2:(1,2,3)→(1,3,2)→(1,2,3)
  • f(P5)=3:(1,2,3)→(3,1,2)→(2,3,1)→(1,2,3)
  • f(P6)=3:(1,2,3)→(2,3,1)→(3,1,2)→(1,2,3)

令 g(n) 为 f2(Pi) 在长度为 n 的所有排列 Pi 上的平均值。
g(3)=(12+22+22+22+32+32)/3!=31/6≈5.166666667e0
g(5)=2081/120≈1.734166667e1
g(20)=12422728886023769167301/2432902008176640000≈5.106136147e3

找到 g(350) 并以四舍五入到 10 有效数字的科学记数法写出答案,使用小写 e 分隔尾数和指数,如上面的示例所示。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。