← RoseCode

ROSECODE 482

置换的周期

Period of permutation

liuguangxi · 数学 ·

令 i1,i2,i3,…,in 为集合 {1,2,3,...,n} 的排列,其中 n 为正整数。排列也可以被视为函数 f。我们用 2-by-n 数组表示此排列 f=(12⋯ni1i2⋯in) 它将编号 1 映射到 i1,将编号 2 映射到 i2,依此类推。当该函数对集合1,2,3,...,n的排列,即x1,x2,x3,⋯,xn进行操作时,可以获得新的排列y1,y2,y3,⋯,yn。这里是y1=f(x1),y2=f(x2),⋯,yn=f(xn)。

例如,当 n=4 和 2,4,1,3 存在排列时。我们让这个排列连续地运行在一个排列 1,2,3,4 上,那么它将是 1,2,3,4→2,4,1,3→4,3,2,1→3,1,4,2→1,2,3,4→⋯ 显然,在 4 操作之后,结果排列返回到初始排列。

令 F(l,p) 为集合 {1,2,3,...,l} 的排列数,这使得排列 1,2,3,⋯,l 在 p 操作后返回到其自身。例如,F(4,3)=9,因为存在满足条件的 9 排列:(1,2,3,4)、(1,3,4,2)、(1,4,2,3)、(2,3,1,4)、(2,4,3,1)、(3,1,2,4)、(3,2,4,1)、(4,1,3,2)、(4,2,1,3)。您还获得了 F(5,5)=25、F(10,6)=625176、F(20,11)=609493248001。

让S(L,P)=∑l=1L∑p=1PF(l,p)。找到 S(10000,1000)mod1000000007。


感谢 百黑客 为了这个想法。