HDU
题意:已知F0 = 0,F1 = 1,Fn = Fn - 1 + Fn - 2(n >= 2), 且若
分析:找规律可得,F2*k+3 - 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 ", (Q_POW(a, n - 1) - 1 + MOD) % MOD); } return 0; }