Pythonでリストの全順列における特別な値Sの平均を計算するプログラム

問題の概要

要素のリストが与えられたとき、次のアルゴリズムに従って値Sを計算できるものとします。

while L のサイズが 1 より大きい間、繰り返す:
    a := L[0]
    b := L[1]
    L[1] を削除
    L[0] := a + b + a*b
return L[0] mod (10^9 + 7)

この問題では、リストLのすべての可能な順列(並べ替え)から計算されるSの値の平均を求める必要があります。

例えば、入力が L = [5, 3, 4] の場合、出力は 119 になります。これは、どのような順列であってもSの値が常に119になるため、その平均も119となるからです。

解法のポイント:(a+1)(b+1) − 1 の性質

この問題を効率的に解く鍵は、演算 a + b + a*b を変形することです。実は、次の恒等式が成り立ちます。

a + b + a*b = (a+1)(b+1) − 1

この性質を繰り返し適用すると、最終的なSの値は「各要素に1を加えたものの総積から1を引いた値」、すなわち

S = (x₁+1)(x₂+1)...(xₙ+1) − 1  (mod 10^9+7)

となることが分かります。積の計算結果は要素の順序に依存しないため、リストの順列がどれであってもSの値は常に同一になります。したがって、「すべての順列に対するSの平均」を求めるには、任意の一つの順列に対するSの値を計算すれば十分です。

解く手順

• m := 10^9 + 7 とする
• li := L の各要素 x に対して x+1 としたリストを作成する
• prod := 1 で初期化する
• li の各要素 i について、以下を繰り返す
  • prod := prod * i
  • prod := prod mod m
• (prod − 1) mod m を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(L):
    m = 10**9+7
    li = [x+1 for x in L]
    prod = 1
    for i in li:
        prod *= i
        prod %= m
    return (prod-1) % m

L = [5,3,4]
print(solve(L))

入力

[5,3,4]

出力

119

計算量の考察

この解法の時間計算量は O(n)(nはリストの長さ)です。もしすべての順列(n!通り)を実際に生成してそれぞれSを計算すると、リストが少し大きくなるだけで現実的な時間では処理できません。しかし、上記の数学的性質を利用すれば、順列を列挙せずに線形時間で答えを求められます。また、各ステップで剰余(mod)を取ることで、巨大な数によるオーバーフローを防いでいる点も重要です。