HDU - 6198 number number number（规律+矩阵快速幂）

题意：已知F= 0，F= 1，F = F + F(n >= 2)，且若n=Fa1+Fa2+...+Fak where 0≤a1≤a2≤⋯≤a，n为正数，则n为mjf-good，否则为mjf-bad，给定k，求最小的mjf-bad。

分析：找规律可得，F - 1，矩阵快速幂即可。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const LL MOD = 998244353;

const double pi = acos(-1.0);

const int MAXN = 100000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

struct Matrix{

    LL r, c;

    LL matrix[2][2];

    Matrix(LL rr, LL cc):r(rr), c(cc){

        memset(matrix, 0, sizeof matrix);

    }

};

Matrix mul(Matrix a, Matrix b){

    Matrix ans(a.r, b.c);

    for(int i = 0; i < a.r; ++i){

        for(int j = 0; j < b.c; ++j){

            for(int k = 0; k < a.c; ++k){

                (ans.matrix[i][j] += (a.matrix[i][k] * b.matrix[k][j]) % MOD) %= MOD;

            }

        }

    }

    return ans;

}

int Q_POW(Matrix a, int n){

    Matrix ans(a.r, a.c);

    ans.matrix[0][0] = ans.matrix[1][1] = 1;

    while(n){

        if(n & 1) ans = mul(ans, a);

        a = mul(a, a);

        n >>= 1;

    }

    return ans.matrix[0][0] % MOD;

}

int main(){

    int k;

    while(scanf("%d", &k) == 1){

        int n = 5 + (k - 1) * 2;

        Matrix a(2, 2);

        a.matrix[0][0] = a.matrix[0][1] = a.matrix[1][0] = 1;

        printf("%lld\n", (Q_POW(a, n - 1) - 1 + MOD) % MOD);

    }

    return 0;

}