Pythonで回文のないmサイズのアルファベットからの文字で作られたn個の長さの文字列を見つけるプログラム

m個の文字と別の値nがあるとします。これらのm文字から文字で作成された長さnの文字列の数を数える必要があり、文字列には1より大きい長さの回文部分文字列はありません。答えが大きすぎる場合は、結果を10 ^ 9+7で変更します。

したがって、入力がn =2 m =3の場合、m =3であるため、出力は6になります。したがって、アルファベットが{x、y、z}の場合、次のような文字列を生成できます。[xx、xy、xz 、yx、yy、yz、zx、zy、zz]ですが、[xx、yy、zz]は無効であるため、6つの文字列があります。

これを解決するには、次の手順に従います-

• p：=10 ^ 9 + 7
• nが1と同じ場合、
  • return m mod p
• nが2と同じ場合、
  • return m *（m-1）mod p
• m <=2の場合、
  • 0を返す
• return m *（m-1）*（（m-2）^（n-2）mod p）mod p

例

理解を深めるために、次の実装を見てみましょう-

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))

入力

3, [1,2,3,4,1]

出力

6