翻译版原题如下取自https://pe-cn.github.io/902/第一版deffactorial(n):计算n的阶乘result1foriinrange(2,n1):result*ireturnresultdefrank(perm): 计算置换perm的rank字典序位置从1开始 perm是一个列表perm[i]表示位置i1的值 nlen(perm)r1# rank从1开始foriinrange(n):# 计算在位置i有多少个未使用的数小于perm[i]count0forjinrange(i1,n):ifperm[j]perm[i]:count1rcount*factorial(n-i-1)returnrdefcompute_sigma(m): 计算σ置换 n m(m1)/2 σ(i) k(k-1)/2 1 如果存在k使得i k(k1)/2 σ(i) i 1 其他情况 nm*(m1)//2sigma[0]*(n1)# 1-indexed# 标记特殊位置special_positionsset()forkinrange(1,m1):posk*(k1)//2special_positions.add(pos)foriinrange(1,n1):ifiinspecial_positions:# 找到k使得i k(k1)/2forkinrange(1,m1):ifik*(k1)//2:sigma[i]k*(k-1)//21breakelse:sigma[i]i1returnsigma[1:]# 返回0-indexed列表defcompute_tau(n): 计算τ置换 τ(i) ((10^9 7) * i mod n) 1 MOD_BASE10**97tau[0]*(n1)# 1-indexedforiinrange(1,n1):tau[i]((MOD_BASE*i)%n)1returntau[1:]# 返回0-indexed列表defcompute_inverse(perm):计算置换perm的逆置换nlen(perm)inv[0]*nforiinrange(n):inv[perm[i]-1]i1# perm是1-indexed的值returninvdefcompute_pi(m): 计算π置换 π(i) τ^(-1)(σ(τ(i))) nm*(m1)//2sigmacompute_sigma(m)taucompute_tau(n)tau_invcompute_inverse(tau)# π(i) τ^(-1)(σ(τ(i)))# 注意sigma, tau, tau_inv都是0-indexed列表但存储的是1-indexed的值pi[0]*nforiinrange(n):# i是0-indexed的位置对应1-indexed的i1tau_itau[i]# τ(i1)这是1-indexed的值sigma_tau_isigma[tau_i-1]# σ(τ(i1))pi[i]tau_inv[sigma_tau_i-1]# τ^(-1)(σ(τ(i1)))returnpidefcompose_permutations(p1,p2): 计算置换的复合 p1 ∘ p2 即先应用p2再应用p1 nlen(p1)result[0]*nforiinrange(n):# p2[i]是位置i1映射到的值1-indexed# 需要在p1中找到这个值对应的位置result[i]p1[p2[i]-1]returnresultdefpower_permutation(perm,k):计算置换perm的k次幂nlen(perm)ifk0:returnlist(range(1,n1))# 恒等置换resultlist(range(1,n1))# 恒等置换baseperm[:]whilek0:ifk%21:resultcompose_permutations(base,result)basecompose_permutations(base,base)k//2returnresultdefcompute_P(m): 计算P(m) Σ(k1 to m!) rank(π^k) nm*(m1)//2picompute_pi(m)total0m_factfactorial(m)# 计算π的幂pi_powerlist(range(1,n1))# 初始为恒等置换forkinrange(1,m_fact1):pi_powercompose_permutations(pi,pi_power)rrank(pi_power)totalrifk3orkm_fact:# 只显示前几个和最后一个print(f k{k}: rank{r})returntotal# 验证例子 print(验证例子) print(rank([2,1,3]) , rank([2, 1, 3])) print(期望值3) print() print(计算P(2)) p2 compute_P(2) print(fP(2) {p2}) print(f期望值4) print(f匹配{p2 4}) print() print(计算P(3)) p3 compute_P(3) print(fP(3) {p3}) print(f期望值780) print(f匹配{p3 780}) print() print(计算P(4)) p4 compute_P(4) print(fP(4) {p4}) print(f期望值38810300) print(f匹配{p4 38810300}) print(计算P(10))p10compute_P(10)print(fP(10) {p10})优化版importmathfrommathimportgcd MOD10**97deffactorial_mod(n,mod):计算n! mod modresult1foriinrange(2,n1):result(result*i)%modreturnresultdeffactorial(n):计算n的阶乘完整值result1foriinrange(2,n1):result*ireturnresultdefrank_mod(perm,mod): 计算置换perm的rank字典序位置从1开始并对mod取模 使用优化的算法边计算边取模 nlen(perm)r1# rank从1开始# 预计算阶乘facts[1]*(n1)foriinrange(1,n1):facts[i](facts[i-1]*i)%modforiinrange(n):# 计算在位置i有多少个未使用的数小于perm[i]count0forjinrange(i1,n):ifperm[j]perm[i]:count1r(rcount*facts[n-i-1])%modreturnrdefcompute_sigma(m): 计算σ置换 n m(m1)/2 σ(i) k(k-1)/2 1 如果存在k使得i k(k1)/2 σ(i) i 1 其他情况 nm*(m1)//2sigma[0]*(n1)# 1-indexed# 标记特殊位置special_positionsset()forkinrange(1,m1):posk*(k1)//2special_positions.add(pos)foriinrange(1,n1):ifiinspecial_positions:# 找到k使得i k(k1)/2forkinrange(1,m1):ifik*(k1)//2:sigma[i]k*(k-1)//21breakelse:sigma[i]i1returnsigma[1:]# 返回0-indexed列表defcompute_tau(n): 计算τ置换 τ(i) ((10^9 7) * i mod n) 1 MOD_BASE10**97tau[0]*(n1)# 1-indexedforiinrange(1,n1):tau[i]((MOD_BASE*i)%n)1returntau[1:]# 返回0-indexed列表defcompute_inverse(perm):计算置换perm的逆置换nlen(perm)inv[0]*nforiinrange(n):inv[perm[i]-1]i1# perm是1-indexed的值returninvdefcompute_pi(m): 计算π置换 π(i) τ^(-1)(σ(τ(i))) nm*(m1)//2sigmacompute_sigma(m)taucompute_tau(n)tau_invcompute_inverse(tau)# π(i) τ^(-1)(σ(τ(i)))pi[0]*nforiinrange(n):tau_itau[i]# τ(i1)这是1-indexed的值sigma_tau_isigma[tau_i-1]# σ(τ(i1))pi[i]tau_inv[sigma_tau_i-1]# τ^(-1)(σ(τ(i1)))returnpidefcompose_permutations(p1,p2): 计算置换的复合 p1 ∘ p2 即先应用p2再应用p1 nlen(p1)result[0]*nforiinrange(n):result[i]p1[p2[i]-1]returnresultdefget_cycle_lengths(perm): 获取置换的循环分解中各个循环的长度 nlen(perm)visited[False]*n cycle_lengths[]foriinrange(n):ifnotvisited[i]:length0jiwhilenotvisited[j]:visited[j]Truejperm[j]-1# perm[j]是1-indexed的值length1cycle_lengths.append(length)returncycle_lengthsdefcompute_permutation_order(perm): 计算置换的阶order 阶是所有循环长度的最小公倍数 cycle_lengthsget_cycle_lengths(perm)order1forlengthincycle_lengths:orderlcm(order,length)returnorderdeflcm(a,b):计算最小公倍数returna*b//gcd(a,b)defcompute_P_optimized(m): 计算P(m) Σ(k1 to m!) rank(π^k) mod (10^9 7) 利用置换的周期性进行优化 nm*(m1)//2picompute_pi(m)# 计算π的阶ordercompute_permutation_order(pi)print(f置换π的阶:{order})# 计算m!m_factfactorial(m)print(fm! {m_fact})# 计算一个周期内的rank和print(f计算一个周期内的rank和需要计算{order}次...)cycle_sum0pi_powerlist(range(1,n1))# 初始为恒等置换# 只计算前几个用于验证forkinrange(1,min(order,4)1):pi_powercompose_permutations(pi,pi_power)rrank_mod(pi_power,MOD)cycle_sum(cycle_sumr)%MODprint(f k{k}: rank mod (10^97) {r})# 如果order很小计算完整的周期和iforder10000:forkinrange(4,order):pi_powercompose_permutations(pi,pi_power)rrank_mod(pi_power,MOD)cycle_sum(cycle_sumr)%MODelse:# 如果order很大需要继续计算这里可能需要更长时间的计算print(f 警告阶{order}很大继续计算可能需要较长时间...)forkinrange(4,order):pi_powercompose_permutations(pi,pi_power)rrank_mod(pi_power,MOD)cycle_sum(cycle_sumr)%MODifk%1000000:print(f 已计算到k{k})print(f一个周期内的rank和:{cycle_sum})# 计算P(m)# P(m) (m!/order) * cycle_sum 剩余部分quotientm_fact//order remainderm_fact%orderprint(fm! / order {quotient}, 余数 {remainder})# 计算剩余部分remaining_sum0ifremainder0:print(f计算剩余{remainder}项...)pi_powerlist(range(1,n1))forkinrange(1,remainder1):pi_powercompose_permutations(pi,pi_power)rrank_mod(pi_power,MOD)remaining_sum(remaining_sumr)%MOD# P(m) quotient * cycle_sum remaining_sumresult(quotient%MOD*cycle_sum%MODremaining_sum)%MODreturnresult# 验证例子 print( * 60) print(验证例子) print(rank([2,1,3]) , rank_mod([2, 1, 3], MOD)) print(期望值3) print() print( * 60) print(计算P(2)) p2 compute_P_optimized(2) print(fP(2) {p2}) print(f期望值4) print(f匹配{p2 4}) print() print( * 60) print(计算P(3)) p3 compute_P_optimized(3) print(fP(3) {p3}) print(f期望值780) print(f匹配{p3 780}) print() print( * 60) print(计算P(4)) p4 compute_P_optimized(4) print(fP(4) {p4}) print(f期望值38810300) print(f匹配{p4 38810300}) print(计算P(10))p10compute_P_optimized(10)print(fP(14) {p10})里题目要求的p(100)还很远但理解力和正确性、简单的优化能力都不错了。