Bagaimana untuk memahami kod ini dalam jawapan OJ?

Question

Huraian Masalah

Jujukan nombor ditakrifkan seperti berikut:

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

Diberi A, B dan n, anda perlu mengira nilai f(n).

Input

Input terdiri daripada berbilang kes ujian. Setiap kes ujian
mengandungi 3 integer A, B dan n pada satu baris (1 <= A, B <= 1000, 1
<= n <= 100,000,000). Tiga sifar menandakan tamatnya input dan
kes ujian ini tidak akan diproses.

Output

Untuk setiap kes ujian, cetak nilai f(n) pada satu baris.

Sampel Input

1 1 3

1 2 10

0 0 0

Sampel Output

2

5

#include <iostream>
using namespace std;
int f[54] = {0, 1, 1};
int main()
{
    int A, B, n, q = 1;
    while (cin >> A >> B >> n && A && B && n)
    {
        for (int i = 3; i < 54; ++i)
        {
            f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;   //这里
            if (i > 4)
            {    if (f[i - 1] == f[3] && f[i] == f[4])
                {
                    q = i - 4; //特别是这个地方

                }
            }
        }
        cout << f[n % q] << endl;  //这里

    }

    return 0;
}

Answer 1

Tidakkah terdapat laporan penyelesaian masalah dalam talian? Soalan ini sedang mencari pola Q dalam soalan ini sedang mencari tempoh T. Mengenai mengapa kita hanya mencari 54 yang pertama, ini memerlukan penaakulan matematik yang teliti. Saya mengujinya dan mendapati bahawa 53 adalah OK, tetapi tidak di bawah 52.

--------------Penyimpangan-------------

Untuk soalan seperti ini, pada pandangan pertama, ia seperti membuat jadual atau mencari corak.

Di bawah premis bahawa soalan ini bukan soalan yang salah, pasti ada dua cara untuk menyelesaikan soalan seperti ini: membuat jadual ganas atau mencari corak Yang pertama bermaksud soalan ini adalah soalan yang besar, dan yang kedua bermaksud soalan ini adalah soalan penaakulan, bukan? Air bergantung kepada kesukaran penaakulan, tetapi sejauh soalan ini, ia adalah masalah air yang besar 1000 sehingga mereka menemui tempoh dan melompat keluar.

Answer 2

Perbincangan berikut adalah terhadi>=1:

• Jelas sekalif(i) in { 0 .. 6}

• Jadi<f(i-2), f(i-1)>ruang negeri ini terhad, maksimum tidak melebihi 49

• Jadi f(i) mempunyai haid, dan 49 adalah period

• Kemudian hitung keseluruhan kitaran dan cari nomborf(n)

  yang berada pada kedudukan yang sama dalam kitaran dengan

Ditambah:

• q dalam kod anda bukanlah tempoh yang paling singkat, sebenarnya, anda boleh berhenti apabila anda mendapati tempoh pertama

• Ia mesti dikembalikan apabila n ialah gandaan 49f[0]=0 Ini mungkin pepijat