J斐波那契和 矩阵快速幂

考虑 这个会稍微好求一些。我们做差分，可以得到
我们可以用矩阵快速幂的方法求出所有 ，考虑一个向量，维护Fib(i),Fib(i-1)和所有的，矩阵共k+3维。
得到之后，我们可以展开得到关于 的表达式。 也就是 .

整体复杂度O(k^3 log(n))
也有大佬直接用BM板子过题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modn = 998244353;
struct Mat{
    ll a[105][105];
    Mat(){
        memset(a,0,sizeof(a));\
    }
    ll* operator[](int i){
        return a[i];
    }
};
int W=104;
Mat operator *(Mat &a, Mat &b){
    Mat ans;
    for(int i=0;i<W;i++)for(int j=0;j<W;j++){
        for(int k=0;k<W;k++) {
            ans[i][j] += a[i][k] * b[k][j] % modn;
        }
        ans[i][j]%=modn;
    }
    return ans;
}
ll C[505][505];
ll F_b[505];
ll F[505];
ll pown[505];
Mat powmod(Mat a, ll p){
    Mat ans;
    for(int i=0;i<W;i++)ans[i][i]=1;
    while(p) {
        if (p % 2) {
            ans = ans * a;
        }
        p /= 2;
        a = a * a;
    }
    return ans;
}

int main()
{
    C[0][0]=1;
    for(int i=0;i<500;i++){
        for(int j=0;j<=i;j++){
            C[i+1][j]+=C[i][j];
            C[i+1][j+1]+=C[i][j];
            C[i+1][j]%=modn;
            C[i+1][j+1]%=modn;
        }
    }
    ll n,k;
    cin>>n>>k;
    pown[0]=1;
    for(int i=1;i<=k;i++)
        pown[i]=pown[i-1]*(n%modn)%modn;
    W=k+3;
    Mat ans;
    ans[0][0]=1;
    ans[0][1]=1;
    ans[1][0]=1;
    ans[2][2]=1;
    ans[2][0]=1;
    ans[2][1]=1;
    for(int i=1;i<=k;i++){
        for(int j=0;j<=i;j++){
            ans[i+2][j+2]=C[i][j];
        }
    }

    ans = powmod(ans,n);

    for(int i=0;i<=k;i++)
        F_b[i]=ans[i+2][1];

    F[0]=F_b[0];
    for(int i=1;i<=k;i++){
        ll fi = F_b[i];
        ll flag = 1;
        for(int j=0;j<i;j++){
            flag = modn-flag;
            fi += flag * C[i][j] %modn *pown[i-j]%modn * F[j]%modn;
        }
        fi %= modn;
        fi *= flag;
        F[i]=fi%modn;
    }
    cout<<F[k]<<endl;

    return 0;
}