Pythonの無限シーケンスから生成されたベクトルの内積を見つけるプログラム

3つの整数c、m、およびnが与えられていると仮定します。最初の値が0、2番目の値がc、3番目の値以降はki =（ki-2 + ki-1）modmに等しい無限シーケンスを生成する必要があります。アイテムk2n+1までのシリーズのすべての値を生成する必要があります。今シリーズの値から;シーケンス内の2つの連続する値を、2次元ベクトルのx座標とy座標として取得し、n個のベクトルを生成します。注意点として、3番目の値から順番に値を使用します。別のセットSがあり、各値はベクトルiとベクトルjの内積であり、1 <=i、j <=nおよびi！=jです。セットS内の異なる残基の数を見つける必要があります。値が非常に大きい場合は、mで変更します。

したがって、入力が5、6、4のような場合、出力は3

生成されるシーケンスは次のとおりです：[0、5、5、4、3、1、4、5、3、2]。

ベクトルは次のとおりです：（5、4）、（3、1）、（4、5）、（3、2）。

ベクトルの内積から、セットSには3つの残差値mod6しかありません。

したがって、結果は3 mod 6=3になります。

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

• nが1と同じ場合、
  • 0を返す
• それ以外の場合、
  • temp_arr：=0で初期化されたサイズ2* n+2の新しいリスト
  • temp_arr [0]：=0
  • temp_arr [1]：=c
  • arr2：=新しいリスト
  • 2〜2 * n + 2の範囲のiの場合、実行
    • temp_arr [i]：=（temp_arr [i-1] + temp_arr [i-2]）mod m
  • 2〜2 * n-2の範囲のiの場合、2ずつ増やします。
    • temp：=（temp_arr [i] * temp_arr [i + 2] + temp_arr [i + 1] * temp_arr [i + 3]）mod m
    • arr2の最後にtempを挿入
    • temp：=（temp_arr [i] * temp_arr [i + 4] + temp_arr [i + 1] * temp_arr [i + 5]）mod m
    • arr2の最後にtempを挿入
  • temp：=（temp_arr [2 * n-2] * temp_arr [2 * n] + temp_arr [2 * n-1] * temp_arr [2 * n + 1]）mod m
  • arr2の最後にtempを挿入
  • arr2から重複するアイテムを削除する
  • arr2の戻りサイズ

例

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

def solve(c, m, n):
   if (n == 1):
      return 0
   else:
      temp_arr=[0 for i in range(2 * n+2)]
      temp_arr[0] = 0
      temp_arr[1] = c
      arr2 = []
      for i in range(2, 2 * n+2):
         temp_arr[i] = (temp_arr[i - 1] + temp_arr[i - 2]) % m
      for i in range(2, 2 * n-2, 2):
         temp = (temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) % m
         arr2.append(temp)
         temp = (temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) % m
         arr2.append(temp)
      temp = (temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n- 1] * temp_arr[2 * n+1]) % m
      arr2.append(temp)
      arr2 = set(arr2)
      return len(arr2)

print(solve(5, 6, 4))

入力

5, 6, 4

出力

3