PythonのAjobシーケンスからシーケンスを選択する方法の数を見つけるためのプログラム

Ajob言語と呼ばれる奇妙な言語があるとします。文字数は無限です。私たちはこの言語でn語を知っています。最初の単語は1文字の長さで、2番目の単語は2文字の長さというように続きます。そして、単語内のすべての文字は一意です。 n個の単語のいずれかを選択し、そこからサブシーケンスを形成するとします。サブシーケンスの長さは、元の単語の長さよりk短くする必要があります。たとえば、選択した単語の長さがLの場合、サブシーケンスの長さは（L --k）になります。長さがkより小さい単語がある場合は、その単語を選択しないでください。また、2つのサブシーケンスは、長さが異なる場合、または同じ位置に異なる文字が含まれている場合、互いに異なります。 pを法とする結果を見つけなければなりません。piは素数です。

したがって、入力がn =6、k =5、p =11の場合、出力は7になります。

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

• 空の辞書メモを1つ作成する
• n：=n + 1、k：=k + 1
• fact：=1つの要素を持つリスト1
• 1からp-1の範囲のiについては、
  • ファクトの最後に（ファクトの最後の要素* i mod p）を挿入します
• メモにpが含まれている場合は、
  • inv_fact：=memo [p]
• それ以外の場合、
  • inv：=0つの要素が0と1のリスト
  • 2からp-1の範囲のiについては、
    • invの最後に（p-p / i * inv [p mod i] mod pのフロア）を挿入します
  • inv_fact：=1つの要素を持つリスト1
  • 1からp-1の範囲のiについては、
    • inv_factの最後に（inv_fact * inv [i] mod pの最後の要素）を挿入します
  • メモ[p]：=inv_fact
• ret：=1
• n> 0の場合、do
  • n1：=n mod p
  • k1：=k mod p
  • k1> n1の場合、
    • 0を返す
  • ret：=ret * fact [n1] * inv_fact [k1] * inv_fact [n1-k1] mod p
  • n：=（n / p）のフロア
  • k：=k/pのフロア
• return ret

例

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

memo = {}
def solve(n, k, p):
   n += 1
   k += 1
   fact = [1]
   for i in range(1, p):
      fact.append(fact[-1] * i % p)
   if p in memo:
      inv_fact = memo[p]
   else:
      inv = [0, 1]
      for i in range(2, p):
         inv.append(p - p // i * inv[p % i] % p)
      inv_fact = [1]
      for i in range(1, p):
         inv_fact.append(inv_fact[-1] * inv[i] % p)
      memo[p] = inv_fact
   ret = 1
   while n > 0:
      n1 = n % p
      k1 = k % p
      if k1 > n1:
         return 0
      ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
      n //= p
      k //= p
   return ret

n = 6
k = 5
p = 11
print(solve(n, k, p))

入力

6, 5, 11

出力

7