【題解】TOJ 638. 遞回呀遞回

題意

\(a, b, c, r_0, r_1, n, p\) 和遞迴關係式 \(r_{i+2} = a \cdot r_{i+1} \cdot r_i + b \cdot r_{i+1} + c \cdot r_i\)，求 \(r_n \mod p\)

• \(n \le 10^{18}\)
• \(p \le 10^4\)

觀察

• 因為有 \(r_{i+1} \cdot r_i\)，不能用矩陣快速冪
• 只會用到前兩項
• \(p \le 10^4\)，因此前兩項的可能性不超過 \(10^8\) 種

作法

當只要出現兩項 \({f[i-1],f[i]}\) 曾經出現過，就代表接下來會循環： \(A, B, C, ..., X, ..., X, ..., X...\)

我們紀錄第一次循環出現的位置和循環節長度，若 \(n\) 在循環出現前可以直接回答，否則計算出 \(n\) 在循環節中的哪個位置再回答。

AC Code

const int N = 5e7;

int a, b, c, r0, r1, n, p;
int f[N];
map<pii,int> mp; //{{f[i-1], f[i]}, i}

signed main(){
    cin >> a >> b >> c >> f[0] >> f[1] >> n >> p;
    a%=p, b%=p, c%=p, f[0]%=p, f[1]%=p;
    mp[{f[0],f[1]}] = 1;

    int op, len;
    rep(i,2,N){
        f[i] = ((a*f[i-1]*f[i-2]%p + b*f[i-1]%p + c*f[i-2]%p)%p+p)%p;
        if (mp[{f[i-1],f[i]}] != 0){
            op = mp[{f[i-1],f[i]}];
            len = i - op;
            break;
        }
        mp[{f[i-1],f[i]}] = i;
    }
    if (n <= op+len) cout << f[n] << '\n';
    else cout << f[(n-op)%len+op] << '\n';
}