P4834 【萨塔尼亚的期末考试】

$\Large\mathscr{D}\mathcal{escription}$

一句话题意 $:$ 求

答案对 $998244353$ 取模。

$\Large\mathscr{S}\mathcal{olution}$

重点是要求 $\sum\limits_{i = 1}^n \text{Fib}_i \times i$,分母上的直接求逆元就行了。

刚开始以为是一道矩阵水题,就直接从后往前推,然后累加一下。

这样的话复杂度是 $\mathcal{O}(4^3Tlog_n)$。boom

所以还是得颓柿子$……$

首先,有一个结论 $:$ $\sum\limits_{i = 1}^n \text{Fib}_i$ $=$ $\text{Fib}_{n + 2} - 1$

证明 $:$

$\qquad$ 原式 $=$ $\text{Fib}_1 + \text{Fib}_2 + \text{Fib}_3 + …+\text{Fib}_n + 1 - 1$

$\qquad$ $\qquad$$=$ $\text{Fib}_1 + 2\text{Fib}_2 + \text{Fib}_3 + … + \text{Fib}_n - 1$

$\qquad$ $\qquad$$=$ $\text{Fib}_2 + 2\text{Fib}_3 + … + \text{Fib}_n - 1$

$\qquad$ $\qquad$$……$

$\qquad$ $\qquad$$=$ $\text{Fib}_{n + 2} - 1$

证毕。

然后就可以大力颓柿子了。

之后直接矩阵快速幂就好了。

$\Large\mathscr{C}\mathcal{ode}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

template <typename Tp>
inline void read(Tp &x) {
x = 0;
bool f = true; char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
x = f ? x : -x;
}

const int N = 5, P = 998244353;

int F[N];

struct Matrix {
int m[N][N];
Matrix() {
memset(m, 0, sizeof(m));
}
};
Matrix Dp;

inline Matrix operator * (Matrix A, Matrix B) {
Matrix ret;
for (int k = 1; k <= 2; ++k)
for (int i = 1; i <= 2; ++i) {
int r = A.m[i][k];
for (int j = 1; j <= 2; ++j)
ret.m[i][j] = (ret.m[i][j] + 1LL * r * B.m[k][j] % P) % P;
}
return ret;
}

inline void Mul() {
int ret[N];
memset(ret, 0, sizeof(ret));
for (int j = 1; j <= 2; ++j) {
int r = F[j];
for (int i = 1; i <= 2; ++i)
ret[i] = (ret[i] + 1LL * r * Dp.m[j][i] % P) % P;
}
memcpy(F, ret, sizeof(ret));
}

inline void Power(int x) {
while (x) {
if (x & 1) Mul();
Dp = Dp * Dp;
x >>= 1;
}
}

inline int Power(int a, int x) {
int ret = 1;
while (x) {
if (x & 1) ret = 1LL * ret * a % P;
a = 1LL * a * a % P;
x >>= 1;
}
return ret;
}

inline int Inv(int x) {
return Power(x, P - 2);
}

int main() {
int T;
read(T);
while (T--) {
int n;
read(n);
memset(Dp.m, 0, sizeof(Dp.m));
Dp.m[2][1] = Dp.m[1][2] = Dp.m[2][2] = 1;
F[1] = 0, F[2] = 1;
Power(n + 2);
int Ans = ((1LL * n * F[1] % P - F[2] + 2) % P + P) % P;
Ans = 2LL * Ans % P * Inv(n) % P * Inv(n + 1) % P;
printf("%d\n", Ans);
}
return 0;
}