题解：CF392C Yet Another Number Sequence

· · 题解

题目分析

首先，将题目中的式子简化成便于计算的形式：

\begin{align*} A_i(k) &=i^k F_i \\ &=i^k(F_{i-1}+F_{i-2}) \\ &=(i-1+1)^k F_{i-1}+(i-2+2)^k F_{i-2} \\ &=F_{i-1}\sum_{j=0}^k{\binom{k}{j}(i-1)^j 1^{k-j}}+F_{i-2}\sum_{j=0}^k{\binom{k}{j}(i-2)^j 2^{k-j}} \\ &=\sum_{j=0}^k{\binom{k}{j}A_{i-1}(j)}+\sum_{j=0}^k{\binom{k}{j}A_{i-2}2^{k-j}} \end{align*}

发现是个递推式，同时 1 \le n \le 10^{18}，考虑使用矩阵加速递推。

设初始矩阵 B 为：

\begin{bmatrix} 0,A_{1}(0),A_{1}(1),A_{1}(2),\dots,A_1(k),A_0(0),A_0(1),\dots,A_0(k) \end{bmatrix}

其中，第一个元素表示最终答案。那么，转移 i 步后，B 应该为下面的矩阵：

\begin{bmatrix} \sum_{j=1}^{i-1} A_j(k),A_i(0),A_i(1),\dots,A_i(k),A_{i-1}(0),A_{i-1}(1),\dots,A_{i-1}(k) \end{bmatrix}

那么，结合上面的递推式，我们能够得出转移矩阵 C：

\begin{bmatrix} & \sum_{j=1}^{i-1} A_j(k) & A_i(0) & A_i(1) & \dots & A_i(k) & A_{i-1}(0) & A_{i-1}(1) & \dots & A_{i-1}(k) \\ \sum_{j=1}^{i-1} A_j(k) & 1 & 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0 \\ A_i(0) & 0 & \binom{0}{0} & \binom{1}{0} & \dots & \binom{k}{0} & 1 & 0 & \dots & 0 \\ A_i(1) & 0 & 0 & \binom{1}{1} & \dots & \binom{k}{1} & 0 & 1 & \dots &0 \\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ A_i(k) & 1 & 0 & 0 & \dots & \binom{k}{k} & 0 & 0 & \dots & 1 \\ A_{i-1}(0) & 0 & \binom{0}{0}2^0 & \binom{1}{0}2^1 & \dots & \binom{k}{0}2^k & 0 & 0 & \dots & 0 \\ A_{i-1}(1) & 0 & 0 & \binom{1}{1}2^0 & \dots & \binom{k}{1}2^{k-1} & 0 & 0 & \dots & 0 \\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ A_{i-1}(k) & 0 & 0 & 0 & \dots & \binom{k}{k}2^0 & 0 & 0 & \dots & 0 \end{bmatrix}

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using i128=__int128;

const int mod=1e9+7;
ll n,c[45][45],pw[45];
int m;

struct matrix{
    vector<vector<ll>>a;
    matrix(int n,int m,ll v){
        a.resize(n,vector<ll>(m,v));
    }
    matrix operator *(const matrix &b)const{
        int n=a.size(),m=a[0].size(),s=b.a[0].size();
        matrix res(n,s,0);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<s;k++)
                    res.a[i][k]=(res.a[i][k]+a[i][j]*b.a[j][k]%mod)%mod;
            }
        }
        return res;
    }
};

matrix power(matrix p,ll q){
    matrix res(p.a.size(),p.a.size(),0);
    for(int i=0;i<p.a.size();i++) res.a[i][i]=1;
    while(q){
        if(q&1) res=res*p;
        p=p*p,q>>=1;
    }
    return res;
}

void solve(){
    cin>>n>>m;

    c[0][0]=1;
    for(int i=1;i<=m;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    pw[0]=1;
    for(int i=1;i<=m;i++) pw[i]=pw[i-1]*2%mod;

    matrix e(2*(m+1)+1,2*(m+1)+1,0),ans(1,2*(m+1)+1,0);
    e.a[0][0]=e.a[m+1][0]=1;
    for(int i=1;i<=m+1;i++){
        for(int j=1;j<=m+1;j++){
            if(i>j) continue;
            e.a[i][j]=c[j-1][i-1];
        }
    }
    for(int i=m+2;i<=2*(m+1);i++){
        for(int j=1;j<=m+1;j++){
            if(i-m-1>j) continue;
            e.a[i][j]=c[j-1][i-m-2]*pw[j-i+m+1]%mod;
        }
    }
    for(int j=m+2;j<=2*(m+1);j++) e.a[j-m-1][j]=1;
    for(int i=1;i<=m+2;i++) ans.a[0][i]=1;
    e=power(e,n),ans=ans*e;

    cout<<ans.a[0][0]<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) solve();
    return 0;
}