【肥不垃圾数列】number number number

矩阵乘法

传送门：HDU6198

思路：找规律即可（讲道理我不会证）

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define mod 998244353
LL n,x;
struct matrix{
    LL s[4][4];
    
    matrix(){memset(s,0,sizeof s);}
    
    matrix operator * (const matrix &n) const {
        matrix c;
        for (int i=1;i<=3;++i)
            for (int j=1;j<=3;++j)
                for (int k=1;k<=3;++k)
                    c.s[i][j]=(c.s[i][j]+s[i][k]*n.s[k][j])%mod;
        return c;
    }
}ans,k,l;
matrix pow(matrix k,LL x){
    if (x==1) return k;
    
    matrix u=pow(k,x>>1);
    if ((x&1)==1) return u*u*k;
    else return u*u;
}
    
int main(){
    while (~scanf("%lld",&x)){
        k.s[1][1]=1;
        k.s[1][2]=1;
        k.s[2][1]=1;
        k.s[2][2]=0;
        l.s[1][1]=1;
        l.s[2][1]=1;
        ans=pow(k,x*2+1)*l;
        printf("%lld\n",((ans.s[1][1]-1)%mod+mod%mod));
    }
    return 0;
}