专栏文章

题解：CF392C Yet Another Number Sequence

ZZBH_799
CF392C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioru5x6
此快照首次捕获于
2025/12/03 00:07
3 个月前
此快照最后确认于
2025/12/03 00:07
3 个月前
查看原文

题目分析

首先，将题目中的式子简化成便于计算的形式：
Ai(k)=ikFi=ik(Fi−1+Fi−2)=(i−1+1)kFi−1+(i−2+2)kFi−2=Fi−1∑j=0k(kj)(i−1)j1k−j+Fi−2∑j=0k(kj)(i−2)j2k−j=∑j=0k(kj)Ai−1(j)+∑j=0k(kj)Ai−22k−j\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≤n≤10181 \le n \le 10^{18}，考虑使用矩阵加速递推。
设初始矩阵 BB 为：
[0,A1(0),A1(1),A1(2),…,A1(k),A0(0),A0(1),…,A0(k)]\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}
其中，第一个元素表示最终答案。那么，转移 ii 步后，BB 应该为下面的矩阵：
[∑j=1i−1Aj(k),Ai(0),Ai(1),…,Ai(k),Ai−1(0),Ai−1(1),…,Ai−1(k)]\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}
那么，结合上面的递推式，我们能够得出转移矩阵 CC：
[∑j=1i−1Aj(k)Ai(0)Ai(1)…Ai(k)Ai−1(0)Ai−1(1)…Ai−1(k)∑j=1i−1Aj(k)100…000…0Ai(0)0(00)(10)…(k0)10…0Ai(1)00(11)…(k1)01…0…………………………Ai(k)100…(kk)00…1Ai−1(0)0(00)20(10)21…(k0)2k00…0Ai−1(1)00(11)20…(k1)2k−100…0…………………………Ai−1(k)000…(kk)2000…0]\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

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...