Python3(3.5.2) 解法, 执行用时: 30ms, 内存消耗: 3560K, 提交时间: 2019-09-20 21:36:20

mod=998244353
def inv(t):
    if t==1:
        return 1
    else:
        return (mod-mod//t)*inv(mod%t)%mod
def mat_mul(x,y):
    res = [[0 for i in range(2)] for i in range(2)]
    for i in range (0,2):
        for j in range (0,2):
            for k in range (0,2):
                res[i][j]=(res[i][j]+x[i][k]*y[k][j])%mod
    return res
def mat_pow(n):
    c = [[0 for i in range(2)] for i in range(2)]
    c[0][0]=c[0][1]=c[1][0]=1;
    Cs=[[0 for i in range(2)] for i in range(2)]
    Cs[0][0]=Cs[1][1]=1
    while n>0:
        if n&1:
            Cs=mat_mul(Cs,c)
        c=mat_mul(c,c)
        n>>=1
    return Cs[0][1]

n=int(input())
add1=mat_pow(n+1)
add2=mat_pow(n)
add3=mat_pow(n-1)
ans=(n*add1%mod-add2%mod+n*add3%mod)*inv(5)%mod
print(ans)

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-09-20 21:10:08

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,inv5=598946612;
typedef long long LL;
LL n;
struct MAT{
	int a[2][2];
	MAT operator*(MAT b){
		MAT res;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++){
			res.a[i][j]=0;
			for(int k=0;k<2;k++){
				res.a[i][j]=(res.a[i][j]+1LL*a[i][k]*b.a[k][j]%mod)%mod;
			}
		}return res;
	}
}A,B,C;
int fib(LL x){
	A.a[0][0]=0;A.a[0][1]=A.a[1][0]=A.a[1][1]=1;
	B.a[0][0]=B.a[0][1]=B.a[1][1]=0;B.a[1][0]=1;
	C.a[0][0]=C.a[1][1]=1;C.a[0][1]=C.a[1][0]=0;
	for(;x;x>>=1,A=A*A){
		if(x&1)C=C*A;
	}
	C=C*B;
	return C.a[0][0];
}
int main(){
	scanf("%lld",&n);
	printf("%d\n",(n%mod*fib(n+1)%mod-fib(n)+n%mod*fib(n-1)%mod+mod)%mod*inv5%mod);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2019-09-20 19:10:18

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mo=998244353;
struct mat{
	ll a[4][4];
}e,a,b,c;
mat mul(mat a,mat b){
	mat c;
	memset(c.a,0,sizeof c.a);
	for (int i=0;i<4;i++)
	for (int j=0;j<4;j++)
	for (int k=0;k<4;k++){
		(c.a[i][j]+=a.a[i][k]*b.a[k][j])%=mo;
	}
	return c;
}
ll n;
int main(){
	cin>>n;n--;
	for (int i=0;i<4;i++)e.a[i][i]=1;
	a.a[0][0]=a.a[0][1]=a.a[1][0]=a.a[2][0]=a.a[2][2]=a.a[2][3]=a.a[3][2]=1;
	c=e;
	while (n){
		if (n&1)c=mul(c,a);
		a=mul(a,a);
		n>>=1;
	}
	cout<<c.a[2][0]<<endl;
}