Pythonで解く：m種類の文字から作る長さnの回文を含まない文字列の個数を求める方法

問題の概要

m種類の文字と整数nが与えられたとき、これらの文字を使って構成できる「長さ2以上の回文（前から読んでも後ろから読んでも同じになる文字列）を部分文字列として含まない」長さnの文字列の個数を求める問題です。答えが非常に大きな値になる可能性があるため、10⁹+7で割った余りを返します。

具体例で理解する

例として、n = 2、m = 3 のケースを見てみましょう。使用できる文字が {x, y, z} の3種類であるとき、理論上は [xx, xy, xz, yx, yy, yz, zx, zy, zz] の9通りの文字列が作れます。しかし、このうち [xx, yy, zz] は同じ文字が2つ並んでおり、長さ2の回文を含んでいるため条件を満たしません。結果として、有効な文字列は6個となります。

解法のポイント

この問題の鍵となるのは、「長さ2以上の回文を含まない」という条件が「長さ2と長さ3の回文を含まない」ことと同等であるという点です。なぜなら、それより長い回文は必ずその中心部分に長さ2または3の回文を内包しているからです。

この性質をもとに、各位置の文字の選び方を整理すると以下のようになります。

• 1文字目：自由に選べるため、m通り
• 2文字目：1文字目と異なる必要がある（長さ2の回文を回避）ため、m−1通り
• 3文字目以降：直前の文字と異なり（長さ2の回文を回避）、かつその前の文字とも異なる（長さ3の回文を回避）必要があるため、m−2通り

以上より、答えは m × (m−1) × (m−2)ⁿ⁻² という式で表せます。また、m ≤ 2 の場合は n ≥ 3 の文字列を構成することが不可能なので、答えは0になります。

解法の手順

• p := 10⁹+7 を法（モジュロ）として設定する
• n が 1 の場合：m mod p を返す
• n が 2 の場合：m × (m−1) mod p を返す
• m ≤ 2 の場合：0 を返す
• それ以外の場合：m × (m−1) × ((m−2)ⁿ⁻² mod p) mod p を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(n, m):
   p = 10**9+7
   if n == 1:
      return m % p
   if n == 2:
      return m * (m - 1) % p
   if m <= 2:
      return 0
   return m * (m - 1) * pow(m - 2, n - 2, p) % p

n = 2
m = 3
print(solve(n, m))

このコードで使われている組み込み関数 pow(底, 指数, 法) は、冪乗を指定した数で割った余りを高速に計算できる便利な関数です。指数が非常に大きい場合でも、繰り返し二乗法によって効率的に処理されます。

入力と出力

入力：

n = 2, m = 3

出力：

6

まとめ

本記事では、回文を含まない文字列の個数を求める問題を取り上げました。重要なのは「長い回文は必ず短い回文（長さ2または3）を含む」という観察です。これにより、各文字の選択肢が m−2 通りに限定され、冪乗計算だけで答えを導き出せるシンプルな公式が得られます。計算量は O(log n) 程度に抑えられるため、n が非常に大きい場合でも高速に動作するのが魅力です。