Eight Function 2

2 secs 1024 MB

dyktr_06

問題

提出

テストケース

解説

関数の形がフィボナッチ数列にそっくりであることに注目してみましょう。

フィボナッチ数列の第 $N$ 項は、行列累乗を用いることで $O(log N)$ で求めることができます。

また、 $f'(0) = a, f'(1) = b, f'(x) = f'(x - 2) + f'(x - 1) \: (2 \leq x)$ として、 $f'(0)$ から順番に計算してみましょう。
$a、b、a + b、a + 2b、2a + 3b、3a + 5b$ とフィボナッチ数列の値が係数として現れることが分かります。

よって、フィボナッチ数列の第 $N$ 項の値を $g(N)$ とすると、
$f(N) = 8 \times g(N - 1) + 88 \times g(N) \: (2 \leq N)$
と求められます。

したがって、この問題を十分高速に解くことができました。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

const long long MOD = 998244353;

// 行列の積を計算
vector<vector<long long>> mul(vector<vector<long long>> a, vector<vector<long long>> b){
    vector<vector<long long>> res((int) a.size(), vector<long long>(b[0].size()));
    for(int i = 0; i < (int) a.size(); i++){
        for(int j = 0; j < (int) b[0].size(); j++){
            for(int k = 0; k < (int) b.size(); k++){
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}

// 繰り返し二乗法
long long calc(long long n){
    vector<vector<long long>> a(2, vector<long long>(2));
    a[0][0] = 1; a[0][1] = 1;
    a[1][0] = 1; a[1][1] = 0;

    vector<vector<long long>> b(2, vector<long long>(2, 0));
    for(int i = 0; i < 2; i++) b[i][i] = 1;

    while(n > 0){
        if(n & 1) b = mul(a, b);
        a = mul(a, a);
        n >>= 1;
    }
    return b[1][0];
}

int main(){
    long long n;
    cin >> n;
    if(n == 0){
        cout << 8 << endl;
    }else if(n == 1){
        cout << 88 << endl;
    }else{
        long long ans = 88 * calc(n) + 8 * calc(n - 1);
        ans %= MOD;
        cout << ans << endl;
    }
}