OJの回答にあるこのコードをどう理解すればよいでしょうか?

Question

問題の説明

数値シーケンスは次のように定義されます:

f(1) = 1、f(2) = 1、f(n) = (A f(n - 1) B f(n - 2)) mod 7.

A、B、n が与えられた場合、f(n) の値を計算します。

入力

入力は複数のテスト ケースで構成されます。各テスト ケース
には、1 行に 3 つの整数 A、B、n が含まれています (1 <= A, B <= 1000、1
<= n <= 100,000,000)。 3 つのゼロは入力の終了を示し、この
テスト ケースは処理されません。

出力

各テスト ケースについて、f(n) の値を 1 行に出力します。

サンプル入力

1 1 3

1 2 10

0 0 0

サンプル出力

2

5

リーリー

Answer 1

オンライン上に問題解決レポートはありませんか?この質問はパターンを探しています。この質問の q は周期 T を探しています。なぜ最初の 54 個だけを探すのかというと、これには厳密な数学的推論が必要です。テストしたところ、53 は問題ありませんが、52 未満ではないことがわかりました。

--------------余談---------------

この種の質問は、一見すると表を作るかパターンを探すかのような感じです。

この問題が間違った問題ではないという前提の下では、この種の問題を解く方法は間違いなく 2 つあります。乱暴に表を作成するかパターンを見つけるかです。前者はこの問題が大きな問題であることを意味し、後者はこの問題が大きな問題であることを意味します。は推論の問題ですよね? 水は推論の難易度によって異なりますが、この問題に関して言えば、インターネット上で問題解決レポートを直接開く人もいます。彼らがピリオドを見つけて飛び出すまで1000。

Answer 2

以下のディスカッションは制限されていますi>=1:

• 明らかにf(i) in { 0 .. 6}

• したがって、この状態空間は制限されており、最大値は 49 を超えません<f(i-2), f(i-1)>

• つまり、

  にはピリオドがあり、49はピリオドですf(i)

• 次に、サイクル全体を列挙し、サイクル内で

  と同じ位置にある番号 f(n)

  を見つけます。

追加:

コード内の

• q は最短のピリオドではありません。実際、最初のピリオドを見つけたら停止できます
  。
• nが49の倍数の場合に返される必要があります

  これはバグである可能性がありますf[0]=0