牛客 - 斐波拉契和（线性BM）

传送门：牛客 - 斐波拉契和

思路分析

直接套BM模板就行了

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int mod = 998244353; 

namespace linear_seq {
    #define pb push_back
    const ll MOD=998244353;
    ll qp(ll a,ll b){
        ll x=1; a%=MOD;
        while(b){if(b&1) x=x*a%MOD;    a=a*a%MOD; b>>=1;}
        return x;
    }
    inline vector<int> BM(vector<int> x){
        vector<int> ls,cur;
        int pn=0,lf,ld;
        for(int i=0;i<int(x.size());++i){
            ll t=-x[i]%MOD;
            for(int j=0;j<int(cur.size());++j)   t=(t+x[i-j-1]*(ll)cur[j])%MOD;
            if(!t) continue;
            if(!cur.size()){cur.resize(i+1); lf=i; ld=t; continue;}
            ll k=-t*qp(ld,MOD-2)%MOD;
            vector<int> c(i-lf-1); c.pb(-k);
            for(int j=0;j<int(ls.size());++j) c.pb(ls[j]*k%MOD);
            if(c.size()<cur.size()) c.resize(cur.size());
            for(int j=0;j<int(cur.size());++j)    c[j]=(c[j]+cur[j])%MOD;
            if(i-lf+(int)ls.size()>=(int)cur.size())    ls=cur,lf=i,ld=t;
            cur=c;
        }
        vector<int>&o=cur;
        for(int i=0;i<int(o.size());++i)    o[i]=(o[i]%MOD+MOD)%MOD;
        return o;
    }
    const int SZ=10010;
    int N; ll a[SZ],h[SZ],t_[SZ],s[SZ],t[SZ];
    inline void mull(ll*p,ll*q){
        for(int i=0;i<N+N;++i) t_[i]=0;
        for(int i=0;i<N;++i) if(p[i])
            for(int j=0;j<N;++j)    t_[i+j]=(t_[i+j]+p[i]*q[j])%MOD;
        for(int i=N+N-1;i>=N;--i) if(t_[i])
            for(int j=N-1;~j;--j)    t_[i-j-1]=(t_[i-j-1]+t_[i]*h[j])%MOD;
        for(int i=0;i<N;++i) p[i]=t_[i];
    }
    inline ll calc(ll K){
        for(int i=N;~i;--i) s[i]=t[i]=0;
        s[0]=1; if(N!=1) t[1]=1; else t[0]=h[0];
        for(;K;mull(t,t),K>>=1) if(K&1) mull(s,t); ll su=0;
        for(int i=0;i<N;++i) su=(su+s[i]*a[i])%MOD;
        return (su%MOD+MOD)%MOD;
    }
    inline int gao(vector<int> x,ll n){
        if(n<int(x.size())) return x[n];
        vector<int> v=BM(x); N=v.size(); if(!N) return 0;
        for(int i=0;i<N;++i) h[i]=v[i],a[i]=x[i];
        return calc(n);
    }
}


ll qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n&1) res = res * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return res;
}

ll f[1111],fib[1111];

int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=1010;i++) f[i] = qpow(i,k)%mod;
    fib[1] = 1,fib[2] = 1;
    for(int i=3;i<=1010;i++) fib[i] = (fib[i-1]+fib[i-2])%mod;
    ll sum = 0;
    vector<int>x;
    for(int i=1;i<=1010;i++){
        sum = (sum+f[i]*fib[i]%mod)%mod;
        x.pb(sum);
    }
    cout<<linear_seq::gao(x,n-1)<<endl;




    return 0;
}